Mining Overlapping Communities in Real-world Networks Based on Extended Modularity Gain

Authors

Department of CSE, University College of Engineering Kakinada(A), JNTUK, Kakinada, India

Abstract

Detecting communities plays a vital role in studying group level patterns of a social network and it can be helpful in developing several recommendation systems such as movie recommendation, book recommendation, friend recommendation and so on. Most of the community detection algorithms can detect disjoint communities only, but in the real time scenario, a node can be a member of more than one community at the same time, that leads to overlapping communities. A novel approach is proposed to detect such overlapping communities by extending the definition of newman’s modularity for overlapping communities. The proposed algorithm is tested on LFR benchmark networks with overlapping communities and on real-world networks. The performance of the algorithm is evaluated using popular metrics such as ONMI, Omega Index, F-score and Overlap modularity and the results are compared with its competent algorithms. It is observed that extended modularity gain can detect highly modular structures in complex networks with overlapping communities.

Keywords


1.     Harenberg, S., Bello, G., Gjeltema, L., Ranshous, S., Harlalka, J., Seay, R., Padmanabhan, K. and Samatova, N., "Community detection in large‐scale networks: A survey and empirical evaluation", Wiley Interdisciplinary Reviews: Computational Statistics,  Vol. 6, No. 6, (2014), 426-439.

2.     Chintalapudi, S.R. and Prasad, M.K., "A survey on community detection algorithms in large scale real world networks", in Computing for Sustainable Global Development (INDIACom), 2nd International Conference on, IEEE., (2015), 1323-1327.

3.     Chakraborty, T., "Leveraging disjoint communities for detecting overlapping community structure", Journal of Statistical Mechanics: Theory and Experiment,  Vol. 2015, No. 5, (2015), P05017.

4.     Xie, J., Kelley, S. and Szymanski, B.K., "Overlapping community detection in networks: The state-of-the-art and comparative study", Acm Computing Surveys (csur),  Vol. 45, No. 4, (2013), 43-50.

5.     Palla, G., Derényi, I., Farkas, I. and Vicsek, T., "Uncovering the overlapping community structure of complex networks in nature and society", Nature,  Vol. 435, No. 7043, (2005), 814-818.

6.     Gregory, S., "Finding overlapping communities in networks by label propagation", New Journal of Physics,  Vol. 12, No. 10, (2010), 103018.

7.     Xie, J. and Szymanski, B.K., "Towards linear time overlapping community detection in social networks", in Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer., (2012), 25-36.

8.     Newman, M.E. and Girvan, M., "Finding and evaluating community structure in networks", Physical review E,  Vol. 69, No. 2, (2004), 026113.

9.     Leicht, E.A. and Newman, M.E., "Community structure in directed networks", Physical Review Letters,  Vol. 100, No. 11, (2008), 118703.

10.   Meng, K., Liu, G., Hu, Q. and Li, J., "An modularity-based overlapping community structure detecting algorithm", in Advances in Social Networks Analysis and Mining (ASONAM), IEEE/ACM International Conference on, (2014), 113-117.

11.   Lancichinetti, A., Fortunato, S. and Radicchi, F., "Benchmark graphs for testing community detection algorithms", Physical review E,  Vol. 78, No. 4, (2008), 046110.

12.   McDaid, A.F., Greene, D. and Hurley, N., "Normalized mutual information to evaluate overlapping community finding algorithms", arXiv preprint arXiv:1110.2515,  Vol., No., (2011).

13.   Gregory, S., "Fuzzy overlapping communities in networks", Journal of Statistical Mechanics: Theory and Experiment,  Vol. 2011, No. 02, (2011), P02017.

14.   Nicosia, V., Mangioni, G., Carchiolo, V. and Malgeri, M., "Extending the definition of modularity to directed graphs with overlapping communities", Journal of Statistical Mechanics: Theory and Experiment,  Vol. 2009, No. 03, (2009), P03024.