Research On Local Community Detection Algorithm Based On Monte-Carlo Iterative Solving Strategy

With the wide application of modern information technology,the number of complex networks in sociology,statistical physics,economic management,biology,computer science and other fields has grown rapidly,and the scale of the network has become larger and larger.Analyzing the global structural characteristics of a network has gradually become difficulty.In some application scenarios,people only care about the community to which a particular node belongs,so local community detection has attracted the attention of many researchers.Compared with global community detection,it pays more attention to the local network structure and can return more personalized communities.In this paper,the problems existing in the current local community detection algorithm are studied as follows:1.For static networks,this paper proposes a local community detection algorithm based on Monte-Carlo iterative solution strategy.The existing local community detection algorithm uses a gradual expansion method based on a greedy strategy to detect the target community,which is prone to premature convergence and difficult to obtain all nodes of the target community.In the community expansion stage,the algorithm proposed in this paper assigns selection probability to all adjacent candidate nodes according to the contribution ratio of nodes to the objective function,and randomly selects nodes according to this probability.In order to avoid random selection leading to the expansion direction deviating from the target community,the node elimination mechanism should be triggered according to the community quality decline degree.In the node elimination mechanism,the nodes that have joined are assigned elimination probability according to node similarity,and the nodes are deleted randomly according to the probability.Repeat the above steps until the iteration termination condition is reached.Experimental results show that the performance of the proposed algorithm is greatly improved compared with traditional algorithms.2.For dynamic networks,the algorithm is extended to an incremental dynamic local community detection algorithm.Existing local community detection algorithms usually divide dynamic networks into time slices,and then implement static network local community detection algorithm for network snapshots of each time slice,which will cause a lot of redundant calculation and very low efficiency.In this paper,the local community detection algorithm based on Monte-Carlo iterative solution strategy is firstly used to obtain the initial local community.Then,from the second time slice,based on the local community of the previous time slice network,the corresponding incremental operation is carried out on the local community according to the changes of cohesion and connectedness.The experimental results show that the incremental algorithm can significantly reduce the time cost compared with the static algorithm on the premise of ensuring the quality of the detected local communities.3.Combined with the above research content,a local community detection system is designed and implemented.The system integrates a variety of local community detection algorithms,which can perform local community detection operations on the nodes to be searched in the selected dataset,and visually display the execution results of the algorithms.