A Genetic Algorithm for Identifying Overlapping Communities in Social Networks Using an Optimized Search Space

Brian  Dickinson; Benjamin  Valyou; Wei  Hu

doi:10.4236/sn.2013.24019

Brian Dickinson, Benjamin Valyou, Wei Hu^*

Abstract: There are currently many approaches to identify the community structure of a network, but relatively few specific to detect overlapping community structures. Likewise, there are few networks with ground truth overlapping nodes. For this reason,we introduce a new network, Pilgrim, with known overlapping nodes, and a new genetic algorithm for detecting such nodes. Pilgrim is comprised of a variety of structures including two communities with dense overlap,which is common in real social structures. This study initially explores the potential of the community detection algorithm LabelRank for consistent overlap detection; however, the deterministic nature of this algorithm restricts it to very few candidate solutions. Therefore, we propose a genetic algorithm using a restricted edge-based clustering technique to detect overlapping communities by maximizing an efficient overlapping modularity function. The proposed restriction to the edge-based representation precludes the possibility of disjoint communities, thereby, dramatically reducing the search space and decreasing the number of generations required to produce an optimal solution. A tunable parameterr allows the strictness of the definition of overlap to be adjusted allowing for refinement in the number of identified overlapping nodes. Our method, tested on several real social networks, yields results comparable to the most effective overlapping community detection algorithms to date.

Keywords: Overlapping Community Detection; Genetic Algorithm; Social Networks

Cite this paper: Dickinson, B. , Valyou, B. and Hu, W. (2013) A Genetic Algorithm for Identifying Overlapping Communities in Social Networks Using an Optimized Search Space. Social Networking, 2, 193-201. doi: 10.4236/sn.2013.24019.

References

[1] J. Xie, B. K. Szymanski and X. Liu, “SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process” Proceedings of Data Mining Technologies for Computational Collective Intelligence Workshop at ICDM, Vancouver, 2011, pp. 344-349.

[2] S. Gregory, “Finding Overlapping Communities in Networks by Label Propagation,” New Journal of Physics, Vol. 12, 2010, Article ID: 103018. http://dx.doi.org/10.1088/1367-2630/12/10/103018

[3] C. Lee, F. Reid, A. McDaid and N. Hurley, “Detecting Highly Overlapping Community Structure by Greedy Clique Expansion,” eprint arXiv, 2010.

[4] A. Lancichinetti, F. Radicchi and J. Ramasco, “Finding Statistically Significant Communities in Networks”, PLoS One, Vol. 6, No. 4, 2011, p. e18961. http://dx.doi.org/10.1371/journal.pone.0018961

[5] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, Vol. 33, No. 4, 1977, pp. 452-473.

[6] D. E. Knuth, “The Stanford Graph Base: A Platform for Combinatorial Computing,” Addison-Wesley Reading, Boston, 1993.

[7] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten and S. M. Dawson, “The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations,” Behavioral Ecology and Sociobiology, Vol. 54, No. 4, 2003, pp. 396-405. http://dx.doi.org/10.1007/s00265-003-0651-y

[8] M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” Proceedings of the National Academy of Sciences of USA, Vol. 99, No. 12, 2002, pp. 7821-7826.

[9] P. Gleiser and L. Danon, “Community Structure in Jazz,” Advanced Complex Systems, Vol. 6, No. 4, 2003, p. 565. http://dx.doi.org/10.1142/S0219525903001067

[10] M. E. J. Newman, “Finding and Evaluating Community Structure in Networks,” Physical Review E, Vol. 69, No. 2, 2004, p. 026113.

[11] H. Shen, X. Cheng, K. Cai and M. B. Hu, “Detect Over- lapping and Hierarchical Community Structure in Net- works,” Physica A, Vol. 388, No. 8, 2009, pp. 1706-1712. http://dx.doi.org/10.1016/j.physa.2008.12.021

[12] V. Nicosia, G. Mangioni, V. Carchiolo and M. Malgeri, “Extending the definition of modularity to directed graphs with overlapping communities,” Journal of Statistical Mechanics, Vol. 2009, 2009, Article ID: P03024. http://dx.doi.org/10.1088/1742-5468/2009/03/P03024

[13] J. Xie and B. K. Szymanski, “LabelRank: A Stabalized Label Propagation Algorithm for Community Detection in Networks”, Proceedings of IEEE Network Science Workshop, West Point, 2013, pp. 138-143.

[14] Y. Cai, C. Shi, Y. Dong, Q. Ke and B. Wu, “A Novel Genetic Algorithm for Overlapping Community Detection”, 7th International Conference Advanced Data Mining and Applications, Vol. 7120, December 2011, pp. 97-108. http://dx.doi.org/10.1007/978-3-642-25853-4_8

[15] C. Pizzuit, “A Multi-objective Genetic Algorithm for Community Detection in Networks,” 21st International Conference on Tools with Artificial Intelligence, Newark, 2-4 November 2009, pp. 379-386. http://dx.doi.org/10.1109/ICTAI.2009.58

[16] J. Xie, S. Kelley and B. Szymanski, “Overlapping Community Detection in Networks: The State of the Art and Comparative Study,” ACM Computing Surveys, Vol. 45, No. 4, 2013, pp. 1-35. http://dx.doi.org/10.1145/2501654.2501657