Community Detection In Complex Networks And The Hierachical Relationship Of The Community

Community structure is widespread in complex networks. Community detection is an important analysis direction in the complex network. Finding community accurately can have a better understanding of complex network characteristics, understanding network functionality and looking for hidden patterns. There are two types of complex network: unipartite network and bipartite network. However, current methods are normally for the uniprtite network or the bipartite network, or choosing different parameters for different types of the network. If the type is unknown, it is hard to do the community detection. Therefore, this thesis proposes an energy theory to measure the relationship of vertices, and create an energy model which can be used in both unipartite networks and bipartite networks. The energy model works on finding the unoverlapping and overlapping communities when the number of the communities is known or unknown. It also works on finding the hierarchical structure in the community. The energy model can solve the resolution limit problem which is widespread in modularity based models, and find overlapping vertices of the community even when most of the vertices are overlapping.This thesis analyzed the definition of community, proposes an energy theory based on the characteristics of the complex network types, which can be used to measure both unipartite networks and bipartite networks. There are two kinds of energy between vertices: positive energy and negative energy. The energy between two vertices is the sum of the positive energy and negative energy. The larger of the energy, the more similar of the two vertices are more likely to be in the same community.To do the community detection of which the number of the communities is known, an unoverlapping community detection method without knowing the number of the communities is proposed. Given the community number, using the eigenvector and the eigenvalue of the energy matrix, each vertex is given an energy vector to calculate the largest energy within communities. Especially, two communities detection can be done only by the largest eigenvalue and the corresponding eigenvector. Experiments show that, different from the traditional method, the unoverlapping community detection method without knowing the number of the communities can do the community detection in both unpartite and bipartite networks.To find the stable community, the largest energy based unoverlapping community detection method is proposed. By finding the positive energy which is greater than 0, the method finds the similar vertices, and put the vertex into the community of a vertex which has the largest energy between the two vertices. Experiments show that, the largest energy based unoverlapping community detection method can find stable community without knowing the number of the communities. What is more, it can be used in unipartite and bipartite networks at same time.To find the important vertices, the sequencing hierarchical method is proposed. By finding the center vertex of the community, this method does the hierarchical structure detection using the belonging coefficient sequencing. Experiments show that, the sequencing hierarchical method can solve the resolution limit problem, and avoid inefficient problem of the traditional hierarchical method which find the hierarchical structure of the complex network.To solve the multiple characteristics problem, the overlapping community detection method is proposed. Using the level of the vertices in a community, the method can find the overlapping vertices quickly based on the energy and the link relationship between the vertices and communities. Experiments show that, different from the traditional overlapping community detection, the method based on energy theory can find overlapping vertices even if most of the vertices are overlapping in a community, which put all the vertices with the same characteristic in the same community.