International Science Index


A Model Based Metaheuristic for Hybrid Hierarchical Community Structure in Social Networks

Abstract:In recent years, the study of community detection in social networks has received great attention. The hierarchical structure of the network leads to the emergence of the convergence to a locally optimal community structure. In this paper, we aim to avoid this local optimum in the introduced hybrid hierarchical method. To achieve this purpose, we present an objective function where we incorporate the value of structural and semantic similarity based modularity and a metaheuristic namely bees colonies algorithm to optimize our objective function on both hierarchical level divisive and agglomerative. In order to assess the efficiency and the accuracy of the introduced hybrid bee colony model, we perform an extensive experimental evaluation on both synthetic and real networks.
[1] Benjamin H. Good, Y. A., and Aaron C. Performance of modularity maximization in practical contexts. Phys. Rev. E, 81:046106, Apr 2010.
[2] Clauset, M. E. J. Newman, and C. Moore Finding community structure in very large networks. , In Phys. Rev. E 70, 066111, 2004.
[4] Newman M. E. Jand Girvan M. Finding and evaluating community structure in networks. Phys. Rev. E, 69(2):026113, February 2004.
[5] Fortunato, S., Physics Reports, 486(3-5), pp. 75 - 174. 2010.
[6] Guimera, R., M. Sales-Pardo, and L. A. N. Amaral Phys. Rev. E 70(2), 025101 (R) 2004.
[7] Guimera, R., and L. A. N. Amaral Nature 433, 895. 2005.
[8] Boettcher, S., and A. G. Percus Phys. Rev. Lett. 86, 5211, 2001.
[9] Duch, J., and A. Arenas, Phys. Rev. E 72(2), 027104, 2005.
[10] Qi G. J., Aggarwal C. C., and Huang T., Community Detection with Edge Content in Social Media Networks IEEE 28th International Conference on Data Engineering, 2012.
[11] Chira C., Gog A., and Iclanzan D. Evolutionary Detection of Community Structures in Complex Networks: a New Fitness Function WCCI 2012 IEEE World Congress on Computational Intelligence, Brisbane, Australia, June, 10-15, 2012.
[12] Kulathumani, A. Arora, Sridharan M., and Demirbas M., Trail: A Distance-Sensitive Sensor Network Service for Distributed Object Tracking ACM Transactions on Sensor Networks, vol. 5, no. 2, article 15, pp. 140, Mar. 2009.
[13] Pothen H. Path Selection for Social Network Evolution Map Formation of Start-up Enterprises Technical Report, Norfolk, VA, USA, 1997.
[14] Huatao P. Partitioning Algorithms with Applications to Scientific Computing International Conference on Computer and Communication Technologies in Agriculture Engineering, IEEE, pp. 4750, 2010.
[15] Duch, J., and Arenas A., Physical Review E, 72(2), 027104. 2005.
[16] Danon, L., A. Daz-Guilera, J. Duch, and A. Arenas Physical Review E, 72(2), 027104. 2005.
[17] Wang, G., Shen Y., and Ouyang M., Comput. Math. Appl. 55(12), 2746, 2008.
[18] Richardson, T., Mucha P. J., and Porter M. A. Phys. Rev. E 80(3), 036111 , 2009.
[19] Ehrgott M. and Gandibleux X. Multiobjective combinatorial optimization , In M. Ehrgott and X. Gandibleux, editors, Multiple Criteria Optimization State of the Art Annotated Bibliographic Surveys, volume 52, pages 369,444. Kluwer Academic Publishers, Boston, MA, 2002.
[20] Leskovec, J., Lang, K. J., and Mahoney, M. Empirical comparison of algorithms for network community detection , In WWW, 631640, 2010.
[21] Fasmer E. E. Community Detection in Social Networks Thesis University of Bergin,April2015.
[22] David L. and Jon K. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7): 10191031, 2007.
[23] Feng, Xiaowei, Nurcan, Y., and Thomas A. J., S. A Novel Similarity-based Modularity Function for Graph Partitioning Proceeding DaWaK’07 Proceedings of the 9th international conference on Data Warehousing and Knowledge Discovery, Pages 385-396, Regensburg, Germany September 03 - 07, 2007.
[24] Toujani R. and Akaichi J. Machine Learning and Metaheuristic For sentiment anal- ysis in social networks Metaheuristic Internatianal Conference MIC’15, Morrocco, 2015.
[25] Sagayam R. and Akilandeswari K. Comparison of Ant Colony and Bee Colony Optimization for Spam Host Detection International Journal of Engineering Research and Development eISSN: 2278-067X, pISSN: 2278-800X, Volume 4, Issue 8, PP. 26-32, November 2012.
[26] San FortunatoBenchmark graphs to test community detection algorithms., Date of access to the site: February 2016.
[27] Christos, G., Fragkiskos D. M., Dimitrios M. T. and Michalis, V. CORECLUSTER: A Degeneracy Based Graph Clustering Framework. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.
[28] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452473, 1977.