×

zbMATH — the first resource for mathematics

A hybrid artificial immune network for detecting communities in complex networks. (English) Zbl 1358.91085
Summary: One of the challenging problems when studying complex networks is the detection of sub-structures, called communities. Network communities emerge as dense parts, while they may have a few relationships to each other. Indeed, communities are latent among a mass of nodes and edges in a sparse network. This characteristic makes the community detection process more difficult. Among community detection approaches, modularity maximization has attracted much attention in recent years. In this paper, modularity density (D value) has been employed to discover real community structures. Due to the inadequacy of previous mathematical models in finding the correct number of communities, this paper first formulates a mixed integer non-linear program to detect communities without any need of prior knowledge about their number. Moreover, the mathematical models often suffer from NP-Hardness. In order to overcome this limitation, a new hybrid artificial immune network (HAIN) has been proposed in this paper. HAIN aims to use a network’s properties in an efficient way. To do so, this algorithm employs major components of the pure artificial immune network, hybridized with a well-known heuristic, to provide a powerful and parallel search mechanism. The combination of cloning and affinity maturation components, a strong local search routine, and the presence of network suppression and diversity are the main components. The experimental results on artificial and real-world complex networks illustrate that the proposed community detection algorithm provides a useful paradigm for robustly discovering community structures.

MSC:
91D30 Social networks; opinion dynamics
90C27 Combinatorial optimization
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrawal, G; Kempe, D, Modularity-maximizing graph communities via mathematical programming, Eur Phys J B, 66, 409-418, (2008) · Zbl 1188.90262
[2] Amiri B, Hossain L, Crawford JW (2011) An efficient multiobjective evolutionary algorithm for community detection in social networks. In: Evolutionary computation (CEC). IEEE Congress, New Orleans, pp 2193-2199. doi:10.1109/CEC.2011.5949886
[3] Amiri, B; Hossain, L; Crawford, JW; Wigand, RT, Community detection in complex networks: multi-objective enhanced firefly algorithm, Knowl Syst, 46, 1-11, (2013)
[4] Arenas, A; Díaz-Guilera, A; Pérez-Vicente, CJ, Synchronization reveals topological scales in complex networks, Phys Rev Lett, 96, 114102, (2006)
[5] Bagrow, JP; Bollt, EM, Local method for detecting communities, Phys Rev, 72, 046108, (2005)
[6] Bhagyesh, VP; Nataraj, PSV; Bhartiya, S, Global optimization of mixed-integer nonlinear (polynomial) programming problems: the Bernstein polynomial approach, Computing, 94, 325-343, (2012) · Zbl 1236.90084
[7] Bonanno, G; Caldarelli, G; Lillo, F; Mantegna, RN, Topology of correlation-based minimal spanning trees in real and model markets, Phys Rev, 68, 046130, (2003)
[8] Castro LN, Timmis J (2002) Artificial immune systems: a new computational intelligence approach. Springer, Berlin · Zbl 1027.68108
[9] Chang, MS; Hung, LJ; Lin, CR; Su, PC, Finding large k-clubs in undirected graphs, Computing, 95, 739-758, (2013) · Zbl 1310.05195
[10] Cheng Q, Liu Z, Huang J, Zhu C (2012) Hierarchical clustering based on hyper-edge similarity for community detection. In: Web intelligence and intelligent agent technology, IEEE, Macau. doi:10.1109/WI-IAT.2012.9 · Zbl 0661.90031
[11] Donath W, Hoffman A (1973) Lower bounds for the partitioning of graphs. IBM J Res Dev 17(5):420-425. doi:10.1147/rd.175.0420 · Zbl 0259.05112
[12] Everett, MG; Borgatti, SP, Regular equivalence: general theory, J Math Soc, 19, 29-52, (1994) · Zbl 0829.92027
[13] Fiedler, M, Algebraic connectivity of graphs, Czech Math J, 23, 298-305, (1973) · Zbl 0265.05119
[14] Flake, GW; Lawrence, S; Giles, CL; Coetzee, FM, Self-organization and identification of web communities, IEEE Comput, 35, 66-71, (2002)
[15] Fortunato, S; Barthélemy, M, Resolution limit in community detection, Proc Natl Acad Sci USA, 104, 36-41, (2007)
[16] Fortunato, S, Community detection in graphs, Phys Rep, 486, 75-174, (2010)
[17] Freeman, LC, A set of measures of centrality based on betweenness, Sociometry, 40, 35-41, (1977)
[18] Girvan, M; Newman, MEJ, Community structure in social and biological networks, Proc Natl Acad Sci USA, 99, 7821-7826, (2002) · Zbl 1032.91716
[19] Goldberg, AV; Tarjan, RE, A new approach to the maximum flow problem, J ACM, 35, 921-940, (1988) · Zbl 0661.90031
[20] Gong M, Fu B, Jiao L, Du H (2011) Memetic algorithm for community detection in networks. Phys Rev E84. doi:10.1103/PhysRevE.84.056101
[21] Gong M, Cai Q, Li Y, Ma J (2012) An improved memetic algorithm for community detection in complex networks. In: Evolutionary computations (CEC) IEEE congress on Brisbane. doi:10.1109/CEC.2012.6252971 · Zbl 0265.05119
[22] Gong, M; Zhang, LJ; Ma, JJ; Jiao, LC, Community detection in dynamic social networks based on multiobjective immune algorithm, J Comput Sci Technol, 27, 455-467, (2012) · Zbl 1280.68064
[23] Guimerà, R; Sales-Pardo, M; Amaral, LAN, Modularity from fluctuations in random graphs and complex networks, Phys Rev E, 70, 025101, (2004)
[24] Halalai R, Lemnaru C, Potolea R (2010) Distributed community detection in social networks with genetic algorithms. In: Intelligent communication and processing (ICCP), IEEE International Conference on Cluj-Napoca, pp 35-41. doi:10.1109/ICCP.2010.5606467
[25] Handcock MS, Raftery AE, Tantrum JM (2007) Model based clustering for social networks. J R Stat Soc A 170(2):301-354. doi:10.1111/j.1467-985X.2007.00471.x
[26] Hemmecke R, Köppe M, Lee J, Weismantel R (2010) Nonlinear integer programming. In: Jünger M et al (eds) 50 Years of integer programming 1958-2008. Springer, Berlin, pp 561-618 · Zbl 1187.90270
[27] Honghao C, Zuren F, Zhigang R (2013) Community detection using ant colony optimization. In: Evolutionary computation (CEC) IEEE Congress on Cancun. doi:10.1109/CEC.2013.6557944
[28] Hughes BD (1995) Random walks and random environments: random walks, vol 1. Clarendon Press, Oxford · Zbl 0820.60053
[29] Kernighan, BW; Lin, S, An efficient heuristic procedure for partitioning graphs, Bell Syst Tech J, 49, 291-307, (1970) · Zbl 0333.05001
[30] Knuth DE (1993) The Stanford graph base: a platform for combinatorial computing. Addison-Wesley, Reading
[31] Kumpula JM, Saramäki J, Kaski K, Kertész J (2007) Limited resolution and multiresolution methods in complex network community detection. In: Noise and stochastics in complex systems and finance in SPIE Conference Series, vol 6601
[32] Lancichinetti, A; Fortunato, S; Radicchi, F, Benchmark graphs for testing community detection algorithms, Phys l Rev E, 78, 046110, (2008)
[33] Li X, Li D, Wang S, Tao Z (2007) Effective algorithm for detecting community structure in complex networks based on GA and clustering. Proc. Comput. Sci. ICCS, Beijing, China, pp 657-664. doi:10.1007/978-3-540-72586-2_95
[34] Li, Z; Zhang, S; Wang, RS; Zhang, XS; Chen, L, Quantitative function for community detection, Phys Rev E, 77, 036109, (2008)
[35] Li, J; Song, Y, A genetic algorithm for community detection in complex networks, Soft Comput, 17, 925-937, (2013)
[36] Liu, X; Murata, T, Advanced modularity-specialized label propagation algorithm for detecting communities in networks, Phys A Stat Mech Appl, 389, 143-150, (2010)
[37] Liu JX, Zeng J (2010) Community detection based on modularity density and genetic algorithm. In: 2010 International Conference on Computational Aspects of Social Networks (CASoN), pp 29-32. doi:10.1109/CASoN.2010.14
[38] Lorrain, F; White, H, Structural equivalence of individuals in social networks, J Math Sociol, 1, 49-80, (1971)
[39] Lusseau, D; Schneider, K; Boisseau, OJ; Haase, P; Slooten, E; Dawson, SM, The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behav Ecol Sociobiol, 54, 396-405, (2003)
[40] Massen CP, Doye JPK (2005) Identifying communities within energy landscapes. Phys Rev E 71 doi:10.1103/PhysRevE.71.046101 · Zbl 1151.68623
[41] Medus, A; Acuña, G; Dorso, CO, Detection of community structures in networks via global optimization, Phys A Stat Mech Appl, 358, 593-604, (2005)
[42] Mitrović, M; Tadić, B, Spectral and dynamical properties in classes of sparse networks with mesoscopic in homogeneities, Phys Rev E, 80, 026123, (2009)
[43] Nepusz T, Petróczi A, Négyessy L, Bazsó F (2008) Fuzzy communities and the concept of bridgeness in complex networks. Phys Rev E. doi:10.1103/PhysRevE.77.016107
[44] Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E. doi:10.1103/PhysRevE.69.026113
[45] Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E. doi:10.1103/PhysRevE.74.036104 · Zbl 1188.90262
[46] Osman IH, Al-Ayoubi B (2005) MIC Analysis for Comparing Metaheuristics. In: Proceedings of the 6th Meta-heuristics International Conference, Vienna, Austria, August 22-26, pp 725-732
[47] Papadopoulos S, Skusa A, Vakali A, Kompatsiaris Y, Wagner N (2009) Bridge bounding: a local approach for efficient community discovery in complex networks. eprint arXiv:0902.0871
[48] Palla, G; Derényi, I; Farkas, I; Vicsek, T, Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814-818, (2005)
[49] Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E. doi:10.1103/PhysRevE.76.036106
[50] Reichardt J, Bornholdt S (2004) Detecting Fuzzy community structures in complex networks with a Potts model. Phys Rev Lett. doi:10.1103/PhysRevLett.93.218701
[51] Reichardt, J; Bornholdt, S, When are networks truly modular?, Phys D, 224, 20-26, (2006) · Zbl 1130.94026
[52] Rosvall, M; Bergstrom, CT, An information-theoretic framework for resolving community structure in complex networks, Proc Natl Acad Sci USA, 104, 7327-7331, (2007)
[53] Shang R, Bai J, Jiao L, Jin C (2010) Community detection based on modularity and an improved genetic algorithm. Phys A Stat Mech Appl 392(5):1215-1231. doi:10.1016/j.physa.2012.11.003 · Zbl 1032.91716
[54] Shi, C; Yan, Z; Cai, Y; Wu, B, Multi-objective community detection in complex networks, Appl Soft Comput, 12, 850-859, (2012)
[55] Talbi E (2009) Metaheuristics from design to implementation. Wiley, Hoboken · Zbl 1190.90293
[56] Tasgin M, Bingol H (2006) Community detection in complex networks using genetic algorithm. In: ECCS ’06. Proceedings of the European Conference on Complex Systems
[57] Traag VA, Bruggeman J (2009) Community detection in networks with positive and negative links. Phys Rev. doi:10.1103/PhysRevE.80.036115
[58] White, JG; Southgate, E; Thompson, JN; Brenner, S, The structure of the nervous system of the nematode C. elegans (aka “the mind of a worm”), Phil Trans R Soc Lond, 314, 1-340, (1986)
[59] Wu FY (1982) The Potts model. Rev Mod Phys 54(1):235-268. doi:10.1103/RevModPhys.54.235
[60] Xu, G; Tsoka, S; Papageorgiou, LG, Finding community structures in complex networks using mixed integer optimization, Eur Phys J B, 60, 231-239, (2007) · Zbl 1189.90027
[61] Yang, B; Liu, J, Discovering global network communities based on local centralities, ACM Trans Web, 2, 1-32, (2008)
[62] Ye Z, Hu S, Yu J (2008) Adaptive clustering algorithm for community detection in complex networks. Phys Rev. doi:10.1103/PhysRevE.78.046115 · Zbl 1130.94026
[63] Yuruk N, Mete M, Xu X, Schweiger TAJ (2007) A divisive hierarchical structural clustering algorithm for networks. In: Data mining workshops, ICDM, Omaha, pp 441-448. doi:10.1109/ICDMW.2007.73 · Zbl 1236.90084
[64] Zachary, WW, An information flow model for conflict and fission in small groups, J Anthropol Res, 33, 452-473, (1977)
[65] Zanghi, H; Ambroise, C; Miele, V, Fast online graph clustering via Erdös-Rényi mixture, Pattern Recognit, 41, 3592-3599, (2008) · Zbl 1151.68623
[66] Zhang XS, Wang RS (2008) Optimization analysis of modularity measures for network community detection. The Second International Symposium on Optimization and System Biology (OSB’08). Lijiang, China
[67] Zhou H (2003) Network landscape from a Brownian particle’s perspective. Phys Rev. doi:10.1103/PhysRevE.67.041908
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.