Research On Community Discovery Algorithms For Complex Networks Based On Gaussian Kernel And Pagerank

In the real world, many complex systems can be expressed by using a complex network, like protein interaction networks, the airline networks, World Wide Web, telephone communication networks, social network of relationships, etc. As an emerging discipline direction, complex networks attracted the concern of researchers from different disciplines. The researches about complex network can help to reveal the regular pattern which regulates different real systems modeled by complex networks, therefore it will be relevant in a number of disciplines (biology, social sciences, etc.), and it is essential for understanding the structures and behaviors of the network.The traditional partition methods of the community structure in complex networks is that one individual belongs to only one community, but actually, some individuals may belong to one more communities in the real world, that is to say the community structures may be overlapping. The previous work about community structure of the complex network analysis is mainly concentrated on undirected and unweighted network. In fact, the connections between network nodes usually have directions and weights, the current common methods to find the network community structure is simply ignoring the directions and the weights of the edges. Ignoring the directions and the weights may lead to lose some important topology information what they contain, and thus one can’t correctly and effectively divide the network into community structures.This paper introduces the definition of the community structure in complex networks and some related indicators firstly, as well a number of algorithms of discovering community structures in complex network and the advantages and disadvantages of the different algorithms, and then proposes two algorithms about community discovery. The details are as follows:With regard to the problem of non-overlapping communities and overlapping communities in undirected and unweighted networks, and based on the Gaussian kernel similarity matrix, and combined with spectral bisection, this paper proposes an algorithm named community structure discovery algorithm based on Gaussian kernel similarity matrix. Firstly, by adjusting the Gaussian kernel parameters to change the similarity of scale, we can find the corresponding community structure when the value of the modularity is largest relatively. Secondly, the changes of the Gaussian kernel parameter would lead to the unstable nodes jumping off, so with a slight change in method of non-overlapping community discovery, we can find the overlapping community structure. Finally, Synthetic data, karate and political books data sets are used to test the algorithm to demonstrate the feasibility and effectiveness of this method. In addition, making some minor changes of the algorithm, it can be used in the weighted networks, the test results show that the method is also feasible.With regard to the problem of overlapping communities in directed networks, this paper proposes an algorithm named community structure discovery algorithm based on PageRank algorithm. The PageRank value can be used to characterize the degree of importance of the nodes in the network to help finding the core node. Then expand outward around the core node to form a local community, if reached the termination condition which we set, stop the expansion. Finally merging the different local communities to observe the change of the modularity, and choosing the partition which corresponds to the largest modularity as the final result. In the process of finding local communities, one node can belong to different local communities, so the method is equally applicable for finding overlapping communities, too. Finally, the tests on synthetic data and real network data also show that the proposed method achieves good results.