| Community structure commonly exists in complex networks as a modular structural feature.This is reflected in that a network can be divided into subgraphs in which nodes are more densely connected to each other than the rest of the network.Such a division is named community detection.The detection of communities contributes to analyzing the local characteristics of individuals and their relationships in complex networks,and is of great significance to understanding the structure and function of real-world networks.At present,community detection has been applied in many fields such as protein structural analysis,infectious disease prevention,commodity recommendation,and Internet communications.Most of the community detection algorithms search for the optimal partition based on community quality evaluation indexes.However,many community quality evaluation indexes cannot accurately measure the community structure,due to the following aspects:on the one hand,they only consider the static structure of communities but ignore the stability reflected in the dynamic process of searching communities;on the other hand,there are usually problems with the indexes based on network topology structure,especially in the resolution limit and the identification of community cohesion.Besides,existing algorithms can hardly keep the balance between search space and efficiency in their community detecting strategy.Such problems limit the accuracy,stability,and scalability of these algorithms when detecting communities on real-world datasets.Aiming at the above problems,based on the average mutual information between partitions,the mutual information of network and communities,and the point-wise mutual information between nodes in the network,corresponding community quality evaluation indexes are proposed and applied for community detection.The main contents and contributions of the thesis are as follows:（1）Community Detection Based on Average Mutual InformationThrough the average mutual information between community partitions,we evaluate the quality of communities from the perspective of stability.In the previous research,we applied this idea to the GN algorithm and the COPRA algorithm,and achieved more accurate results than the original algorithms.However,these two algorithms still have the problems of high time complexity and unstable results.The AMI-NRL algorithm proposed in this paper implements a more efficient community detecting strategy through network representation and hierarchical clustering,thereby greatly reducing the time complexity.The AMI-OMLPA algorithm improves the stability and accuracy of the multi-label propagation algorithm by introducing node influence and average mutual information.（2）Community Detection Based on Mutual Information of Network and CommunitiesAs a community quality evaluation index based on network topology,the mutual information of network structure and communities outperforms the widely used modularity and two-layer average code length in resolution limit and the identification of community cohesion.Based on the index,the MINC-NRL algorithm is proposed,which absorbs the advantages of using network representation and hierarchical clustering as a community detecting strategy,and also overcomes the problem that AMI-NRL is susceptible to single nodes.By using overlapping hierarchical clustering,the algorithm effectively avoids the situation that some border nodes are prematurely assigned to a specific community,and also has the ability to detect overlapping communities.Experiments show that the index can effectively evaluate non-overlapping and overlapping partitions,and the MINC-NRL algorithm can obtain accurate results on both real-world and synthetic datasets.（3）Community Detection Algorithm Based on Point-wise Mutual InformationFor non-overlapping communities,spectral community detection methods are accurate and stable.Spectral methods detect communities by constructing a similarity matrix for nodes,but the similarity matrices used in current methods only extract certain structural features,which limits the accuracy of measuring connections between nodes.In addition,the number of communities is usually required as an input in these methods,which is usually unknown in most application scenarios.Aiming at the above problems,we construct a Laplacian graph kernel for spectral clustering based on the point-wise mutual information between nodes,and determine the number of communities by introducing the community quality evaluation index.Experiments show that the algorithm can figure out the number of communities in different scales of real-world and synthetic networks,and obtain accurate non-overlapping partitions. |
