Research Of Community Detection Problem Based On Spectral Graph Theory

One of the most important features of complex networks is the existence of community structure,where nodes in the same communities often have similar properties or functions.Community detection plays an important role in solving complex problems of life,such as the commodity recommendation,the online public opinion controlling,protein function exploration and so on.The idea of most community detection algorithms are based on division or agglomeration,while the algorithms based on opinion dynamics model are fewer and with bad performance.This thesis studies the community detection algorithms based on the DeGroot model.Firstly,a maximum clique or a node is selected as the seed,and then a larger state is assigned to the seed while a smaller state is assigned to every other node.By exchanging opinions with their neighbors,the nodes in the same community tend to reach local consensus.According to the relationship of states among nodes,this thesis focuses on dividing the networks into two and more than two communities respectively.For dividing the network into two communities,two different algorithms are presented.In the first algorithm,the communities are expanded by the maximum clique of the network,the nodes whose states are not less than mean are recorded in one set,while other nodes are recorded in another set,then the DeGroot model is used to update nodes’ states.The experiment results indicate when the partition reaches the local stability,a very good community partition can be obtained.The time complexity of this algorithm on a network with n nodes and m edges is O(3n/3+Tn+Tm),if the network is sparse,then the time complexity is O(dan3d/3+Tn)where T is the number of iterations of the DeGroot model and d is the depth of the solution space tree.To solve the problem that the maximum clique expansion algorithm fails to detect dense networks or networks with a bigger maximum clique,the second algorithm which expands communities by the seed node is designed.The time complexity of the seed node expansion algorithm is O(Tn + Tm),if the network is sparse,then the time complexity is O(Tn).Moreover,the number of iterations of the algorithm depends on the initial seed node selection.Generally,the larger degree of the seed node,the fewer iterations of the algorithm.Experiments on the benchmark networks,the accuracy of these two algorithms are not less than the classical spectral method,and the algorithm based on seed node expansion is slightly faster than the classical spectral method.For dividing the networks into more than two communities,a seed node method based on DeGroot model is designed.After each iteration,the nodes with larger states are recorded in a set.When the local stability is reached,the set is a good community of the seed node.Then continue selecting seed node from the rest of the nodes and the process is repeated until all nodes are extended to the corresponding communities.The time complexity of this algorithm is O(NcT(nlog2n+m)),if the network is sparse,then the time complexity is O(NcTnlog2n)where Nc is the number of communities of the network.By testing the real and artificial benchmark networks,the accuracy of community partition of this algorithm is higher than that of CNM,BGLL and MG algorithms.