SPM - Shannon-Parry Measure


SPM value of a node is the probability of arriving at that node after a large number of steps, in other words, it is the frequency of a typical long path visit the node. The main idea comes from symbolic dynamics and compatible Markov processes on the network. $SPM$ can characterize the node importance effectively and can be applied to directed networks and weighted networks. Effectiveness of $SPM$ is embodied in its sensibility and robustness.

Let $A$ be an irreducible and aperiodic non-negative $n \times n$ matrix with spectral radius $\rho (A)$. By Perron-Frobenius theorem, $\lambda$ is a simple eigenvalue of $A$. $A$ has a left eigenvector $u$ and a right eigenvector $v$ with eigenvalue $\lambda$ whose components are all positive. Then the $n\times n$ matrix $ \{P_{i,j}\}$ defined by:

$$P_{i,j}={A_{i,j} u_i \over \lambda u_i }$$

is a transition matrix, which induce a compatible Markov Chain of the $SFT(Y,T)$. The stationary distribution of
the Markov Chain is

$$\pi={u_i u_i \over \sum_i u_i u_i}$$

and the Kolmogorov-Sinai entropy is $log \lambda$. The corresponding Markov measure is called the Shannon-Parry measure $(SPM)$.

$SPM$ incorporates both the local neighborhood and global properties of a network, this method can characterize the node importance effectively, and can be applied to directed networks and weighted networks and also, is sensitive and robust.


  • Huang, S., Cui, H. and Ding, Y., 2014. Evaluation of node importance in complex networks. arXiv preprint arXiv:1402.5743. DOI: Publisher web site


There are no comment yet.

Add your comment

Sum of    and  

The rendering mode: