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.
- U. Brandes, M. Gaertler, and D. Wagner. Experiments on graph clustering algorithms. In Algorithms: ESA 2003, 11th Annual European Symposium, pages 568--579, 2003.Google ScholarCross Ref
- Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- S. Lozano, J. Duch, and A. Arenas. Analysis of large social datasets by community detection. European Physical Journal ST, 143:257--259, 2007.Google ScholarCross Ref
- M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69:026113, 2004.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarCross Ref
Index Terms
Community detection in social networks with genetic algorithms
Recommendations
A Data Mining Based Genetic Algorithm
SEUS-WCCIA '06: Proceedings of the The Fourth IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, and the Second International Workshop on Collaborative Computing, Integration, and Assurance (SEUS-WCCIA'06)Genetic algorithms (GAs) are considered as a global search approach for optimization problems. Through the proper evaluation strategy, the best "chromosome" can be found from the numerous genetic combinations. Although the GA operations do provide the ...
Mesoscopic analysis of networks with genetic algorithms
The detection of communities is an important problem, intensively investigated in recent years, to uncover the complex interconnections hidden in networks. In this paper a genetic based approach to discover communities in networks is proposed. The ...
An improved genetic algorithm with conditional genetic operators and its application to set-covering problem
The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
Comments