Research On Complex Network Clustering Algorithm Based On Random Walk

In the real world, there are many complex networks, such as biotechnology network, science, technology network, social network and so on. Recently, the study of complex networks has attracted researchers from many fields of computer, physics, mathematics, biology, etc. It has become one of the hottest interdisciplinary sciences. Complex networks clustering aims to uncover the real community structure of network, including the community structure of unsigned network, signed network, weighted network, directed network and so on. The research of complex networks clustering has an important value of social and application, as it can predict the networks’behaviors, facilitate the analysis of networks’topology and mine the potential functions of networks. In this paper, we make researches on the unsigned and signed complex networks, and propose the corresponding algorithms of detecting community structures based on random walk.Main works of this paper are as follows:(1) In the unsigned networks, the communities can be divided into strong community, weak community and so on, which is based on the obviousness of community structure. Most existing community detection algorithms show excellent performance in mining strong community structure. However, some algorithms are inadequate in mining weak community structure. This paper proposes a new method of detecting community structure based on the assumption that the probability of one node gets to other nodes inside the community is greater than the probability of other nodes outside the community. Firstly, we find the local maximum degree nodes in the global network, then, using local maximum degree nodes to find minimum complete sub-graph regarded as initial community. Nodes in initial communities are treated as clustering nodes, other nodes in network are non-clustering nodes. Secondly, calculate the probability of each non-clustering node belong to initial communities using of conditional probability model based on random walk, then join it in the most likely community. Finally, the clustering communities are formed by optimizing method. In the real-world and computer-generated random networks, we compare the proposed algorithm with other classic network clustering algorithms and evaluate the algorithm performance by the measure of NMI and F1. The experimental results indicate that the proposed algorithm can detect the network community structure well, especially for the weak community. It can improve the clustering accuracy greatly and has obvious advantages compared to other clustering algorithms.(2) In the signed networks, the relationships between nodes have positive relationship of "friendship, alliance" and negative relationship of "hostility, competition". Some existing clustering algorithms of signed networks don’t make full of the negative information, which has a certain influence on the community detecting precision. In view of the above problem, this paper proposes a new method based on the positive and negative relationships in the signed network to detect the community structure via the model of random walk. Firstly, calculating the sum degree of each node which is the sum of positive degree and the absolute of negative degree treated as the node degree. Depending on nodes degree to find local minimum community and expanding by random walk. Nodes in initial communities are treated as clustering nodes, other nodes in network are non-clustering nodes. Then sort all non-clustering nodes in descend and making a judge to them one by one via the positive probability and negative probability calculated by random walk. Based on the comparison results of positive probability and negative probability to determine whether the non-clustering nodes join initial community or not or mining a new local initial community. Finally, the clustering communities are formed by optimizing method. The feasibility and effectiveness of the proposed method are verified on the real-world and computer-generated random signed networks. At the same time, compared with other signed networks clustering algorithms, the proposed algorithm has higher accuracy. Due to the fully use of negative relationship between nodes, the stability and effectiveness of the proposed algorithm can be guaranteed.