Community detection through vector-label propagation algorithms. (May 2022) - Fang, Wenyi; Wang, Xin; Liu, Longzhao; Wu, Zhaole; Tang, Shaoting; Zheng, Zhiming
Abstract: Community detection is a fundamental and important problem in network science, as community structures often reveal both topological and functional relationships between different components of the complex system. In this paper, we first propose a gradient descent framework of modularity optimization called vector-label propagation algorithm (VLPA), where a node is associated with a vector of continuous community labels instead of one label. Retaining weak structural information in vector-label, VLPA outperforms some well-known community detection methods, and particularly improves the performance in networks with weak community structures. Further, we incorporate stochastic gradient strategies into VLPA to avoid stuck in the local optima, leading to the stochastic vector-label propagation algorithm (sVLPA). We show that sVLPA performs better than Louvain Method, a widely used community detection algorithm, on both artificial benchmarks and real-world networks. Our theoretical scheme based on vector-label propagation can be directly applied to high-dimensional networks where each node has multiple features, and can also be used for optimizing other partition measures such as modularity with resolution parameters. Highlights: We propose a gradient descent frame of modularity optimization to detect communities. Our vector-label propagation algorithm (VLPA) retains weak structural information. VLPA obtains better performance particularly when the community structure is weak. sVLPA is further proposed via equipping stochastic strategies to avoid local optima. sVLPA outperforms the classic Louvain Method on both artificial and real networks.