A Dynamic Community-detecting Algorithm Based On Random Walk

The network science has sprung up as an intersectional science since 20 years ago and we realize the importance of the study of the complex network gradually. Community is one of the most principle characteristic of complex system. Intuitively, the community is the structure in which the edges between vertexes are dense and sparse on the contrary. The community-detecting is an NP-hard problem. In the first part of the paragraph, some typical networks and important algorithm are introduced. In the second part i introduce the dynamic algorithm based on random walk. A random walk means that starting from one vertex and jumping to the neighbours of this vertex randomly and going on.Qualitatively we expect the random walk will be stuck in the community if the start vertex. This means that the random walk will take a long step between two vertexes belonging to different community(keep trying to find way out).Base on this idea and calculate the expected first passage step between any pair of vertexes taking use of the Markov processing theory. Then we can cluster the vertexes into different communities according to the index. The third part is complexity and the advantages and disadvantages analysis. I tried many methods of solving the linear equations and proved that the general iterative methods was inefficient by the corollary of Cauchy’s interlace theorem and the spectrum of normalised Laplacian matrix. At last the conjugate gradient methods is accepted and the complexity is O(3). In the end, i examined the algorithm take use of two typical network and random graphs. The accuracy and stability of the algorithm are superior.