Community Mining Algorithms On Large-scale Social Networks

Mining densely connected community structure from a graph is a fundamental technique which has many important commercial values and social benefits.Recently,with the increasing of network data size,the complexity of community search is getting higher and higher,which urgently needs to develop some scalable community search algorithms to support it.This thesis deeply analyzes the challenges faced by the current community search technology for large-scale graph data,and proposes two community-mining methods.The first one is a MapReduce based algorithm,called MRSCAN,and another one is the k-core-truss model.Specifically,the main contribution of this thesis consists of two parts:?1?We propose a MRSCAN algorithm for community detection.Graph structural clustering?SCAN?is a well-known density-based graph clustering algorithm.Different from traditional clustering algorithm,the SCAN algorithm can not only find the clusters in a graph,but it also able to identify hub nodes and outliers,which is very important for many practical applications.However,with the growing of graph size,the traditional SCAN algorithm is very hard to handle massive graph data,as its time complexity is O(m^1.5)?m is the number of edges in the graph?.As a result,it is intractable to handle a large-scale graph with several millions of nodes and edges.To overcome the scalability issue of the SCAN algorithm,we propose a MapReduce-based graph structural clustering algorithm,called MRSCAN.First,MRSCAN calculates the structural similarities between the nodes as well as the core nodes in a distributed manner.Then,we propose a new concept of expanding the core node dimensions.Specifically,in order to merge the core nodes and their direct reachable neighbors,we expand the dimensions of the core nodes.Finally,we propose two distribution algorithms for merging clusters.The first one is the basic algorithm,and the second one is an improved algorithm based on a min-core labeling technique.We conduct extensive experiments using several massive graphs,and the results demonstrate the efficiency and scalability of the MRSCAN algorithm.?2?We propose a new community subgraph model called k-core-truss.The k-core-truss model can overcome the limitations of the traditional k-core and k-truss models.Based on the k-core-truss model,we develop a fast community search algorithm for one or multple users query on massive social networks.Except for the community query problem,we also extend our techniques to find densely-connected subgraphs on social graphs.We conduct extensive experiments on several real-life graph datasets,and the results show the accuracy,efficiency,and scalablity of the proposed model and algorithms.