Coding of Markov dynamics for multiscale community detection in complex networks

Details Coding of Markov dynamics for multiscale community detection in complex networks Coding of Markov dynamics for multiscale community detection in complex networks

2011-09-29

arxiv.org/abs/1109.6642v1

Physics

Physics and Society

9 pages, 5 figures

Scientific paper

The detection of community structure in complex networks is intimately related to the problem of finding a concise description of the network in terms of its modules. This notion has been recently exploited by the Map equation formalism (M. Rosvall and C. T. Bergstrom, PNAS, vol. 105, no. 4, pp. 1118-1123, 2008) through an information-theoretic characterization of the process of coding the transitions of a random walker inside and between communities at stationarity. However, a thorough consideration of the relationship between a time-evolving Markov dynamics and the coding mechanism is still lacking. We show that the original one-step coding scheme used by the Map equation method neglects the internal structure of the communities and introduces an upper scale, the 'field-of-view' limit, for the communities that it can detect. Although the Map equation method is known for its good performance on clique-like graphs, the field-of-view limit can result in undesirable overpartitioning when communities are far from clique-like. We show that a signature of this behavior is a large compression gap: a large deviation of the Map compression from the ideal limit, the entropy rate of the Markov process. To address this issue, we propose a simple dynamic approach that introduces time explicitly into the Map coding procedure through the analysis of the time-evolving multistep transition matrix of the Markov process. The so-induced dynamical zooming across scales can reveal (potentially multiscale) community structure above the field-of-view limit. The relevant partitions are indicated by a small compression gap. Finally, we discuss how the interplay between coding and dynamics could be further developed to improve the detection of community structure in networks.

Affiliated with

Also associated with

No associations

Rating

Coding of Markov dynamics for multiscale community detection in complex networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Coding of Markov dynamics for multiscale community detection in complex networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding of Markov dynamics for multiscale community detection in complex networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-152863