Overlapped community detection in complex networks

ABSTRACT

Extracting and understanding community structure in complex networks is one of the most intensively investigated problems in recent years. In this paper we propose a genetic based approach to discover overlapping communities. The algorithm optimizes a fitness function able to identify densely connected groups of nodes by employing it on the line graph corresponding to the graph modelling the network. The method generates a division of the network in a number of groups in an unsupervised way. This number is automatically determined by the optimal value of the fitness function. Experiments on synthetic and real life networks show the capability of the method to successfully detect the network structure.

REFERENCES

• 1: Balázs Adamcsek , Gergely Palla , Illés J. Farkas , Imre Derényi , Tamás Vicsek, CFinder: locating cliques and overlapping modules in biological networks, Bioinformatics, v.22 n.8, p.1021-1023, April 2006 [doi>10.1093/bioinformatics/btl039]
• 2: A. Arenas and A. Diaz-Guilera. Synchronization and modularity in complex networks. European Physical Journal ST, 143:19--25, 2007.
• 3: Jeffrey Baumes, Mark K. Goldberg, Mukkai S. Krishnamoorthy, Malik Magdon-Ismail, and Nathan Preston. Efficient identification of overlapping communities. In IEEE International Conference on Intelligence and Security Informatics, ISI'05, pages 27--36, 2005.
• 4: S. P. Borgatti. Netdraw 1.0: Network visualization software. harvard: Analytic technologies. 2002.
• 5: Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.
• 6: L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics, P09008, 2005.
• 7: I. Derenyi, Gergely Palla, and Tamás Vicsek. Clique percolation in random networks. Physical Review Letters, 94(16):160202, 2005.
• 8: Aykut Firat , Sangit Chatterjee , Mustafa Yilmaz, Genetic clustering of social networks using random walks, Computational Statistics & Data Analysis, v.51 n.12, p.6285-6294, August, 2007 [doi>10.1016/j.csda.2007.01.010]
• 9: Santo Fortunato and Claudio Castellano. Community structure in graphs. arXiv:0712.2716v1 {physics.soc-ph}, 2007.
• 10: M. Girvan and M. E. J. Newman. Community structure in social and biological networks. In Proc. National. Academy of Science. USA 99, pages 7821--7826, 2002.
• 11: Steve Gregory, An Algorithm to Find Overlapping Community Structure in Networks, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_12]
• 12: Steve Gregory, A Fast Algorithm to Find Overlapping Communities in Networks, Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, September 15-19, 2008, Antwerp, Belgium [doi>10.1007/978-3-540-87479-9_45]
• 13: Julia Handle and Joshua Knowles. An evolutionary approach to multiobjective clustering. IEEE transactions on Evolutionary Computation, 11(1):56--76, 2007.
• 14: John Hopcroft , Omar Khan , Brian Kulis , Bart Selman, Natural communities in large linked networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956816]
• 15: Andrea Lancichinetti, Santo Fortunato, and János Kertés. Community spectroscopy in complex networks. technical report, 2008.
• 16: Andrea Lancichinetti, Santo Fortunato, and Janos Kertész. Detecting the overlapping and hierarchical community structure of complex networks. arXiv:0802.1281v1 {physics.soc-ph}, 2008.
• 17: Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. New benchmark in community detection. arXiv:0805.4770v2 {physics.soc-ph}, 2008.
• 18: S. Lozano, J. Duch, and A. Arenas. Analysis of large social datasets by community detection. European Physical Journal ST, 143:257--259, 2007.
• 19: D. Lusseau. The emergent properties of dolphin social network. Biology Letters, Proc. R. Soc. London B (suppl.), 2003.
• 20: David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, New York, NY, 2002
• 21: Nobukazu Matake , Tomoyuki Hiroyasu , Mitsunori Miki , Tomoharu Senda, Multiobjective clustering with automatic k-determination for large-scale data, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277126]
• 22: M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, 69:066133, 2004.
• 23: M. E. J. Newman. Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA 103, pages 8577--8582, 2006.
• 24: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.
• 25: Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435:814--818, 2005.
• 26: Y.J. Park and M.S. Song. A genetic algorithm for clustering problems. In Proc. of 3rd Annual Conference on Genetic Algorithms, pages 2--9, 1989.
• 27: J. B. Pereira, A.J. Enright, and C.A. Ouzounis. Detection of functional modules from protein interaction networks. Proteins: Structure, Fuctions, and Bioinformatics, (20):49--57, 2004.
• 28: Clara Pizzuti, GA-Net: A Genetic Algorithm for Community Detection in Social Networks, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_107]
• 29: Filippo Radicchi, Claudio Castellano, Federico Cecconi, VittorioLoreto, and Domenico Parisi. Defining and identifying communities in networks. Proc. Natl. Acad.Sci. USA (PNAS'04), 101(9):2658--2663, 2004.
• 30: Mursel Tasgin and Aluk Bingol. Communities detection in complex networks using genetic algorithms. In Proc. of the European Conference on Complex Systems (ECSS'06), 2006.
• 31: Mursel Tasgin, Amac Herdagdelen, and Aluk Bingol. Communities detection in complex networks using genetic algorithms. oai:arXiv.org:0711.0491v1 {physics.soc-ph}, 2007.
• 32: D. J. Watt. Small worlds. Princeton University Press, 1999.
• 33: W.W Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452--473, 1977.
• 34: Shihua Zhang, Rui--Sheng Wang, and Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Phisica A, 374:483--490, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms

Keywords:
clustering, complex networks, data mining, genetic algorithms