Abstract
Community detection method of complex network with a combination of TSP model and ant colony optimization is proposed in this paper. The topology relationship of network node is transformed into distance, thus the community detection problem is transformed into a path optimization problem (TSP) and solved by using ant colony algorithm, and then the pheromone matrix is used to achieve the community clustering by the convergence of algorithm. Experimental results show that, the use of TSP path length as fitness is feasible, and compared with some representative algorithms, TSPP algorithm can cluster out the number of real communities in network effectively, which has a higher clustering accuracy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Girvan, M., Newman, M.: Community structure in social and biological networks. Proceedings of National Academy of Science 9(12), 7821–7826 (2002)
Newman, J.: Fast algorithm for detecting community structure in networks. Physical Review E 69(6), 66133 (2004)
Guimerà, R., Amaral, L.: Functional Cartography of Complex Metabolic Networks. Nature 433(7028), 895–900 (2005)
Newman, J.: Detecting Community Structure in Networks. European Physical Journal B 38(2), 321–330 (2004)
Duch, J., Arenas, A.: Community Detection in Complex Networks Using Extremal optimization. Physical Review E 72(2), 27104 (2005)
Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 10, 10008 (2010)
Lü, Z., Huang, W.: Iterated Tabu Search for Identifying Community Structure in Complex networks. Physical Review E 80(2), 26130 (2009)
Yang, B., Cheung, W., Liu, J.: Community mining from signed social networks. IEEE Trans. on Knowledge and Data Engineering 19(10), 1333–1348 (2007)
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)
Raghavan, U., Albert, R., Kumara, S.: Near Linear-time Algorithm to Detect Community structures in largescale networks. Physical Review E 76(3), 36106 (2007)
Rosvall, M., Bergstrom, C.T.: An Information-theoretic Framework for Resolving community structure in complex networks. Proc. Natl. Acad. Sci. USA 104(18), 7327–7331 (2007)
Jin, D., Yang, B., Liu, J., Liu, D.: Ant Colony Optimization Based on Random Walk for Community Detection in Complex Networks. Journal of Software 23(3), 451–464 (2012)
He, Z., Wang, J., Liu, S.: TSP-Chord: An Improved Chord Model with Physical Topology Awareness. In: 2012 International Conference on Information and Computer Networks, vol. 27, pp. 176–180 (2012)
Zachary, W.: An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research 33(4), 452–473 (1977)
Lusseau, D.: The Emergent Properties of a Dolphin Social Network. Proceedings of the Royal Society B: Biological Sciences 270, 186–188 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, S., Feng, C., Hu, MS., Jia, ZJ. (2014). Community Detection Method of Complex Network Based on ACO Pheromone of TSP. In: Huang, DS., Jo, KH., Wang, L. (eds) Intelligent Computing Methodologies. ICIC 2014. Lecture Notes in Computer Science(), vol 8589. Springer, Cham. https://doi.org/10.1007/978-3-319-09339-0_76
Download citation
DOI: https://doi.org/10.1007/978-3-319-09339-0_76
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09338-3
Online ISBN: 978-3-319-09339-0
eBook Packages: Computer ScienceComputer Science (R0)