Overlapping Community Detection using Local Seed Expansion
Keywords:
Community Detection, Overlapping Community Detection, Local ExpansionAbstract
Communities are usually groups of vertices which have higher probability of being connected to each other than to members of other groups. Community detection in complex networks is one of the most popular topics in social network analysis. While in real networks, a person can be overlapped in multiple communities such as family, friends and colleagues, so overlapping community detection attracts more and more attention. Detecting communities from the local structural information of a small number of seed nodes is the successful methods for overlapping community detection. In this work, we propose an overlapping community detection algorithm using local seed expansion approach. Our local seed expansion algorithm selects the nodes with the highest degree as seed nodes and then locally expand these seeds with their entire vertex neighborhood into overlapping communities using Personalized PageRank algorithm. We use F1_score( node level detection ) and NMI( community level detection ) measures to assess the performances of the proposed algorithm by comparing the proposed algorithm’s detected communities with ground_truth communities on many real_world networks. Experimental results show that our algorithm outperforms over other overlapping community detection methods in terms of accuracy and quality of overlapped communities.
References
. Y. Liu, L. Nie, L. Han, L. Zhang, A. D. S. Rosenblum. Action2activity: recognizing complex activities from sensor data, in Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, 2015, pp. 1617–1623.
. Y. Liu, Y. Zheng, Y. Liang, S. Liu, A. D. S. Rosenblum. Urban water quality prediction based on multi-task multi-view learning. in Proceedings of the International Joint Conference on Artificial Intelligence, 2016.
. X. Wang, L. Nie, X. Song, D. Zhang, T.S. Chua. Unifying virtual and physical worlds: Learning towards local and global consistency. ACM Transactions on Information Systems, 36 (1) (2017) 1-26. https://doi.org/10.1145/3052774
. S. Fortunato. 2010. Community detection in graphs. Physics Reports 486, 3–5 (2010), 75–174.
. Chakraborty, S. Ghosh, and N. Ganguly. 2012. Detecting overlapping communities in folksonomies. In 23rd ACM Conference on Hypertext and Social Media. 213–218.
. J. Xie, S. Kelley, and B. K. Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Computing Surveys 45, 4, Article 43 (Aug. 2013), 35 pages.
. M. F. Balcan and Y. Liang. 2013. Modeling and detecting community hierarchies. In Proceedings of the 2nd International Conference on Similarity-Based Pattern Recognition (SIMBAD’13). Springer-Verlag, Berlin,160–175.
. X.Wang et al.: “Overlapping Community Detection Based on Structural Centrality in Complex Networks”, in IEEE Access • November 2017, DOI: 10.1109/ACCESS.2017.2769484
. G. Palla, I. Der_enyi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, pp. 814–818, 2005.
. Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, “Link communities reveal multiscale complexity in networks,” Nature, vol. 466, pp. 761–764, 2010.
. S. Zhang, R.-S. Wang, and X.-S. Zhang, “Identification of overlapping community structure in complex networks using fuzzy C-means clustering,” Physica A, vol. 374, no. 1, pp. 483–490, 2007.
. R. S. Burt, Structural Holes: The Social Structure of Competition. Cambridge, MA, US: Harvard Univ. Press, 1995.
. B. S. Rees and K. B. Gallagher, “Overlapping community detection by collective friendship group inference,” in Proc. Int. Conf. Adv. Social Netw. Anal. Mining, 2010, pp. 375–379.
. M. Coscia, G. Rossetti, F. Giannotti, and D. Pedreschi, “Demon: A Local-first discovery method for overlapping communities,” in Proc. 1 8th ACM Int. Conf. Knowl. Discovery Data Mining, 2012, pp. 615–623.
. F. Moradi, T. Olovsson and P. Tsigas, “ A local seed selection algorithm for overlapping community detection,”, Proc, 2014 IEEE/ACM I nternational Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014),Beijing, China, 2014, pp. 1-8, doi:10. 1109/ASONAM.2014.6921552.
. J.J. Whang. D.F. Gleich and I.S. Dhillon, “Overlapping community detection using seed set expansion,’ Proc. 22nd ACM International Conference on Information and Knowledge Management (CIKM’13) ,San Francisco, CA, USA, 2013, pp. 2099-2108, doi:10.1145/2505515.2505535.
. R. Andersen, F. Chuang and K. Lang, “Local graph partitioning using PageRank vectors,” Proc. 47th Annual IEEE Symposium on Foundations of Computer Science( FOCS’ 06 ), Berkeley, CA, USA, 2006, pp. 475-486, doi: 10.1109/ FOCS. 2006.44.
. J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground truth,” Proc. 12th IEEE International Conference on Data Mining (ICDM 2012), Brussels, Belgium, 2012, pp. 745-754, doi:10.1109/ICDM. 2012.138.
. D.F. Gleich, C.Seshadhri and Vertex neighborhoods, “low conductance cuts, and good seeds for local community methods, “Proc, 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’ 12), Beijing, China, 2012, pp. 597-605, doi:10.1145/2339530.2339628.
. L.S. Dhillon, Y. Guan and B. Kulis, “Weighted graph cuts without eigenvectors: A multilevel approach,” IEEE Transactions on Pattern Analaysis and Machine Intelligence (PAMI), vol, 29(11), 2007, pp. 1944-1957, doi:10.1109/TPAMI. 2007.1115.
. G.Pan, W.Zhang, Z.Wu and S.Li , “ Online Community Detection for Large Complex Networks”, July 2014 | Volume 9 | Issue 7 | e102799.
. R.K.Behera, D.Naik, “Centrality Approach for Community Detection in Large Scale Network”, ACM COMPUTE ’16, October 21-23, 2016.
. R. Andersen and K. Lang. Communities from seed sets. In Proceedings of the 15th conference on World Wide Web, 2006.
. A.Lancichinetti, S.Fortunato, J. Kertesz, “Detecting the overlapping and hierarchical community structure in complex networks,” New Journal of Physics, 2009, 11(3):033015
. Q.Cai, L. Ma, and M. Gong, “A survey on network community detection based on evolutionary computation,” Int. J. Bio-Inspired Comput.,l vol.8, no.2, pp. 84-98,2014.
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers with this journal agree to the following terms.
