Python functions to compute various notions of algebraic connectivity of directed graphs
Requires python
>= 3.5 and packages numpy
, scipy
, networkx
and cvxpy
.
pip install algebraic-connectivity-directed
After installation, run from algebraic_connectivity_directed import *
There are 4 main functions:
-
Function
algebraic_connectivity_directed
: algebraic_connectivity_directed(G) returnsa, b, M
wherea
is the algebraic connectivity of the digraph G. The graph G is anetworkx
DiGraph object. The definitions ofa, b, M = Q'*(L+L')*Q/2
can be found in Ref. [2]. -
Function
algebraic_connectivity_directed_variants
: algebraic_connectivity_directed_variants(G,k) returns variations of algebraic connectivity of the digraph G. The graphG
is anetworkx
DiGraph object. Settingk = 1, 2, 3, 4
returns a1, a2, a3, a4 as defined in Ref. [6]. -
Function
compute_mu_directed
: compute_mu_directed(G) returnsmu(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 matrixU
with nonpositive off-diagonal elements whereL
is the Laplacian matrix of graphG
(see Ref. [1]). Computed number may be smaller than the defined value due to the difficulty of the SDP problem. -
Function
compute_mu2_directed
: compute_mu2_directed(G) returnsmu2(G)
defined as the eigenvalue with the smallest real part among eigenvalues of the Laplacian matrixL
that do not belong to the all 1's vectore
(see Ref. [5]).
compute_mu_directed
accepts multiple arguments. If the input are multiple graphs G1, G2, G3, ... with Li the Laplacian matrix of Gi,
and all Gi have the same number of nodes,
then compute_mu_directed(G1, G2, G3, ...) 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(Li-μ*I)+(Li '-μ*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.
a1 is the same as the value returned by algebraic_connectivity_directed(G)[0] (see Ref. [2]).
a2 is the same as ã as described in Ref. [3].
a3 is described in the proof of Theorem 21 in Ref. [3].
a4 is equal to η as described in Ref. [4].
We define directed tree in the sense of an arborescence (see Ref. [2]).
-
If a1 > 0, then G is connected and the reversal of G contains a spanning directed tree.
-
If G is balanced, then a1 ≥ 0 and a1 > 0 ⇔ G is connected ⇔ G is strongly connected.
-
If a2 > 0, then G is connected and the reversal of G contains a spanning directed tree.
-
If G is strongly connected then a3 ≥ a2 > 0.
-
a4 > 0 if and only if the reversal of the graph contains a spanning directed tree.
-
a1 ≤ μ ≤ μ2.
-
μ = μ2 = 1 if the reversal of the graph is a directed tree.
-
If the Laplacian matrix L is a normal matrix, then a1 = μ = μ2 and G is connected ⇔ G is strongly connected.
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
-
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.
-
C. W. Wu, "Algebraic connecivity of directed graphs", Linear and Multilinear Algebra, vol. 53, no. 3, pp. 203-223, 2005.
-
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.
-
C. W. Wu, "Synchronization in networks of nonlinear dynamical systems coupled via a directed graph", Nonlinearity, vol. 18, pp. 1057-1064, 2005.
-
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.
-
C. W. Wu, "Synchronization in Complex Networks of Nonlinear Dynamical Systems", World Scientific, 2007.
-
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.