Research For Community Detection Algorithm Based On Semi-supervised Learning

In the world many complex systems can be described as networks .In recent years, people pay more and more attention to complex network and it is used extensively in many fields. There are some main networks being studied such as all kinds of networks in Life Sciences, WWW, Transport network, Scientists cooperation network and Linguistic networks.. With the development of study in network, community structure is found in many networks. Many researchers has studied it from different aspects. However, when there are labeled nodes in a network , we need to use the method of semi-supervised learning to train a good learner on both unlabeled nodes and labeled nodes for detecting community structure. This paper will introduce two unsupervised learning algorithms for detecting community structure in a network with unlabeled and labeled nodes.The first algorithms is based on information dissemination model. It looks a network as an information dissemination network, and the labeled nodes are the source and the unlabeled nodes are the target .The information of labeled nodes disseminate to their neighbours which must be the target .The algorithm can't stop until the information of all labeled nodes spread to every unlabeled nodes .Then every unlabeled node contains every kinds of label information ,and community structure will be find through comparing quantity of every kinds information. During the information dissemination process, the algorithm control signal attenuation to simulate real signal attenuation through the attenuation function. Classification accuracy of this algorithm is relatively high, taking up less storage.The second algorithm is based on the gravity model. All nodes are seen as gravitational entities and the law of Gravity is used into the algorithm. By calculating the gravitation among all nodes, community structure will be found. Experiments show that gravitation reduces as the distance increases .The far nodes are affected weakly, but the distance is not the unique factor. Another factor is the attraction of a node .The larger it is, the stronger the gravitation is.The two algorithms in this paper train good learners on both unlabeled and labeled nodes .It is proved in statistics that unlabeled nodes can improve the accuracy of the learner. Algorithms embody the local and the global consistency, avoiding the local maxima .The experiment shows that complexity of the two algorithms is relatively low.