Abstract
Community structure in networks indicates some meaningful groups or organizations in the real world. Various algorithms to detect community in complex networks were proposed. However, problems about how to judge the goodness and performance of algorithms are still open. This paper reviewed and analyzed the related work and algorithms for community detection, hoping to benefit researchers in related field.
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
Similar content being viewed by others
References
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)
Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Qi, X., Tang, W., Wu, Y., et al.: Optimal local community detection in social networks based on density drop of subgraphs. Pattern Recogn. Lett. 36, 46–53 (2014)
Guimera, R., Amaral, L.A.N.: Functional cartography of complex metabolic networks. Nature 433(7028), 895–900 (2005)
Riedy, J., Bader, D. A., Meyerhenke, H.: Scalable multi-threaded community detection in social networks. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), pp. 1619–1628. IEEE (2012)
Ovelgönne, M., Geyer-Schulz, A.: An ensemble learning strategy for graph clustering. Gr. Partitioning Gr. Clustering 588, 187 (2012)
Ma, L., Gong, M., Liu, J., et al.: Multi-level learning based memetic algorithm for community detection. Appl. Soft Comput. 19, 121–133 (2014)
Nascimento, M.C.V., Pitsoulis, L.: Community detection by modularity maximization using GRASP with path relinking. Comput. Oper. Res. 40(12), 3121–3131 (2013)
Palla, G., Derényi, I., Farkas, I., et al.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814–818 (2005)
Xie, J., Kelley, S., Szymanski, B.K.: Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Comput. Surv. (CSUR) 45(4), 43 (2013)
Evans, T.S., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80(1), 016105 (2009)
De Meo, P., Ferrara, E., Fiumara, G., et al.: Enhancing community detection using a network weighting strategy. Inf. Sci. 222, 648–668 (2013)
Lim, S., Ryu, S., Kwon, S., et al.: LinkSCAN*: overlapping community detection using the link-space transformation. In: 2014 IEEE 30th International Conference on Data Engineering (ICDE), pp. 292–303. IEEE (2014)
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)
Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)
Xie, J., Szymanski, B. K., Liu, X.: Slpa: uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW), pp. 344–349. IEEE, (2011)
Newman, M.E.J.: Community detection and graph partitioning. EPL (Europhys. Lett.) 103(2), 28003 (2013)
Arias-Castro, E., Verzelen, N.: Community detection in dense random networks. Ann. Stat. 42(3), 940–969 (2014)
Shi, C., Yan, Z., Shi, Z., et al.: A fast multi-objective evolutionary algorithm based on a tree structure. Appl. Soft Comput. 10(2), 468–480 (2010)
Shi, C., Kong, X., Fu, D., et al.: Multi-label classification based on multi-objective optimization. ACM Trans. Intell. Syst. Technol. (TIST) 5(2), 35 (2014)
Bassett, D.S., Porter, M.A., Wymbs, N.F., et al.: Robust detection of dynamic community structure in networks. Chaos Interdisc. J. Nonlinear Sci. 23(1), 013142 (2013)
Kim, C.M., Kang, I.S., Han, Y.H., et al.: A community detection scheme in delay-tolerant networks. In: Han, Y.-H., Park, D.-S., Jia, W., Yeo, S.-S. (eds.) Ubiquitous Information Technologies and Applications, pp. 745–751. Springer, Heidelburg (2013)
Shi, C., Kong, X., Huang, Y., et al.: HeteSim: a general framework for relevance measure in heterogeneous Networks. IEEE Trans. Knowl. Data Eng. 10, 2479–2492 (2014)
Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, pp. 3. ACM (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jie, Y., Zhishuai, L., Qiu, X. (2015). Community Detection in Complex Networks: Algorithms and Analysis. In: Yueming, L., Xu, W., Xi, Z. (eds) Trustworthy Computing and Services. ISCTCS 2014. Communications in Computer and Information Science, vol 520. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47401-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-662-47401-3_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47400-6
Online ISBN: 978-3-662-47401-3
eBook Packages: Computer ScienceComputer Science (R0)