algebraic-connectivity-directed

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₁, a₂, a₃, a₄ 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₁, G₂, G₃, ... with L_i the Laplacian matrix of G_i, and all G_i have the same number of nodes, then compute_mu_directed(G₁, G₂, G₃, ...) 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-μ*I)+(L_i '-μ*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].

Properties

1. If the reversal of the graph does not contain a spanning directed tree, then a₂ ≤ 0.

2. If G is strongly connected then a₃ ≥ a₂ > 0.

3. a₄ > 0 if and only if the reversal of the graph contains a spanning directed tree.

4. a₁ ≤ μ ≤ μ₂.

5. μ = μ₂ = 1 if the reversal of the graph is a directed tree (arborescence).

6. If the Laplacian matrix L is a normal matrix, then a₁ = μ = μ₂.

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.