Research On Community Discovery In Social Networks

The community structure exists in complex networks generally. Nodes are connected closely within communities. However, nodes are connected sparsely between communities. There is the community structure in social networks, for example, people in accordance with the "friend" constitute the circle of friends on social networking sites. Community discovery on social networks is an important way to understand the structure of the network and to explore its functions. The community structure has important significance for the research of the dissemination of information on social networks and the recommendation of friends or commodities.This paper analyzes the structure properties of the social network model first. Then, the edge’s local clustering coefficient and the structural balance theory of the signed network are further extended. Finally, two more efficient and stable community discovery algorithms are respectively proposed for the two kinds of modeling methods, which are the unsigned network and the signed network. Specific as follows:1) After analyzing the characteristics of the calculation of local clustering coefficient and node similarity in the unsigned network, the extended local clustering coefficient is proposed as the edge’s structural properties in unsigned networks. This attribute is more able to reflect the characteristics of local network density and network structure. By combining this new edge structure measure with the label propagation algorithm whose time complexity is linear, the label propagation algorithm with the extended local clustering coefficient is proposed. The experiments, which are conducted on a variety of real social network data sets, show that the algorithm can effectively detect and improve the accuracy and stability of the community discovery on unsigned social networks.2) Firstly, as for the problem that the traditional label propagation algorithm cannot be used in the network with negative edges, this paper proposes a new signed network label propagation algorithm. Then, the structural balance theory of the signed network is analyzed deeply and the structural balance degree which can measure the structural balance and the local network density of the edge in the signed network is proposed. Applying structural balance degree in the process of label propagation, a signed network label propagation algorithm combined with structural balance degree is proposed. The algorithm makes labels spread on the local network with balanced structure and high positive edge density. It prevents the propagation of the labels on the local network with high negative edge density and unbalanced structure. These make the communities which are discovered by the algorithm consistent with the definition of the balanced network. The experiments on signed network data sets show that the stability of signed network label propagation algorithm with the structural balance degree is stronger, the communities which it discovered can reflect the network balance, and its convergence speed is faster than that of the signed network label propagation algorithm without considering the structural balance.