Maximal entropy random walk in community finding

Abstract

The aim of this paper is to check feasibility of using the maximal-entropy random walk in algorithms finding communities in complex networks. A number of such algorithms exploit an ordinary or a biased random walk for this purpose. Their key part is a (dis)similarity matrix, according to which nodes are grouped. This study encompasses the use of the stochastic matrix of a random walk, its mean first-passage time matrix, and a matrix of weighted paths count. We briefly indicate the connection between those quantities and propose substituting the maximal-entropy random walk for the previously chosen models. This unique random walk maximises the entropy of ensembles of paths of given length and endpoints, which results in equiprobability of those paths. We compare performance of the selected algorithms on LFR benchmark graphs. The results show that the change in performance depends very strongly on the particular algorithm, and can lead to slight improvements as well as significant deterioration.

7 pages, 4 figures, submitted to European Physical Journal Special Topics following the 4-th Conference on Statistical Physics: Modern Trends and Applications, July 3-6, 2012 Lviv, Ukraine

References in corpus (22)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Communicability in complex networks
• Detecting Network Communities: a new systematic and efficient algorithm
• Detecting communities in large networks
• Distance, dissimilarity index, and network community structure
• Modularity and Extreme Edges of the Internet
• Localization of maximal entropy random walk
• The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
• Network Landscape from a Brownian Particle's Perspective
• Maximal-entropy random walks in complex networks with limited information
• Centrality measures and thermodynamic formalism for complex networks
• Communicability Graph and Community Structures in Complex Networks
• Topologically biased random walk with application for community finding in networks
• Diffusion and networks: A powerful combination!
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Random elastic networks : strong disorder renormalization approach
• Maximal-entropy random walk unifies centrality measures
• Maximal Entropy Random Walk: solvable cases of dynamics

Cited by in corpus (13)

• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Mean first-passage time for maximal-entropy random walks in complex networks
• Path Integral Based Convolution and Pooling for Graph Neural Networks
• Maximal entropy random walk improves efficiency of trapping in dendrimers
• PAN: Path Integral Based Convolution for Deep Graph Neural Networks
• Multitarget search on complex networks: A logarithmic growth of global mean random cover time
• Community detection by label propagation with compression of flow
• Generalized Markov stability of network communities
• Maximal dispersion of adaptive random walks
• Intermittency as metastability: a predictive approach to evolution in disordered environments
• Community Structure aware Embedding of Nodes in a Network
• Stationary Schrödinger Equation and Darwin Term from Maximal Entropy Random Walk