The following Python module computes various notions of algebraic connectivity of directed graphs
https://pypi.org/project/algebraic-connectivity-directed/
Module 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) 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].
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₁, a₂, a₃, a₄ as defined in Ref. [6].
Function compute_mu_directed: compute_mu_directed(G) returns μ(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]). The graph G is a networkx DiGraph object. 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). returns μ₂(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]). The graph G is a networkx DiGraph object.
The function compute_mu_directed accepts multiple arguments. If the input are multiple graphs G₁, G₂, G₃, ... with Lᵢ the Laplacian matrix of Gᵢ, and all Gᵢ 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(Lᵢ-μ*I)+(Lᵢ '-μ*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₁ is the same as the value returned by algebraic_connectivity_directed(G)[0] (see Ref. [2]).
a₂ is the same as ã as described in Ref. [3].
a₃ is described in the proof of Theorem 21 in Ref. [3].
a₄ is equal to η as described in Ref. [4].
We define directed tree in the sense of an arborescence (see Ref. [2]).
If a₁ > 0, then G is connected and the reversal of G contains a spanning directed tree.
If G is balanced, then a₁ ≥ 0 and a₁ > 0 ⇔ G is connected ⇔ G is strongly connected.
If a₂ > 0, then G is connected and the reversal of G contains a spanning directed tree.
If G is strongly connected then a₃ ≥ a₂ > 0.
a₄ > 0 if and only if the reversal of the graph contains a spanning directed tree.
a₁ ≤ μ ≤ μ₂.
μ = μ₂ = 1 if the reversal of the graph is a directed tree.
If the Laplacian matrix L is a normal matrix, then a₁ = μ = μ₂ and G is connected ⇔ G is strongly connected.
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
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.