Effectiveness Evaluation Of Community Detection Algorithms In Complex Networks

The science of complex network has become a powerful tool for the study of complex system problems.There are many complex network systems in real life such as social networks,biological networks,computer communication networks,etc.Almost all complex systems can be understood as the network composed of nodes and their connected relationships.The study of network topology can help us discover some deeper network structures and gain a deeper understanding of network characteristics.Community detection is a typical clustering analysis tool of network node topological relationship.The community mining algorithm can be used to extract tight coupling structures in the network,which can reveal the deep relationship between nodes in the network,mine the organizational structure information contained in the network,and reveal the regular pattern in the network.And the analysis of community detection results can also be used as theoretical support for data mining.In short,the in-depth study of community detection algorithms has important theoretical and practical significance.In the various categories of community mining,the predecessors have done a lot of work,and proposed many authoritative algorithms to solve such problems,including Infomap based on information theory,Big Clam method based on non-negative matrix factorization,which can extract the overlapping structure in network,and also the methods based on modularity optimization such as Louvain,Fastgreedy,etc.And great majority of these methods can produce more optimum result on most networks.However,for networks with different structures generated from different domains,some algorithms have certain bias,for example,the method based on modularity optimization has the disadvantage of resolution limitation.Based on the existing theoretical research,this thesis proposes to research community detection methods by categorizing them.We summarizes and classifies different methods according to the bias of the theoretical hypotheses that form the community,and explores their effectiveness in different domains and different attribute networks.According to experimental result,we give guidance on how to choose the best performing community detection algorithm for a given network.Specifically,the main work of this paper includes the following aspects:1.Based on the existing community detecting theory,we propose to research the community detection methods by categorizing them according to the different theoretical assumptions of the algorithm when forming the community.It mainly includes the following five categories: methods based on global function optimization domain,clique-based methods,methods based on local diffusion,methods based on statistical properties,and methods based on node similarity.2.In this thesis,six networks with wide application and typical structural differences in social network and scientist collaborative network are selected.We propose to calculate the difference of indicators in different networks utilizing network topology attribute indicators.The results are presented through mathematical statistics and demonstrate bias of the network in its internal structure.3.This thesis proposes a comprehensive evaluation approach of the communities discovered by different algorithms in the network by combining the accuracy index with the topological attribute index.According to the difference of the experimental results,the similarity and bias of the same category and different category algorithms in the community are summarized.Based on the experimental results,we give detailed guidance on how to select the best performing community detection algorithm for complex networks of different sizes and structures.