Research On Semi-supervised Community Detection Algorithm

Many systems existed in nature can be represented by the network, such as Interpersonal network, Protein interaction network, Traffic network. These networks have very high complexity, so they are called "complex network". As one of the most important branches of complex networks, community structure has attracted more and more attention form people.The existed community detection algorithms have high computational complexity, require prior number of community, need to advance the development of evaluation index and other defects, some even need give the general community size, this limit the practical application of these algorithms.As one of the most important community detection algorithms, LPA(Label Propagation Algorithm) has the advantages such as simple, low complexity, do not need to specify the number of communities and so on, but its accuracy is relatively low. Based on LPA, we designed an improved algorithm, the innovations are:First, because of equal treatment of each node neighbors in LPA, this will induce label propagate to another community and resulting in low accuracy. In this paper, we add weight to each edge of the network to block the label propagation between different communities.Second, the existed community detection algorithms are unsupervised, they can not make advantage of knowledge that experts give. In this paper, we add an edge to the node pairs of must-link, and delete some edges between cannot-link node pairs from their shortest path, so that the accuracy can be improved.Last, combine the two methods above, and run the algorithm on artificial and real networks, then compare the result with other algorithms to verity the effectiveness.