| There are a large number of complex systems in life,which can be abstracted into complex networks,such as infectious networks,biological networks,human networks and so on.Community structure is the most basic feature of complex networks,which can reveal the structure and functional characteristics of networks.The process of discovering community structure is community detection.With more and more kinds of complex networks,community detection faces new challenges,Thus,it urgently requires researchers to put forward efficient and effective community detection algorithm which can be appropriate for different situations.This thesis presents two community detection algorithms for the following two different problems of community detection,namely,DCDC and Vortex.DCDC algorithm finds the core of a community based on of mutual k nearest neighbor relationship,which can overcome the limitation that the kind of algorithm is unable to detect the community with any structure or size.Vortex algorithm is an improved algorithm of Black Hole algorithm,the algorithm to discovery community core based on the high structure motif gravity pattern,it overcomes the poor performance of Black Hole algorithm on the network where the degree of nodes has a big difference.The basic principles and advantages of DCDC algorithm and Vortex algorithm are as follows:(1)DCDC How to detect community with any structure and size has become a difficulty in community detection.To solve this problem,a community detection algorithm DCDC has been proposed,which can find the community core based on k nearest neighbors.The algorithm first iterates over all the nodes,and then puts two similar nodes which are k nearest neighbors and their common neighbors to find community;Next,if one node being not in the backbone is one of the mutual k nearest neighbors of another node in the backbone;Then,the algorithm detects the abnormal nodes in the community core and marks them as unclassified nodes;Finally,the algorithm uses the influence to assign unclassified nodes to obtain the final community structure.The algorithm is simple and has low time complexity.In addition,there is no need to set the number of communities in advance.The comprehensive experiment,performed on four real networks with different structure and three of LFR synthetic networks with different sizes,show that DCDC algorithm can detect community with any structure and any size,and the quality detected by DCDC is higher than the five benchmark algorithms.(2)Vortex Most community detection algorithms are difficult to correct detect community structure in the network where the degree of nodes has a big difference.The Black Hole algorithm is a robust graph embedding algorithm,which obtains the layout of the minimum net force on the two-dimensional plane through the graph embedding method in graph drawing,and then obtains the final community structure through the DBSCAN clustering algorithm.Since only the lower order connections between nodes are considered,the algorithm poorly performs on the network where the degree of nodes has a big difference.To solve the problem,a community detection algorithm Vortex based on the gravity pattern of the motif is proposed,by using a high order structural motif.When using the motif to embedding,The similarity between two nodes can take advantage of global structure by using the high order structural motif,which enables the Vortex algorithm to find the implicit connections of nodes without being affected by sparsity of networks.Besides,Vortex algorithm also proposes a motif-based method to assign the unclassified nodes.The results show that the community structure detected by Vortex algorithm is not only higher in community detection quality than Black Hole algorithm,but also higher than the other six compared algorithms in most cases,no matter on the LFR network where the degree of nodes has a big difference,or on the 6 small networks with ground-truth structures and 8 networks without ground-truth structures. |
PDF Full Text Request