An Information-Theoretic Approach for Detecting Community Structure Based on Network Representation
Source abstract
Abstract
Community structure is a network characteristic where nodes can be naturally divided into densely connected groups. Community structures are ubiquitous in social, biological, and technological networks. Revealing community structure in the network helps in the understanding of the topological associations and interactions of elements in the network, as well as helping to mine their potential information. However, this has been proven to be a difficult challenge. On the one hand, this is because there is no unified definition of the quality of a community; on the other hand, due to the complexity of the network, it is impossible to traverse all the possibilities of community partitions to find the best one. Aiming at performing high-accuracy community detection, an information-theoretic approach AMI-NRL was proposed. The approach first constructs a community evolution process based on the representation of the target network, then finds the most stable community structure during the evolution using an average-mutual-information-based criterion. The experiments show that the approach can effectively detect community structures on real-world datasets and synthetic datasets.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Complex Network Analysis Techniques · Opinion Dynamics and Social Influence · Mental Health Research Topics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Software Engineering, South China University of Technology, Guangzhou 510006, China
References (36)
Show source-provided references
1. Fortunato, S., and Castellano, C. (2007). Community structure in graphs. arXiv.
2. Karataş, A., and Şahin, S. (2018, January 3–4). Application areas of community detection: A review. Proceedings of the 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism (IBIGDELFT), Ankara, Turkey.10.1109/IBIGDELFT.2018.8625349 ↗
3. Modularity and community structure in networks10.1073/pnas.0601602103 ↗
4. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks10.1088/1367-2630/11/3/033015 ↗
5. A unified framework for community detection and network representation learning10.1109/TKDE.2018.2852958 ↗
6. Cavallari, S., Zheng, V.W., Cai, H., Chang, K.C., and Cambria, E. (2017, January 6–10). Learning community embedding with community detection and node embedding on graphs. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, Singapore.10.1145/3132847.3132925 ↗
7. A New Metric for Quality of Network Community Structure
8. Maps of Random Walks on Complex Networks Reveal Community Structure10.1073/pnas.0706851105 ↗
9. Lambiotte, R., Delvenne, J.C., and Barahona, M. (2008). Laplacian dynamics and multiscale modular structure in networks. arXiv.
10. Fast Algorithm for Detecting Community Structure in Networks10.1103/PhysRevE.69.066133 ↗
11. Finding community structure in very large networks10.1103/PhysRevE.70.066111 ↗
12. Fast unfolding of communities in large networks10.1088/1742-5468/2008/10/P10008 ↗
13. Finding Overlapping Communities in Networks by Label Propagation10.1088/1367-2630/12/10/103018 ↗
14. A Semi-Synchronous Label Propagation Algorithm with Constraints for Community Detection in Complex Networks10.1038/srep45836 ↗
15. Lee, C., Reid, F., McDaid, A., and Hurley, N. (2010, January 4–8). Detecting highly overlapping community structure by greedy clique expansion. Proceedings of the 2010, 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010), Anchorage, AK, USA.
16. An Information-theoretic Framework for Resolving Community Structure in Complex Networks10.1073/pnas.0611034104 ↗
17. A novel clonal selection algorithm for community detection in complex networks10.1111/coin.12031 ↗
18. An Algorithm Based on Positive and Negative Links for Community Detection in Signed Networks10.1038/s41598-017-11463-y ↗
19. Li, P.Z., Huang, L., Wang, C.D., Zhang, L., Zhang, X., and Pan, L. (2019, January 4–8). EdMot: An edge enhancement approach for motif-aware community detection. Proceedings of the 2019, 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.10.1145/3292500.3330882 ↗
20. Community Preserving Network Embedding Based on Memetic Algorithm
21. Perozzi, B., Al-Rfou, R., and Skiena, S. (2014, January 24–27). Deepwalk: Online learning of social representations. Proceedings of the 2014, 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.10.1145/2623330.2623732 ↗
22. Grover, A., and Leskovec, J. (2016, January 13–17). Node2vec: Scalable feature learning for networks. Proceedings of the 2016, 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, San Francisco, CA, USA.10.1145/2939672.2939754 ↗
23. Perozzi, B., Kulkarni, V., Chen, H., and Skiena, S. (August, January 31). Don’t Walk, Skip! Online learning of multi-scale network embeddings. Proceedings of the 2017, 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Sydney, Australia.10.1145/3110025.3110086 ↗
24. Sun, D.L., and Fevotte, C. (2014, January 4–9). Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence. Proceedings of the 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy.10.1109/ICASSP.2014.6854796 ↗
25. Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., and Tang, J. (, January 5–9). Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. Proceedings of the Eleventh ACM International Conference on Web Searchand Data Mining, Los Angeles, CA, USA.
26. GLEE: Geometric Laplacian eigenmap embedding10.1093/comnet/cnaa007 ↗
27. Zhang, Z., Cui, P., Li, H., Wang, X., and Zhu, W. (2018, January 17–20). Billion-scale network embedding with iterative random projection. Proceedings of the 2018 IEEE International Conference on Data Mining (ICDM), Singapore.10.1109/ICDM.2018.00094 ↗
28. Li, J., Wu, L., Guo, R., Liu, C., and Liu, H. (2019, January 27–30). Multi-level network embedding with boosted low-rank matrix approximation. Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Vancouver, BC, Canada.10.1145/3341161.3342864 ↗
29. Donnat, C., Zitnik, M., Hallac, D., and Leskovec, J. (2018, January 19–23). Learning structural node embeddings via diffusion wavelets. Proceedings of the 2018, 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, UK.10.1145/3219819.3220025 ↗
30. Hierarchical grouping to optimize an objective function10.1080/01621459.1963.10500845 ↗
31. An Information Flow Model for Conflict and Fission in Small Groups10.1086/jar.33.4.3629752 ↗
32. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations10.1007/s00265-003-0651-y ↗
33. Adamic, L.A., and Glance, N. (2005, January 21–25). The political blogosphere and the 2004 US Election. Proceedings of the 3rd international workshop on Link discovery, Chicago, IL, USA.10.1145/1134271.1134277 ↗
34. Benchmark Graphs for Testing Community Detection Algorithms10.1103/PhysRevE.78.046110 ↗
35. Comparing Community Structure Identification10.1088/1742-5468/2005/09/P09008 ↗
36. Deng, X., Wang, B., Wu, B., and Yang, S. (2009, January 8–10). Research and evaluation on modularity modeling in community detecting of complex network based on information entropy. Proceedings of the Third IEEE International Conference on Secure Software Integration and Reliability Improvement, Shanghai, China.10.1109/SSIRI.2009.15 ↗