Overlapping Community Detection Based On Local Information Expansion

In recent years,with the development and deepening of network technology research,people have found that many real-world networks contain overlapping community structures,and it is common for a node to belong to multiple community structures.Then we find that overlapping community organizations are of great significance for understanding the interaction and dynamic evolution of information within a community and between other communities.Therefore,it is very necessary to find overlapping communities in the network to study the interaction of information within the communities.At present,the existing overlapping community detection algorithms can be divided into global-based overlapping community detection algorithms and local-based overlapping community detection algorithms.The global overlapping community detection algorithm mainly divides the entire network from a global perspective.It needs to predict the structural information of the network and has high complexity.Based on the local overlapping community detection method,based on the local structure information of the node,it has strong scalability in the consumption of community expansion time and space,and is suitable for large-scale networks.However,most local overlapping community detection algorithms use all nodes that do not belong to the community as the expansion set when the community expands,which increases the complexity of the algorithm and reduces the efficiency of the algorithm.In addition,most algorithms lack effective seed node selection methods and community expansion methods,which lead to low-quality overlapping community structures or use a lot of prior information about real community structures.At the same time,due to the randomness of seed node selection,most overlapping community detection methods have instability problems in community structure,and cannot obtain community structures with different levels and different granularities.This is important for observing community structure and understanding the relationship between community hierarchical structures.Aiming at these two problems,this dissertation proposes a method for detectioning overlapping communities based on local information expansion.The main research contents of this dissertation are as follows:1.This dissertation proposes an overlapping community detection method(HTOCD)based on non-binary tree hierarchical clustering,which is mainly aimed at the problem that the overlapping community detection algorithm is unstable and the community hierarchy cannot be obtained.This method first uses the similarity between nodes in the network to select initial particles(seed nodes),and secondly uses nodes that do not belong to the community to expand the community.At the same time,the process forms a non-binary tree.For the expanded community,the community will be merged in accordance with the merger conditions.Regarding the merged community as a node,rebuild the network and re-execute the above steps until there is only one node in the network.Finally,the modularity of overlapping communities is used as the evaluation index of overlapping communities,and the layer with the largest value is selected as the result of overlapping communities.The experimental results on real complex network data sets show that this method can obtain real and reliable overlapping communities,and the non-binary tree hierarchy can more intuitively see the community structure of different levels and different granularities.2.This dissertation proposes an overlapping community discovery method(MSD)based on the expansion of subgraph density,which mainly addresses the problem of low efficiency of community expansion in the overlapping community discovery algorithm.This method first abstracts the network of the community to be divided into an abstract network connected by nodes;according to the connection properties of the nodes,the degree of each node is obtained,the node with the largest degree is used as the seed node,and the neighbor nodes of the seed node are added to initialized community;repeat the above division method for the remaining nodes until there are no undivided nodes in the abstract network;secondly,all communities are sorted from large to small,and small communities are judged based on the relationship between the contribution of non-overlapping nodes to the community and the community density whether the nodes in can be added to the large community to expand the initial community;finally,judge whether the expanded community meets the merge condition,merge the communities that meet the merge condition,and output the result of community division.Experimental results show that this method achieves better performance.