Overlapping Community Detection using Local Seed Expansion
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.
. 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.
Copyright (c) 2020 International Journal of Computer (IJC)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Authors who submit papers with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
- By submitting the processing fee, it is understood that the author has agreed to our terms and conditions which may change from time to time without any notice.
- It should be clear for authors that the Editor In Chief is responsible for the final decision about the submitted papers; have the right to accept\reject any paper. The Editor In Chief will choose any option from the following to review the submitted papers:A. send the paper to two reviewers, if the results were negative by one reviewer and positive by the other one; then the editor may send the paper for third reviewer or he take immediately the final decision by accepting\rejecting the paper. The Editor In Chief will ask the selected reviewers to present the results within 7 working days, if they were unable to complete the review within the agreed period then the editor have the right to resend the papers for new reviewers using the same procedure. If the Editor In Chief was not able to find suitable reviewers for certain papers then he have the right to reject the paper.
- Author will take the responsibility what so ever if any copyright infringement or any other violation of any law is done by publishing the research work by the author
- Before publishing, author must check whether this journal is accepted by his employer, or any authority he intends to submit his research work. we will not be responsible in this matter.
- If at any time, due to any legal reason, if the journal stops accepting manuscripts or could not publish already accepted manuscripts, we will have the right to cancel all or any one of the manuscripts without any compensation or returning back any kind of processing cost.
- The cost covered in the publication fees is only for online publication of a single manuscript.