Research On Local Community Detection Method Based On Expansion Thought

There are many complex data in practical application,such as user interaction in social networks,product purchase and interaction between organic proteins,etc.It can be described as a network of nodes connected by interacting edges,that is,a complex network.Community detection is one of the essential technologies of complex network analysis.The purpose is to discover a group of nodes with high internal cohesion in the network but relatively isolated from others.It can be seen that the community detection can help to understand the characteristics and dynamic behavior of the complex networks,thereby improving the visibility of network data.In recent years,with the rapid growth of various networks,the detection of large networks is expensive and complicated.In addition,for large networks,the stability of community detection methods needs to be improved.Therefore,this thesis proposes a local community detection method with the idea of expansion,which adopts local information in the network to predict the community structure.The main contents of this thesis are as follows:(1)Aiming at the local community detection problem of large networks,a local spectral approximation algorithm(LRW-LSA)based on the limited random walk is proposed.Firstly,LRW-LSA obtains a smaller range of subgraphs through the fast limited random walk to decrease the amount of calculation.Then,a fast clustering fusion method is employed to improve the coverage ratio of sub-graphs to the restored community.Finally,he local Lanczos spectral approximation method is utilized to restore the local community.In conclusion,the exploration process of LRW-LSA starts with a small number of seed nodes to identify all potential community members in the local community.Through experiments results on real data,the effectiveness of this algorithm is verified.(2)To enhance the stability of the existed community detection algorithms,combined with the integrated learning algorithm,an ensemble local spectral approximation algorithm based on a limited random walk(LRW-LSA-EL)is proposed.Firstly,the optimal seed set ratio is obtained through experimental strategies,and the influence of nodes is introduced to optimize the seed set in the meantime.Then,combined with the LRW algorithm,the Bagging algorithm is employed to random sampling to construct multiple base learners with individual differences,and then LRW-LSA-EL utilizes the voting strategy to obtain a strong learner.Finally,the local community to be detected is recovered by using the Lanczos method.Experimental results show that LRWLSA-EL is more stability and accuracy than LRW-LSA algorithm on different real network data sets.