Parallel Iterative Algorithm Of Structural Holes Mining Based On Community Detection On Social Networks

With the rise of Facebook, Twitter and etc, the scale of social networks has become larger and more complex increasingly. Typically, the networks present the distribution of communities and the holes generated by non-redundant relationships between communities. We can learn about the clusters’ distribution and the competitive advantage on networks via analyzing these communities and holes, which is an important basic research for social network analysis and has become a hot topic in academia and industry.Currently, the classical community detect algorithms include GN algorithm proposed by Newman and its improvements, the algorithms based on Q function which is used to evaluate the structure of communities, the algorithms based on clique detection and so on. However, the time complexity of these algorithms is so high that could not apply to processing large social networks. In this thesis, learning from the label propagation mechanism in COPRA algorithm, we simplify the process of community detection and propose a parallel iterative algorithm PCOPRA based on BSP model, then apply it to BC-BSP system. At the same time, aiming at overcoming the disadvantages of COPRA algorithm, we carry out two improvements:(1) In order to avoid label oscillation caused by label synchronous propagation in COPRA which may make the algorithm not to converge, and unstable result of the community detection caused by label asynchronous propagation, we present a semi-asynchronous iterative mechanism of label propagation. Through propagating labels synchronously alternates asynchronously, we can combine the advantages of two iterations which are that making result stable, accelerating the speed of convergence and making better performance. (2) In order to avoid the over-reliance on the unknown global parameter of the networks which may make result inaccurate in COPRA, we decide the parameter of the networks autonomously by judging surrounding communities of each node’s neighborhoods. This method increases the flexibility of the process of the community detection and improves the efficiency of mining. In addition, to support for label iterative update asynchronously, we expand the synchronous mode of BC-BSP system. Through get messages of next super step in advance at current super step, the system can stride update vertices. This mechanism could support rapid process for the applications of incremental iteration, label propragation and so on.People still do not have a complete theory for mining structural holes on social networks, especially mining on large networks. To solve the above problems, we make the following contributions:(1) Based on the results of community detection, and learning from Tang’s HIS model of structural hole, we propose a parallel algorithm PHIS based on BSP model and apply it to BC-BSP system eventually. (2) By analyzing the update rules of the nodes, we optimize the algorithm from two aspects which are that reducing the amount of nodes computed and messages communicated. These improvements make a better performance to a great extent.The parallel algorithms proposed in this thesis are all based on BSP model. The result of experiments shows that these algorithms can detect high-quality communities and structural holes during a short period of time on social networks in large scale.