|
Abstract
|
Community structure is one of the most best-known properties of complex networks. Finding
communities help us analyze networks from a mesoscopic viewpoints instead of microscopic or
macroscopic one. It helps to understand behavior grouping. Various community detection algorithms
have been proposed with some shortcomings in time and space complexity, accuracy, or stability. Label
Propagation Algorithm (LPA) is a popular method used for finding communities in an almost-linear
time-consuming process. However, its performance is not satisfactory in some metrics such as accuracy
and stability. In this paper, a new modified version of LPA is proposed to improve the stability and
accuracy of the LPA by defining two concepts -nodes and link strength based on semi-local similarity-,
while preserving its simplicity. In the proposed method a new initial node selection strategy, namely the
tiebreak strategy, updating order and rule update are presented to solve the random behavior problem
of original LPA. The proposed algorithm is evaluated on artificial and real networks. The experiments
show that the proposed algorithm is close to linear time complexity with better accuracy than the
original LPA and other compared methods. Furthermore, the proposed algorithm has the robustness
and stability advantages while the original LPA does not have these features.
|