Research On Key Methods Of Community Detection For Complex Network

With the rapid development of the social networks,people have obtained massive and rich network data.However,how to obtain the knowledge has become an urgent problem to be solved.The community structure plays an important role in understanding the structural functions and discovering hidden patterns in the network.However,due to the complexity,heterogeneous and massiveness of the complex networks,there are three challenges in community detection:1)How to improve the efficiency of overlapping community detection;2)How to improve the effectiveness of community detection by using higher-order structure;3)How to fuse the network structure,text and timestamp information to jointly detect community and topic.We provide corresponding solutions from three aspects:overlapping community detection,community detection based on higher-order structure,and community detection based on rich information.The main contributions of this thesis are as follows:1)Community detection based on lower-order structure.To solve the problems of outliers,non-determined result,excessive overlapping in overlapping community detection,We propose two improved strategies.(1)Nodes in overlapping community have differen types.We adopt rough set to characterize node type,and propose an overlapping community detection method based on rough set.Meanwhile,we adopt an easy-tuned threshold to control the range of overlapping nodes to solving excessive overlapping problem.(2)We propose an overlapping community detection method by combining density and modularity optimization to detect outlier and avoid non-determined result.Meanwhile,we merge communities with high overlapping degree to solving excessive overlapping problem.We adopt distributed computing platform to parallelize it to improve the efficiency of overlapping community detection from large-scale network.2)Community detection based on higher-order structure.Methods based on lower-order structure can not capture the information hidden in higher-order structure,which lead to low effectiveness of community detection.We adopt higher-order structure to detect community.Firstly,we design a method to generate higher-order structure adjacency matrix;Secondly,we design a method to generate approximate invariant subspace to avoid the calculation of many singular vectors;Finally,we propose a method to search commnity indicator vector in approximate invariant subspace to detect local community.It improves the effectiveness of community detection.3)Community detection based on rich information network.Considering rich information including text,and timestamp into community detection,we propose a generative model to detect dynamic topical community.Firstly,we define the problem of dynamic topical community detection.Secondly,the network structure,text and timestamp are modeled in a unified way;Finally,we design an inference method to estimate the parameters to detect community,topic and their temporal variation effectively.