Community Detection Algorithm of the Large-Scale Complex Networks Based on Random Walk

摘要

Community detection on large-scale complex networks has become a popularly discussed topic with the development of the social network. In this paper, we proposed a community detection algorithm based on the random walk theory. We assume each node has the energy value and the random walk process is considered as energy transfer. According to the transition probability matrix, nodes transfer energy in the network. We divide two nodes which transfer the most energy to each other into one community. The algorithm can obtain accurate division results on small data sets. However, when we applied it to the large-scale network, we find a problem that the sparse degree of matrix is reduced during the energy transfer process. We set the threshold to keep the energy matrix is still sparse in the process of transfer to solve this problem. We conduct extensive experiments on real-word large network provided by Stanford University and the results demonstrate the efficiency and effectiveness of our proposed algorithm.