Research On Overlapping Community Detection Method Based On Seed Extension

Many complex interconnected systems in real life can be abstracted as network structures.Through this abstraction,we can better study and analyze these systems.Community detection has important implications for understanding the structure and characteristics of the entire network and has been widely used in many fields.The overlapping nature of communities is considered as an important feature of the community.Previous non-overlapping communities have found it difficult to meet the current application scenarios,and overlapping community detection has become a new research hotspot.The research of traditional community detection algorithm is non-overlapping community.There are still many deficiencies in the research of overlapping community detection algorithms.Therefore,it is often found that the overlapping community structure in the network has more practical significance.Community detectability studies the issue of whether the community can be detected which is a prerequisite for community detection algorithms.Existing community detectability methods generally work under the premise of uniform communities.For the problem of community detectability under non-uniform conditions,this thesis proposes a community detectability method based on SBM.Firstly,we use the Stochastic Block Model(SBM)to model the network.And then we introduce the Bayesian inference to analyze the parameters of the model.Thirdly we use the fixed point of the free energy theory to determine state change of the model parameters.In the end we combine the BP algorithm to iteratively calculate the model parameters and get the final community detectability results.Through further verification of the simulation experiment,the community detectability method proposed in this thesis can complete the work of community detectability under non-uniform community conditions.The community detection algorithm studies the issue of how the community can be detected.With the deepening research on the detection of overlapping communities,many overlapping community detection algorithms have been proposed.However,existing algorithms still have the problem of high computational complexity and low accuracy.To solve these problems,this thesis proposes an overlapping community detection algorithmbased on seed extension(OCDSE).This thesis analyzes a large number of real-world network datasets and finds that there are a large number of edge-map diagram structures in the network which don't participate in overlapping community detection process.Excluding this kind of structure in advance can effectively improve the efficiency of overlapping community detection.Moreover,the importance of nodes of networks is studied in this thesis.Based on the degree of nodes,nodes with good distribution characteristics are selected as the seed nodes.Then we extend the seed nodes by the PPR algorithm to complete the core overlapping community detection.Finally,edge-map diagram structures removed are rejoined by the propagation algorithm.Through experimental comparison,this method has significantly improved accuracy and efficiency compared to other overlapping community detection algorithms.