Research On Detection Algorithm And Node Influence Of Overlapping Community

Community is one of the topological characteristics widely existed in complex networks.Discovering community structure is a fundamental and hot issue in complex network.Community detection algorithm can be divided into overlapping and disjoint algorithms according to the classification results.In social networks,overlapping communities are closer to the real network structure than disjoint communities.Therefore,in this dissertation we research the overlapping community detection algorithm.At the same time,considering the changes of community structure may have a negative impact on the applications which depend on the community,we also research the influence of nodes on the stability of the community structure,which is used to assist in the analysis of the vulnerability of this type of application.Analyzing the influence of nodes is also a hot issue for researchers.For solving these two issues,this dissertation proposes two following algorithms.Firstly,an overlapping community detection algorithm ESCA(Edge Strength Conductance Algorithm)is proposed,which is an improved algorithm overcoming the shortcomings of the Conductance.Conductance is a weighted overlapping community detection algorithm with relatively reliable detection results,but the relationship between nodes and their neighbors is not considered when selecting the initial community,which leads to unreasonable initial community selection and lower accuracy in discovering the real community of the network.In addition,the algorithm still has problems of missing nodes.For solving these shortcomings,ESCA is proposed by considering the edge strength and the belonging degree.Experiments show that there is no missing node problem in the ESCA,compared with the Conductance and COPRA(Community Overlap PRopagation Algorithm),it can more accurately find the number of communities in the network,and the divided community is closer to the real community of the network in the weighted and unweighted networks generated by the LFR benchmark.Secondly,we propose an algorithm BCA(Break Community Algorithm)for evaluating the influence of nodes on network community structure.BCA firstly identifies the substructures which has the greatest influence on the community structure of the network,then evaluates the global influence of all substructures.Finally,the first K nodes with the greatest influence on the community structure are selected from the substructures.Experiments show that compare with the traditional node evaluation indexes,BCA can more accurately identify the node set which has the greatest impact on the community structure in the weighted and unweighted networks generated by the LFR benchmark.