Research On Community Detection Technology In Complex Networks

In recent years,as the increasingly large scale of Internet and its virtual network,the network's topology becomes more and more complex.In the complex networks,the individual preference and group relationship have great application value.And the community discovery technology is a fundamental methodology to dig the individual preference and the group relationship,and it obtains extensive attention of the researchers.However,there are some problems in the current community discovery algorithms.Such as,some algorithms need to set some parameters to obtain accurate community structure,and some classic community discovery algorithms cannot exploit the overlapping community structure.These problems affect the accuracy of the community discovery algorithms in the complex networks.In order to solve the above problems,this paper focuses on the study of community attributes and overlapping communities in the complex networks,and proposes a pre-processing model that can be applied to the complex networks and an overlapping community discovery algorithm.The work of the dissertation is partly supported by the National Natural Science Foundation of China(No.61172072,61271308),Beijing Natural Science Foundation(No.4112045),and Research Fund for the Doctoral Program of Higher Education of China(No.20100009110002).The main works of this paper include the following two aspects:(1)Based on the Markov clustering algorithm,this paper proposes a pre-processing model of the complex networks.The pre-processing model can analyze the material information of the nodes from the complex networks to obtain the kernel nodes,and can weigh the network topology with the obtained edge information of the complex networks.Combined with the kernel nodes and weighted edges to obtain the pre-processing network.The pre-processing network contains the apriori information needed by the community discovery algorithms.So the pre-processing network plays a significant role in reducing the influence of the artif-icial setting on the accuracy of the community discovery algorithms.(2)A multi-label overlapping community discovery algorithm based on random walk(RW-MLP algorithm)is proposed in this paper.The RW-MLP algorithm combines with the global advantage of random walk,and uses the information of network structure obtained by the pre-processing model.Then it constructs the label matrix and performs label propagation by random walk.Finally,the algorithm uses the obtained labels to get the result of community discovery.The RW-MLP algorithm can reduce the randomness and balance the size of the communities,while also can guarantee the global division of the communities.The pre-processing model and the RW-MLP algorithm are respectively tested on the artif-icial network dataset and the real network dataset in this paper.The numerical results show that,the pre-processing model can get more accurate structure information of the network,and can improve the accuracy of the community discovery algorithm.Compared with other overlapping community discovery algorithms,the accuracy of the RW-MLP algorithm is also improved remarkably.