Research Of Community Structure Detection In Complex Networks Based On Local-center Vertices

With the development of modern network science, our understanding of complexnetworks has improved. One of the most relevant features of graphs representing complexnetworks is community structure, or clusters, i.e. the organization of vertices in clusters, withmany edges joining vertices of the same cluster and comparatively few edges joining verticesof different clusters. How to detect the community structure in complex networks has becamean important research project in data mining field–community detection technology.Based on the features of complex networks, we purpose the concept of local-centervertices. with the observations and study of the distributions of local-center vertices incomplex networks, we analyze the effection of local-center vertices on community detection.Based on local-center vertices,we purpose two communtity detection algorithms. The firstalgorithm first finds all local-center vertices, and then detects communtites by local expansionstarting with local-center vertices, we can apply parallel technology to expand local-centervertices in order to quickly detect the communities which regard the local-center vertices ascores. The second algorithm also find all local-center vertices first, and then calculates therelationships between local-center vertices and other vertices in the eigenvector matrix ofmodularity matrix to find the corresponding communities which regrad the local-centervertices as cores. For those remaining vertices which don’t belong to any community, thesetwo algorithms both find the iterative local-center vertices in remaining vertices, the firstalgorithm carrys out local expansion again and the second algorithm calculates relationshipsagain, then communities are formed. Repeat this procedure until the number of communitiesdon’t increase.Our experiment uses adjusted omega index and overlap modularity to evaluate theaccuracy and rationality of those results on31datasets，which shows that，two algorithmsboth improve the rationality in some datasets compared with some well-known algorithms,and the number of found communities is closer to the real number of communities. The firstalogrithm still improves the efficience of community detection for larget-scale networks. Thesecond algorithm gets better accuracy.