Spectral graph indices and label-propagation communities

EstradaIndex: \(\sum_i e^{\lambda_i} = \mathrm{tr}\, e^A\) (Estrada 2000). Communicability: \(G = e^A\) from the eigen-decomposition, with subgraph centralities (Estrada and Hatano 2008). ModularityMatrix: \(B = A - kk^\top/2m\), its leading eigenpair and spectral bisection, and the modularity of a partition (Newman 2006). PerronFrobenius: spectral radius and unit positive eigenvector. RandicIndex: \(\sum_{uv}(d_u d_v)^\alpha\) (Randic 1975). LabelPropagation: Raghavan et al. (2007) communities with Philox visiting orders and tie-breaks. Identical to the Python arm morie.fn.graphspec; memberships are 0-based as in Python.

Usage

EstradaIndex(A)

Communicability(A)

ModularityMatrix(A, membership = NULL)

PerronFrobenius(A)

RandicIndex(A, alpha = -0.5)

LabelPropagation(A, seed = 1L, max_iter = 100L)

Arguments

A

Symmetric (weighted) adjacency matrix.

membership

Community labels for the modularity.

alpha

Randic exponent.

seed

Philox seed.

max_iter

Maximum sweeps.

Value

Numeric or list.

References

Estrada, E. and Hatano, N. (2008). Communicability in complex networks. Physical Review E 77, 036111.

Newman, M. E. J. (2006). Modularity and community structure in networks. PNAS 103, 8577-8582.

Randic, M. (1975). Characterization of molecular branching. Journal of the American Chemical Society 97, 6609-6615.

Raghavan, U. N., Albert, R. and Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 036106.

Examples

EstradaIndex(matrix(c(0, 1, 1, 0), 2))
#> [1] 3.086161
PerronFrobenius(1 - diag(3))$eigenvalue
#> [1] 2