Detecting fuzzy network communities based on semi-supervised label propagation

Abstract

Most existing methods use only network topology information, which neglect much other important information such as the network background information which could be useful to uncover the network communities. In this paper, we proposed a fast semi-supervised algorithm to uncover the fuzzy network communities using label propagation technology, which incorporating the prior information to facilitate the community detection process. Specially, we know the true community membership of a certain percentage nodes in advance. Firstly, the node graph is transformed to line graph, and the weight of line graph are defined. Then, the proposed algorithm is applied in the line graph to propagate the label of certain labeled nodes to the whole network until convergence, and the final label of a given node is its community id. It worth mentioning that our algorithm is very fast and with almost linear time complexity. Extensive simulations using both synthetic and real-world benchmark networks are performed to verify the algorithmic performance.