Improved label propagation algorithm for overlapping community detection
- PDF / 550,098 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 237 Views
Improved label propagation algorithm for overlapping community detection Shi Dong1 Received: 25 August 2019 / Accepted: 24 July 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract Community detection plays an important role in the analysis of complex networks. However, overlapping community detection in real networks is still a challenge. To address the problems of pre-input parameters and label redundancy, an improved label propagation algorithm (ILPA) that adopts a method based on the influence factor is proposed in this paper. Theoretical analysis and experimental results on both synthetic and real datasets show that the ILPA detects that the overlapping community has higher accuracy compared to other existing methods. Keywords Overlapping community · Community detection · Label propagation · Complex network Mathematics Subject Classification 05C82 · 68T99 · 68U99
1 Introduction Community detection is one of the most important tasks and tools to mine the information from a network analysis with applications. Given a network, a community is defined to be a set of cohesive nodes that have more connections inside the set than outside. Since a network can be modeled as a graph with vertices and edges, community detection can be thought of as a graph clustering problem where each community corresponds to a cluster in the graph. Discovering the communities in these networks will help these networks to be better understood and developed, while simultaneously helping to provide accurate personalized services. Therefore, community detection has important theoretical significance and practice application for the analysis, function evolution, and prediction of network structures. In many complex networks of the real world, community overlapping is one of the most important characteristics. Previ-
B 1
Shi Dong [email protected] School of Computer Science and Technology, Zhoukou Normal University, Zhoukou 466001, China
123
S. Dong
ous works mainly address the problem by identifying a disjoint community structure, where one node belongs to only one community. However, it is very common that a node belongs to more than one community in real-world networks. Because there exist some defects in the current topology-potential-based community detection methods, the authors propose an improved label propagation algorithm (ILPA) that can detect the overlapping community and a rule considering the influence factor as the metric is applied. When the influence of a node on another node is large, the node to update the label will be considered as a priority. Doing so enables the degree of influence to be used as the parameter for selecting the optimal node in this community. Since the order for updating the node label can affect the detection result of the overlapping community, a suitable updating strategy can optimize the detection accuracy. The paper is structured as follows. Section 2 introduces related work. Section 3 presents the preliminaries. The ILPA method is described in Sect. 4. The experimental re
Data Loading...
