Ant Colony Optimization with a New Random Walk Model for Community Detection in Complex Networks
Preprint
Abstract
Detecting communities from complex networks has recently triggered great interest. Aiming at this problem, a new ant colony optimization strategy building on the Markov random walks theory, which is named as MACO, is proposed in this paper. The framework of ant colony optimization is taken as the basic framework in this algorithm. In each iteration, a Markov random walk model is employed as heuristic rule; all of the ants local solutions are aggregated to a global one through an idea of clustering ensemble, which then will be used to update a pheromone matrix. The strategy relies on the progressive strengthening of within-community links and the weakening of between-community links. Gradually this converges to a solution where the underlying community structure of the complex network will become clearly visible. The proposed MACO has been evaluated both on synthetic benchmarks and on some real-world networks, and compared with some present competing algorithms. Experimental result has shown that MACO is highly effective for discovering communities.Keywords
All Related Versions
- Version 1, 2013-03-24, ArXiv
- Published version: Advances in Complex Systems, 14 (05), 795.
This publication has 23 references indexed in Scilit:
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Comparing community structure identificationJournal of Statistical Mechanics: Theory and Experiment, 2005
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Functional cartography of complex metabolic networksNature, 2005
- Defining and identifying communities in networksProceedings of the National Academy of Sciences, 2004
- The emergent properties of a dolphin social networkProceedings Of The Royal Society B-Biological Sciences, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- Random graphs with arbitrary degree distributions and their applicationsPhysical Review E, 2001
- An Information Flow Model for Conflict and Fission in Small GroupsJournal of Anthropological Research, 1977
- The small-world problem1967