Research On Social Network Community Detection Mechanism

Complex network generally refers to the number of nodes is large and the interactions between nodes is frequent. Community structure is one of the characteristics of complex network topology, the network is constituted by a number of communities, internal nodes of community interact frequently,while the nodes between the communities interact weakly. How to extract the community structures from the complex network has become a hot area of research.With the size of the network increasing, especially the rise of Facebook, Twitter, microblogging and other social website, not only the complexity of the algorithm proposed to be high efficient, but also introduced the requirement of algorithm parallelization. Because most of the community do not have parallel ability, it will be difficult to meet the computing needs of large amounts of data in complex networks. This paper aims at disjoint community and overlapping community, to realize efficient parallel computing needs in large-scale network analysis.In this paper, for the calculation of the propinquity matrix, a new optimization approach is dynamic threshold adjustment, which can enhance the accuracy of the algorithm. The introduction of the process for calculating the propinquity matrix of the different weights set, and adds to support for the weighted graph.For disjoint community, the algorithm proposed two.One is detection algorithm CKE(Community Detection based on Key Nodes Extracting) and the other is SKC(Spectral K-Means Cluster based Detection). While, CKE algorithm uses approximate betweenness algorithm combined with the propinquity of node pairs to obtain key set of nodes.And then, perform BFS algorithm to detect communities. The simulation can be proved, CKE algorithm can accurately find key set of nodes, and detect the community accurately. SKC algorithm based on clustering idea.By the propinquity matrix, SKC use spectral clustering to convert utility matrix, and use Canopy clustering to init K value and initial center nodes.For overlapping communities, community detection algorithm proposed two: CCO(Core-clique Combination Optimization detection algorithm) and IMB(Iterative diffusion Mark based on high-Betweenness) algorithms. CCO algorithm use central node as the initial set, extract node to high cohesion cluster. IMB algorithm places a high betweenness set of nodes,which has weak correlation. Algorithm flag the neighbors of node continuously, and finally get the overlapped communities.To achieve efficient parallel computing on the large-scale network analysis, we need to import BSP model as parallel model implementation, and the Hadoop as distributed computing framework. Therefore, this paper also discusses how to be executed on the Hadoop.