Constructors module

Module to create constructors of quality matrix and null models.

The generalized Markov Stability is given as

\[Q_{gen}(t,H) = \mathrm{Tr} \left [H^T \left (F(t)-\sum_{k=1}^m v_{2k-1} v_{2k}^T\right)H\right]\]

where \(F(t)\) is the quality matrix and \(v_k\) are null model vectors.

In the following we denote by \(A\) the adjacency matrix of a graph with \(N\) nodes and \(M\) edges. The out-degree of the graph is given by \(d=A\boldsymbol{1}\), where \(\boldsymbol{1}\) is the vector of ones, and we denote the diagonal degree matrix by \(D=\mathrm{diag}(d)\).

pygenstability.constructors.load_constructor(constructor, graph, **kwargs)

Load a constructor from its name, or as a custom Constructor class.

class pygenstability.constructors.Constructor(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Parent class for generalized Markov Stability constructor.

This class encodes generalized Markov Stability through the quality matrix and null models. Use the method prepare to load and compute scale independent quantities, and the method get_data to return quality matrix, null model, and possible global shift.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

get_data(scale)

Return quality and null model at given scale as well as global shift (or None).

User has to define the _get_data so we can enure numpy does not use multiple threads

class pygenstability.constructors.constructor_linearized(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for continuous linearized Markov Stability.

The quality matrix is:

\[F(t) = t\frac{A}{2M},\]

and the associated null model is \(v_1=v_2=\frac{d}{2M}\).

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

class pygenstability.constructors.constructor_continuous_combinatorial(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for continuous combinatorial Markov Stability.

This implementation follows equation (16) in [1]. The quality matrix is:

\[F(t) = \Pi\exp(-tL/<d>)\]

where \(<d>=(\boldsymbol{1}^T D \boldsymbol{1})/N\) is the average degree, \(L=D-A\) is the combinatorial Laplacian and \(\Pi=\mathrm{diag}(\pi)\), with null model \(v_1=v_2=\pi=\frac{\boldsymbol{1}}{N}\).

References

[1] (1,2,3)

Lambiotte, R., Delvenne, J.-C., & Barahona, M. (2019). Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks. IEEE Trans. Netw. Sci. Eng., 1(2), p. 76-90.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

class pygenstability.constructors.constructor_continuous_normalized(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for continuous normalized Markov Stability.

This implementation follows equation (10) in [1]. The quality matrix is:

\[F(t) = \Pi\exp(-tL)\]

where \(L=D^{-1}(D-A)\) is the random-walk normalized Laplacian and \(\Pi=\mathrm{diag}(\pi)\) with null model \(v_1=v_2=\pi=\frac{d}{2M}\).

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

class pygenstability.constructors.constructor_signed_modularity(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor of signed modularity.

This implementation is equation (18) of [2], where quality is the adjacency matrix and the null model is the difference between the standard modularity null models based on positive and negative degree vectors.

References

[2]

Gomez, S., Jensen, P., & Arenas, A. (2009). Analysis of community structure in networks of correlated data. Physical Review E, 80(1), 016114.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

class pygenstability.constructors.constructor_signed_combinatorial(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for continuous signed combinatorial Markov Stability.

This implementation follows equation (19) in [3]. The quality matrix is:

\[F(t) = \exp(-tL)^T\exp(-tL)\]

where \(L=D_{\mathrm{abs}}-A\) is the signed combinatorial Laplacian, \(D_{\mathrm{abs}}=\mathrm{diag}(d_\mathrm{abs})\) the diagonal matrix of absolute node strengths \(d_\mathrm{abs}\), and the associated null model is given by \(v_1=v_2=\boldsymbol{0}\), where \(\boldsymbol{0}\) is the vector of zeros.

References

[3]

Schaub, M., Delvenne, J.-C., Lambiotte, R., & Barahona, M. (2019). Multiscale dynamical embeddings of complex networks. Physical Review E, 99(6), 062308.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

get_data(scale)

Return quality and null model at given scale.

class pygenstability.constructors.constructor_directed(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for directed Markov stability.

The quality matrix is:

\[F(t)=\Pi \exp\left(t \left(M(\alpha)-I\right)\right)\]

where \(I\) denotes the identity matrix, \(M(\alpha)\) is the transition matrix of a random walk with teleportation and damping factor \(0\le \alpha < 1\), and \(\Pi=\mathrm{diag}(\pi)\) for the associated null model \(v_1=v_2=\pi\) given by the eigenvector solving \(\pi M(\alpha) = \pi\), which is related to PageRank. See [1] for details.

The transition matrix \(M(\alpha)\) is given by

\[M(\alpha) = \alpha D^{-1}A+\left((1-\alpha)I+\alpha \mathrm{diag}(a)\right) \frac{\boldsymbol{1}\boldsymbol{1}^T}{N},\]

where \(D\) denotes the diagonal matrix of out-degrees with \(D_{ii}=1\) if the out-degree \(d_i=0\) and \(a\) denotes the vector of dangling nodes, i.e. \(a_i=1\) if the out-degree \(d_i=0\) and \(a_i=0\) otherwise.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.

class pygenstability.constructors.constructor_linearized_directed(graph, with_spectral_gap=False, exp_comp_mode='spectral', **kwargs)

Constructor for linearized directed Markov stability.

The quality matrix is:

\[F(t)=\Pi t M(\alpha)\]

where \(M(\alpha)\) is the transition matrix of a random walk with teleportation and damping factor \(0\le \alpha < 1\), and \(\Pi=\mathrm{diag}(\pi)\) for the associated null model \(v_1=v_2=\pi\) given by the eigenvector solving \(\pi M(\alpha) = \pi\), which is related to PageRank.

The transition matrix \(M(\alpha)\) is given by

\[M(\alpha) = \alpha D^{-1}A+\left((1-\alpha)I+\alpha \mathrm{diag}(a)\right) \frac{\boldsymbol{1}\boldsymbol{1}^T}{N},\]

where \(I\) denotes the identity matrix, \(D\) denotes the diagonal matrix of out-degrees with \(D_{ii}=1\) if the out-degree \(d_i=0\) and \(a\) denotes the vector of dangling nodes, i.e. \(a_i=1\) if the out-degree \(d_i=0\) and \(a_i=0\) otherwise.

The constructor calls the prepare method upon initialisation.

Parameters:

• graph (csgraph) – graph for which to run clustering

• with_spectral_gap (bool) – set to True to use spectral gap to rescale

• kwargs (dict) – any other properties to pass to the constructor.

• exp_comp_mode (str) – mode to compute matrix exponential, can be expm or spectral

prepare(**kwargs)

Prepare the constructor with non-scale dependent computations.