Weighted label propagation based on Local Edge Betweenness

In complex networks, especially social networks, networks could be divided into disjoint partitions. However, nodes could be partitioned such that the number of internal edges (the edges between the vertices within the same partition) to the number of outer edges (edges between two vertices of different partitions) is high. Generally, these partitions are called communities. Detecting community structure helps data scientists to extract meaningful information from networks and analyze them. In the last decades, various algorithms have been proposed to detect communities in graphs, and each one has examined this issue from a different perspective. Yet, most of these algorithms have a significant time complexity and costly calculations that make them unsuitable to detect communities in large graphs with millions of edges and nodes. Label propagation algorithm (LPA), a fast random-based algorithm, can easily detect communities in big graphs, but its accuracy compared to other algorithms is low. In this paper, we have improved LPA accuracy, and to achieve this goal, we propagate label based on the Local Edge Betweenness score. The proposed algorithm, named Weighted Label Propagation based on Local Edge Betweenness, is able to identify distinct communities in both the real-world and artificial networks. Also, the proposed algorithm could detect communities in weighted graphs. Empirical experiments show that the accuracy and speed of the proposed algorithm are acceptable; additionally, the proposed algorithm is scalable.