Detecting Overlapping Communities in Social Networks using Deep Learning

Document Type : Original Article

Authors

Department of Computer Engineering, Shahrood University of Technology, Shahrood, Iran.

Abstract

In network analysis, a community is typically considered of as a group of nodes with a great density of edges among themselves and a low density of edges relative to other network parts. Detecting a community structure is important in any network analysis task, especially for revealing patterns between specified nodes. There is a variety of approaches presented in the literature for overlapping and disjoint detection of community in networks. In recent years, many researchers have concentrated on feature learning and network embedding methods for node clustering. These methods map the network into a lower-dimensional representation space. We propose a model in this research for learning graph representation using deep neural networks. In this method, a nonlinear embedding of the original graph is fed to stacked auto-encoders for learning the model. Then an overlapping clustering algorithm is performed to obtain overlapping communities. The effectiveness of the proposed model is investigated by conducting experiments on standard benchmarks and real-world datasets of varying sizes. Empirical results exhibit that the presented method outperforms some popular community detection methods.

Keywords

References

1. Huang, F., Li, X., Zhang, S., Zhang, J., Chen, J. and Zhai, Z.,
"Overlapping community detection for multimedia social
networks", IEEE Transactions on Multimedia,  Vol. 1, No. 99,
(2017), 1-3. 
2. Mortazavi, R. and Erfani, S., "An effective method for utility
preserving social network graph anonymization based on
mathematical modeling", International Journal of Engineering,
Transactions A: Basics,  Vol. 31, No. 10, (2018), 1624-1632. 
3. Fortunato, S. and Hric, D., "Community detection in networks: A
user guide", Physics Reports,  Vol. 659, (2016), 1-44. 
4. Chintalapudi, S.R. and Prasad, M.K., "Mining overlapping
communities in real-world networks based on extended
modularity gain", International Journal of EngineeringTransactions A: Basics, Vol. 30, No. 4, (2017), 486-492.
5. Yang, S., Yang, X., Zhang, C. and Spyrou, E., "Using social
network theory for modeling human mobility", IEEE Network, 
Vol. 24, No. 5, (2010), 6-13. 
6. 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. 
7. 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. 
8. Coscia, M., Giannotti, F. and Pedreschi, D., "A classification for
community discovery methods in complex networks", Statistical
Analysis and Data Mining,  Vol. 4, No. 5, (2011), 512-546. 
9. Clauset, A., Newman, M.E. and Moore, C., "Finding community
structure in very large networks", Physical review E,  Vol. 70,
No. 6, (2004), 066111. 
10. Chen, M., Kuzmin, K. and Szymanski, B.K., "Extension of
modularity density for overlapping community structure", in
IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM)., (2014), 856-863. 
11. Girvan, M. and Newman, M.E., "Community structure in social
and biological networks", Proceedings of the National Academy
of Sciences,  Vol. 99, No. 12, (2002), 7821-7826. 
12. Gregory, S., "An algorithm to find overlapping community
structure in networks", in European Conference on Principles of 
Data Mining and Knowledge Discovery, Springer., (2007), 91102.
13. Raghavan, U.N., Albert, R. and Kumara, S., "Near linear time
algorithm to detect community structures in large-scale
networks", Physical Review E,  Vol. 76, No. 3, (2007), 036106. 
14. Gregory, S., "Finding overlapping communities in networks by
label propagation", New Journal of Physics,  Vol. 12, No. 10,
(2010), 103018. 
15. 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. 
16. 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. 
17. Lee, C., Reid, F., McDaid, A. and Hurley, N., "Detecting highly
overlapping community structure by greedy clique expansion",
the 4
th
 Workshop on Social Network Mining and Analysis (2010),
33-42. . 
18. Evans, T. and Lambiotte, R., "Line graphs, link partitions, and
overlapping communities", Physical Review E,  Vol. 80, No. 1,
(2009), 016105. 
19. Goyal, P. and Ferrara, E., "Graph embedding techniques,
applications, and performance: A survey", Knowledge-Based
Systems,  Vol. 151, (2018), 78-94. 
20. Cao, S., Lu, W. and Xu, Q., "Grarep: Learning graph
representations with global structural information", in
Proceedings of the 24th ACM International on Conference on
Information and Knowledge Management, ACM., (2015), 891900.
21. Perozzi, B., Al-Rfou, R. and Skiena, S., "Deepwalk: Online
learning of social representations", in Proceedings of the 20th
ACM SIGKDD international conference on Knowledge
discovery and data mining, ACM., (2014), 701-710. 
22. Khatami, A., Babaie, M., Tizhoosh, H., Nazari, A., Khosravi, A.
and Nahavandi, S., "A radon-based convolutional neural network
for medical image retrieval", International Journal of
Engineering-Transactions C: Aspects,  Vol. 31, No. 6, (2018),
910-915. 
23. LeCun, Y., Bengio, Y. and Hinton, G., "Deep learning", Nature, 
Vol. 521, No. 7553, (2015), 436-444. 
24. Mikolov, T., Chen, K., Corrado, G. and Dean, J., "Efficient
estimation of word representations in vector space", arXiv
preprint arXiv:1301.3781,  (2013). 
25. Pennington, J., Socher, R. and Manning, C., "Glove: Global
vectors for word representation", in Proceedings of the 2014
conference on empirical methods in natural language processing
(EMNLP)., (2014), 1532-1543. 
26. Levy, O. and Goldberg, Y., "Neural word embedding as implicit
matrix factorization", in Advances in neural information
processing systems., (2014), 2177-2185. 
27. Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S. and Dean, J.,
"Distributed representations of words and phrases and their
compositionality", in Advances in Neural Information Processing
Systems, (2013), 3111-3119. 
28. Tian, F., Gao, B., Cui, Q., Chen, E. and Liu, T.-Y., "Learning
deep representations for graph clustering", in AAAI., (2014),
1293-1299. 
29. Baldi, P., "Autoencoders, unsupervised learning, and deep
architectures", in Proceedings of ICML Workshop on
Unsupervised and Transfer Learning., (2012), 37-49. 
30. Cleuziou, G., "An extended version of the k-means method for
overlapping clustering", in Pattern Recognition, 2008. ICPR
2008. 19th International Conference on, IEEE,(2008), 1-4. 
31. Kunegis, J., "Konect: The koblenz network collection", in
Proceedings of the 22nd International Conference on World Wide
Web, ACMe, (2013), 1343-1350. 
32. Barabási, A.-L., "Scale-free networks: A decade and beyond",
Science,  Vol. 325, No. 5939, (2009), 412-413. 
33. Lancichinetti, A. and Fortunato, S., "Benchmarks for testing
community detection algorithms on directed and weighted graphs
with overlapping communities", Physical Review E,  Vol. 80, No.
1, (2009), 016118. 
34. Danon, L., Diaz-Guilera, A., Duch, J. and Arenas, A.,
"Comparing community structure identification", Journal of
Statistical Mechanics: Theory and Experiment, No. 09, (2005),
P09008. 
35. Leskovec, J., Lang, K.J. and Mahoney, M., "Empirical
comparison of algorithms for network community detection", in
Proceedings of the 19th international conference on World wide
web, ACM,(2010), 631-640. 

 
 
 
 
 
International Journal of Engineering
Volume 33, Issue 3
TRANSACTIONS C: Aspects
March 2020
Pages 366-376

Files

Cited by

Share

How to cite

Statistics