Optimal partition and effective dynamics of complex networks
- 10 June 2008
- journal article
- research article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 105 (23) , 7907-7912
Abstract
Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.Keywords
This publication has 30 references indexed in Scilit:
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Community detection in complex networks using extremal optimizationPhysical Review E, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Detecting Fuzzy Community Structures in Complex Networks with a Potts ModelPhysical Review Letters, 2004
- Detecting network communities: a new systematic and efficient algorithmJournal of Statistical Mechanics: Theory and Experiment, 2004
- Fast algorithm for detecting community structure in networksPhysical Review E, 2004
- Finding communities in linear time: a physics approachThe European Physical Journal B, 2004
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000