Research On Community Discovery Algoithms In Social Networks

The rapid development of Internet technology, has promoted the prosperity of various social platforms application. The research on social network, such as finding the characteristics of network structure, is helpful to understand the social network system deeply. Earlier studies only found the non overlapping community and considered that a node belonged to one community. As further research, the experts considered a node could belong to multiple communities, and found the overlapping community structure in social networks. Later, the experts focused their eyes on the edges to find the overlapping community structure in social networks. In this thesis, the community discovery algorithm in social networks is studied, and the two aspects of the concrete work in this thesis are as follows:(1) In the aspects of non-overlapping community discovery, this thesis implements a clustering algorithm based on diversity of similarity matrix, which is used to dig out the community structure of social network. Not only the two existing kinds of similarity measurements, this thesis also designs two improved similarity measure methods, and combines the two clustering algorithms to discover the community structure. The results show that, on the two kinds of artificial data sets and four real world networks, the two clustering algorithms based on diversity similarity matrix can find more accurate community structure, compared with the existing community discovery algorithms.(2) In the aspect of overlapping community discovery, this thesis proposes the three phase overlapping community discovery algorithm based on edge attraction. Besides clustering the edges based on the edge attraction, this algorithm not only adds optimization phase that transforms the edge community into node community, but also increases a phase that improves the quality of discovered overlapping community structure according to the overlapping nodes bias. The experimental results show that the proposed algorithm is better than the existing overlapping community discovery algorithm in the most of data sets.