Finding The Community Structure In Online Social Networks Based On The Mechanical Model

Online social network dates from the early E-mail network, after several generations of development by the BBS network, the blog network and the instant messaging network, it becomes a huge social network consist of massive user nodes. Community structure is widespread in the real network and OSN. Finding the community structure in OSN is the foundation to understand the overall network structure, it is also one of the most important problem in the field of the research of OSN. The traditional community discovery algorithm can not be applied to large-scale online social networks due to the high complexity of the algorithm. To meet this end, we propose the mechanical model of online social networks, and design a heuristic community discovery algorithm based on the mechanical model. The algorithm start from the local perspective, establish heuristic rules, accept nodes that are complied with the rules join into the community gradually.We introduce the mechanical model, it is the abstract of the community evolution. The core idea is that the community structure is the result of the movement of the nodes; moreover, community evolution can be divided into stages. Initialization phase, the community structure is unstable, the community grow slowly; rapid expansion phase, the nodes can quickly move closer to the community, the community quickly formed.Based on the mechanical model, we design and implement a heuristic algorithm. The algorithm using different strategies at different stages of community evolution. The initialization phase select the most powerful node into the community; rapid expansion phase, establish heuristic rules, the nodes that are complied with the rules join into the community at the same time. Setting up the heuristic algorithm accelerate the formation of the Community.Running the algorithm on Sina Weibo user data sets and Zachary karate club network data set and so on. The traditional data sets are used to validate the algorithm accuracy; microblogging data set is used to test the performance of the algorithm. The experimental results show that the community discovery algorithm based on the mechanical model has higher classification accuracy, excellent time performance, suitable for large-scale online social network.