معرفی شرکت ها
algebraic-connectivity-directed-0.0.9
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشترتوضیحات
Python functions to compute various notions of algebraic connectivity of directed graphs
| ویژگی | مقدار |
|---|---|
| سیستم عامل | - |
| نام فایل | algebraic-connectivity-directed-0.0.9 |
| نام | algebraic-connectivity-directed |
| نسخه کتابخانه | 0.0.9 |
| نگهدارنده | [] |
| ایمیل نگهدارنده | [] |
| نویسنده | Chai Wah Wu |
| ایمیل نویسنده | cwwuieee@gmail.com |
| آدرس صفحه اصلی | https://github.com/postvakje/algebraic-connectivity-directed |
| آدرس اینترنتی | https://pypi.org/project/algebraic-connectivity-directed/ |
| مجوز | LICENSE |
# algebraic-connectivity-directed
[](https://github.com/psf/black)
Python functions to compute various notions of algebraic connectivity of directed graphs
## Requirements
Requires `python` >= 3.5 and packages `numpy`, `scipy`, `networkx` and `cvxpy`.
## Installation
`pip install algebraic-connectivity-directed`
## Usage
After installation, run `from algebraic_connectivity_directed import *`
There are 4 main functions:
1. Function `algebraic_connectivity_directed`: algebraic_connectivity_directed(G) returns `a, b, M` where `a` is the algebraic connectivity of the digraph G. The graph G is a `networkx` DiGraph object. The definitions of `a, b, M = Q'*(L+L')*Q/2` can be found in Ref. [2].
2. Function `algebraic_connectivity_directed_variants`: algebraic_connectivity_directed_variants(G,k) returns variations of algebraic connectivity of the digraph G.
The graph `G` is a `networkx` DiGraph object. Setting `k = 1, 2, 3, 4` returns a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, a<sub>4</sub> as defined in Ref. [6].
3. Function `compute_mu_directed`:
compute_mu_directed(G)
returns `mu(G)` defined as the supremum of numbers μ such that
U(L-μ\*I)+(L'-μ\*I)U is positive semidefinite for some symmetric zero row sums
real matrix `U` with nonpositive off-diagonal elements where `L` is the Laplacian matrix
of graph `G` (see Ref. [1]). Computed number may be smaller than the defined value due to the difficulty of the SDP problem.
4. Function `compute_mu2_directed`:
compute_mu2_directed(G)
returns `mu2(G)` defined as the eigenvalue with the smallest real part among eigenvalues of the Laplacian matrix `L` that do not belong to the all 1's vector `e` (see Ref. [5]).
`compute_mu_directed` accepts multiple arguments. If the input are multiple graphs G<sub>1</sub>, G<sub>2</sub>, G<sub>3</sub>, ... with L<sub>i</sub> the Laplacian matrix of G<sub>i</sub>,
and all G<sub>i</sub> have the same number of nodes,
then compute_mu_directed(G<sub>1</sub>, G<sub>2</sub>, G<sub>3</sub>, ...) returns the supremum of μ such that there
exist some symmetric zero row sums real matrix U with nonpositive off-diagonal elements
where for all i, U(L<sub>i</sub>-μ\*I)+(L<sub>i</sub> '-μ\*I)U is positive semidefinite. This is useful in analyzing
synchronization of networked systems where systems are coupled via multiple networks. See Ref. [7].
The graph G is a `networkx` DiGraph object.
a<sub>1</sub> is the same as the value returned by algebraic_connectivity_directed(G)[0] (see Ref. [2]).
a<sub>2</sub> is the same as ã as described in Ref. [3].
a<sub>3</sub> is described in the proof of Theorem 21 in Ref. [3].
a<sub>4</sub> is equal to η as described in Ref. [4].
### Properties
1. If the reversal of the graph does not contain a spanning directed tree, then a<sub>2</sub> ≤ 0.
2. If G is strongly connected then a<sub>3</sub> ≥ a<sub>2</sub> > 0.
3. a<sub>4</sub> > 0 if and only if the reversal of the graph contains a spanning directed tree.
4. a<sub>1</sub> ≤ μ ≤ μ<sub>2</sub>.
5. μ = μ<sub>2</sub> = 1 if the reversal of the graph is a directed tree (arborescence).
6. If the Laplacian matrix L is a normal matrix, then a<sub>1</sub> = μ = μ<sub>2</sub>.
## Examples
Cycle graph
```
from algebraic_connectivity_directed import *
import networkx as nx
import numpy as np
G = nx.cycle_graph(10,create_using=nx.DiGraph)
print(algebraic_connectivity_directed(G)[0:2])
>> (0.19098300562505233, 2.0)
print(algebraic_connectivity_directed_variants(G,2))
>> 0.1909830056250514
```
Directed graphs of 5 nodes
```
A1 = np.array([[0,0,1,0,0],[0,0,0,1,1],[1,0,0,1,1],[1,1,0,0,1],[0,0,0,1,0]])
G1 = nx.from_numpy_matrix(A1,create_using=nx.DiGraph)
print(compute_mu_directed(G1))
>>> 0.8521009635833089
print(algebraic_connectivity_directed_variants(G1, 4))
>>> 0.6606088707716056
A2 = np.array([[0,1,0,0,1],[0,0,0,1,0],[0,0,0,1,1],[1,0,0,0,0],[1,0,1,1,0]])
G2 = nx.from_numpy_matrix(A2,create_using=nx.DiGraph)
A3 = np.array([[0,1,0,0,0],[1,0,1,0,0],[0,1,0,0,0],[0,0,1,0,0],[1,1,1,0,0]])
G3 = nx.from_numpy_matrix(A3,create_using=nx.DiGraph)
print(compute_mu_directed(G1,G2,G3))
>>> 0.8381214637786955
```
## References
1. C. W. Wu, "Synchronization in coupled arrays of chaotic oscillators
with nonreciprocal coupling", IEEE Transactions on Circuits and Systems-I, vol. 50,
no. 2, pp. 294-297, 2003.
2. C. W. Wu, "Algebraic connecivity of directed graphs",
Linear and Multilinear Algebra, vol. 53, no. 3, pp. 203-223, 2005.
3. C. W. Wu, "On Rayleigh-Ritz ratios of a generalized Laplacian matrix of directed graphs", Linear Algebra
and its applications, vol. 402, pp. 207-227, 2005.
4. C. W. Wu, "Synchronization in networks of nonlinear dynamical systems coupled via a directed graph",
Nonlinearity, vol. 18, pp. 1057-1064, 2005.
5. C. W. Wu, "On a matrix inequality and its application to the synchronization in coupled chaotic systems," Complex Computing-Networks: Brain-like and Wave-oriented Electrodynamic Algorithms, Springer Proceedings in Physics, vol. 104, pp. 279-288, 2006.
6. C. W. Wu, "Synchronization in Complex Networks of Nonlinear Dynamical Systems", World Scientific, 2007.
7. C. W. Wu, "Synchronization in dynamical systems coupled via multiple directed networks,"
IEEE Transactions on Circuits and Systems-II: Express Briefs, vol. 68, no. 5, pp. 1660-1664, 2021.
نیازمندی
| مقدار | نام |
|---|---|
| - | numpy |
| - | scipy |
| - | networkx |
| - | cvxpy |
زبان مورد نیاز
| مقدار | نام |
|---|---|
| >= 3.5 | Python |
نحوه نصب
نصب پکیج whl algebraic-connectivity-directed-0.0.9:
pip install algebraic-connectivity-directed-0.0.9.whl
نصب پکیج tar.gz algebraic-connectivity-directed-0.0.9:
pip install algebraic-connectivity-directed-0.0.9.tar.gz