Research And Application Of PageRank Algorithm To Community Detection

The specific structure of Social Network is discovered because of the degree of closeness among vertexes in the network or their similar features. Therefore, detecting the communities of social networks is one of the most important methods to research the structure of social networks. We can obtain the inner constructs, the relation of interaction and the specific properties by researching the divided networks, which can help understand and apply them.Lots of algorithms which utilized the closeness between vertexes to detect community had been proposed. We regarded the networks as a system of which information diffused randomly. In other words, the rank of other vertexes about the information that one vertex had diffused reflected the closeness between them, which conformed to the rank principle of PageRank algorithm. We proposed an algorithm(PR-DCS, Page Rank-Detecting Community Structure) for detecting community structure that based upon the principle of PageRank algorithm and information diffusion theory. PR-DCS algorithm based on the random walk model to extend the PageRank vector to information diffusion matrix and obtained the structure of community by using the distribution of information diffusing from vertexes and the closeness between vertexes calculated in the network. Through the comparisons with other typical algorithms of detecting community structure the results had shown that PR-DCS could extract the structure of community of networks accurately.PR-DCS algorithm has been improved by combining prestige in PageRank and desire conception in PR-DCS called PR-DCS pro. Vertexes in the same community are with closer relationship to communicate fluently, which process is faster than vertexes in different community to be stable. PR-DCS pro calculate the stable relationship by the rate of information after diffusion from vertexes. The core vertexes which are divided in together tend to be stable firstly, which is accurate in extracting community structure. Experiments demonstrate that the rate of core vertexes to be stable is faster than others. The modularity in the improved algorithm is higher and it has a better explanation to the real structure.We have analyzed the impact of information diffusion count to the result of partition in the process of the exploration and exploitation. It is “Six Degrees of Separation” that guaranteed the correctness of elements in information matrices which is the constraint of diffusion. For the reason that as the times of diffusion grow, so does information turning into prestige. At the same time communication between vertexes are obtained assurance.Experiments have shown that it is 6 that can help constrain objectively the degree of communicate and extract structure of communities.