Community detection in social networks with genetic algorithms

ABSTRACT

A new genetic algorithm to detect communities in social networks is presented. The algorithm uses a fitness function able to identify groups of nodes in the network having dense intra-connections, and sparse inter-connections. The variation operators employed are suitably adapted to take into account the actual links among the nodes. These modified operators makes the method efficient because the space of possible solutions is sensibly reduced. Experiments on a real life network show the capability of the method to successfully identify the network structure.

REFERENCES

• 1: U. Brandes, M. Gaertler, and D. Wagner. Experiments on graph clustering algorithms. In Algorithms: ESA 2003, 11th Annual European Symposium, pages 568--579, 2003.
• 2: Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.
• 3: L. Danon, J. Duch, A. Arenas, and A. Díaz-Guilera. Community structure identification. Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science,World Scientific,, pages 93--113, 2007.
• 4: 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.
• 5: S. Lozano, J. Duch, and A. Arenas. Analysis of large social datasets by community detection. European Physical Journal ST, 143:257--259, 2007.
• 6: M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.
• 7: 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.
• 8: Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proc. Natl. Acad.Sci. USA (PNAS'04), 101(9):2658--2663, 2004.

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, data mining, genetic algorithm, social networks