The Research Of Community Detecting Algorithm For Complex Networks

Social network analysis started in the1930’s and has become one of the most important topics in sociology. Thestudy of the systems by complex network analysis has brought significant advances to our understanding ofcomplex systems. The community structure, or cluster, is proved to be one of the most famous feasures of thecomplex network. The cluster is the organization of vertices, with many edges joining vertices of the same clusterand comparatively few edges joining vertices of different clusters. The community structure of a network areusually related to the the type of the network, playing a similar role like the tissues or the organs in the humanbody. Detecting communities is of great importance in sociology, economy, biology and even the engineering.This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinarycommunity of scientists working on it over the past few years. Based on the algorithm of the community detecting,the main research of this thesis is as follows:1. The method to detecting the important vertices in the network has been studied in this thesis, whichincludes clustering coefficient, loop coefficient and betweenness. With the comparison of the simulation results, amethod which can detect the important vertices effectively has been found, and the best applied environment alsobeen defined.2. Based on the object oriented methodology, a concept of the “Virtual Force” has been proposed in thethesis. In which the relation between the adjacent vertices is considered as attraction while the relation betweenthe non-adjacent vertices is repulsion. The community structure is formed by the self-organization of verticeswhich are influenced by the virtual force of their neighbors.3. A new algorithm which based on the “Virtual Force” also been proposed. By the multiple simulations onthe computer-generated networks and the natural networks, the result proved a fact that, the algorithm can gainsatisfied detecting results in virous kinds of network, and can be applied in large-scale networks.4. This thesis also focuses on the study of the methods and standards to measure a community detectingalgorithm. Those methods and standards also been applied to estimated the result of the virtual force algorithm.And the algorithm is proved to be one of the balance methods, which have big advantage both on the efficiency,accuracy and applicability.