Partitioning Methods For Community Structure In Complex Networks

In recent years,as the WS small-world network model and BA scale-free network model was proposed,the study on complex networks is achieving a climax at home and abroad now. The study on complex networks treats the real systems such as the Internet,electricity networks and metabolic networks with the viewpoint of system science.Community structure exists in many real networks.How to find such communities effectively is one of focuses of many recent researches in the branch of complex networks.In this article,the author proposes a partitional method based on common neighbours matrix and gain function and generalizes the method to weighted networks.The main work of this paper can be summarized as follows:1.Defining the common neighbours matrix and gain function,and Proposing an effective method of analyzing the community structure in complex networks based on these two concepts.The elements in common neighbours matrix means the number of common neighbours between nodes.With the gain function as the objective function of analyzing the community structure,we derive a partition method based on the eigenvalues and eigenvectors of gain matrix and increment matrix.Further more,we apply this method to three common real network data and compare the computational results with modularity-based analysis methods proposed by Newman.Computational results demonstrate that the proposed method is feasible and effective.2.Redefining the common neighbours between a pair of nodes in weighed network and generalizing the algorithm based on common neighbours matrix and gain function to weighted networks.Although there are many weighted network in the world,networks are usually considered to be unweighted in lots of algorithms for community structure in complex network.Certainly the above algorithms can be applied to such networks by simply ignoring edge weights,but to do so is to throw away useful information contained in the weights,information that could help us to make a more accurate determination of the communities.In this paper we use the technique that weighed networks are mapped onto multigraphs proposed by Newman and redefine the common neighbours between a pair of nodes in weighted network.Then,the algorithm based on common neighbours matrix and gain function is generalized to weighted networks.Further more,we apply this method to a computer-generated network and a real social network.Computational results demonstrate that the proposed method is feasible and effective.