Research On The Methods Of Overlapping Community Detection In Complex Networks

Most complex systems in the real world can be modeled as complex networks.The nodes in the network represent the objects,and the edges represent the relationship between objects.The research of complex networks has become a hot interdisciplinary field.Extensive studies reveal that there generally exist underlying community structures in complex networks.The interconnections between nodes in the same community are close,but it is sparse between nodes from different communities.This property is very important for understanding the structure and function of complex networks.It is also useful for discovering the hidden rules and predicting their behavior,so as to provide guidance for the use and transformation of the network.Community structrue is the key and the fuandation for complex network analysis,which is of great importance.The community structures in real world are often overlapped,that is,there are common nodes between communities and some nodes belong to more than one commuinty.The overlapping community structure is more closer to the original real world.For example,we can simultaneously belong to the family group,the colleage group,the friends group and the partners group etc.Overlapping community detection and analysis has important theoretical and practical significance.We focus on the research of four key problems in community detection,namely,node importance computing,overlapping node seletction,local community expanding and community detection in attributed networks.Our contributions are as follows:1.In order to obtain stable comminity detection result,we propose a node infulence based label propagation algorithm.It takes the descending sequence of node infulence as the node order of label propagation.During the process of label propagation,we use the label infulence to make sure that each updated label can be identified.By calculating the node influence and the label influence,the stochastic factors in the original algorithm are avoided.The algrithm can not only obtain the stable result,but also performe better than other representative community detection algorithms.2.In order to use the disjoint community structure to get the overlapping community structure and improve the efficiency of overlapping community detection.We propose a novel overlapping community detection algorithm based on disjoint community expansion.It identifies the potential member nodes of each community by calculating the similarity between the nodes and the community.Then,according to the influence of the nodes on the community,the final overlapping nodes are determined.The algorithm can effectively use the existing disjoint community structure by identifying the overlapping nodes to detect the overlapping commuinty structure.It improves the efficiency of overlapping commuinty detection,and the quality of overlapping nodes is also high.3.Aiming at the high time complexity of global based community detection algorithm,we propose a community detection algorithm based on local extension.By analysing the local information of the network,the algorithm identifies local communities from two endpoints of each edge and its common neighbors,and then combines the high overlapped local communities.Each analysis process only considers the relationship between adjacent nodes or adjacent communities,so it narrows the scope of calculation,and can adapt to the large-scale networks.4.Most existing community detection algorithms only use the topological structure information of the network and ignore the importance of node attributes.For this problem,we propose a community detection algorithm based on coupled node similarity in attributed networks.The algorithm takes full account of the complex interactions at different levels to calculate the similarity of nodes,and then uses the similarity as the weight of the corresponding edges.Finally,it uses the community detection algorithms in weighted networks to obtain the community structure.The algorithm makes effective use of the node attributes and topological structure information in the network,and improves the quality of community detection result.Finally,we do many experiments on simulation and real networks and compare the proposed algorithms with the representative community detection algorithms.The experimental results confirm the effectiveness of the proposed algorithms in this thesis.