Research On Static And Dynamic Community Division Algorithm Based On Similarity Voting And Information Transmission

In real life there are all kinds of social networks,such as routing autonomous network,scientist cooperation network,Twitter user relationship network.As early as 1969,the research on social networks began.The study found that social networks have inherent characteristics of small world nature,degrees of power distribution and community structure.Due to the immense practical value of social networks,this area attracts in-depth research by biologists,sociologists,computer scientists and others.Community structure has become the focus of researchers due to its huge practical value such as terrorist tracking,personalized recommendation and public opinion control.With the continuous exploration and innovation of researchers,a series of methods of community division are put forward constantly,and certain achievements have been made in the community structure.However,with the rapid development of science and technology,the scale of social networks has rapidly expanded.For example,some social networks have hundreds of millions of users,making it difficult for most current community partitioning algorithms.The high time overhead is the main reason that many algorithms cannot divide the community on the large-scale social network.In this paper,the Community Division Algorithm Based on Similarity Voting(CDBSV algorithm)is proposed to meet this pressing need.The CDBSV algorithm uses the local similarity between neighboring nodes in combination with the voting mechanism to quickly complete the initial division of the community so that the scale of large-scale social network can be rapidly reduced,and then the iterative community division can be iterated on the smaller-scale social network using the modularity increment criterion until get the community with the largest module degree.The CDBSV algorithm utilizes the local similarity between neighboring nodes a nd the voting mechanism to quickly complete the initial division of the community so that the scale of the large-scale social network can be rapidly reduced,and then iteratively uses the modularity increment criterion on the smaller-scale social network to carry out the community divide until get the community with the largest modularity.The CDBSV algorithm uses the simple local similarity calculation and the voting mechanism to make the first phase of the algorithm realize the rapid reduction of the network while ensuring the module degree.After reducing the size of the network,we can use the modularity increment criterion which is more accurate but slightly more complex to carry on the further division to obtain the maximum modularity,so as to complete the community division of the large-scale social network.In exploring the social structure of social networks,researchers have noticed that with the gradual passage of time,social networks are constantly changing,and the relationship among nodes is not static.There are nodes in the social network that are newly added and disappeared.Although social networks are slowly changing,their community structure tends to be stable or little changed in a relatively short period of time.Therefore,by studying in detail the relationship between community structure and nodes and the impact of node changes on community structure,an incremental dynamic partitioning algorithm is proposed to complete the rapid division of social networks.Dynamic Partitioning Algorithm Base on Information Transmission(DPBIT algorithm)to use the incremental network to modify the community to complete the division of the new community.By analyzing the impact of node changes on the adjacency community modularity to determine the communities to which their neighbors may be segmented,the information about the changes in nodes is passed to their neighbors instead of directly testing all possible neighborhoods of neighboring nodes to speed up algorithm.Finally,the validity of CDBSV algorithm and DPBIT algorithm is verified on real social network.The experimental results show that CDBSV algorithm is suitable for large-scale social network community partitioning task.The algorithm has higher accuracy and time efficiency than the existing algorithms.Compared with other dynamic algorithms,DPBIT algorithm can complete the community division of social network more efficiently and has higher modularity,and also outperforms the traditional static community partitioning algorithm in time efficiency.