Download files
Abstract
Due to the strong expressive power of the graph model, many real-world applications model data and relationships among the data as a graph, and significant research efforts have been devoted towards efficiently and effectively managing and analyzing graph data. Among them, mining and querying cohesive subgraph structure in massive networks is of great importance for a deeper understanding and better management of such networks. However, the massive graph volume and rapid evolution present huge challenges, which need highly efficient solutions. In this thesis, we study three important problems in mining cohesive subgraph structure in massive networks, and designs efficient and scalable solutions.
Firstly, We study the problem of structural graph clustering. We develop a new two-step paradigm for scalable structural graph clustering based on our three new observations. Then, we present a pSCAN approach, and propose optimization techniques to speed up checking whether two vertices are structure-similar. Moreover, we also propose efficient techniques for updating the clusters when the input graph dynamically changes.
Secondly, we formulate and investigate the problem of diversified top-k community detection over labeled graphs. We introduce a model, called special-interest-group, to enforce both structural cohesiveness and focused interests of a community. We prove that computing the top-1 community is NP-hard. Nevertheless, we propose effective pruning techniques to efficiently enumerate all communities in a graph, based on which we then select diversified top-k communities in a greedy manner. We prove that our algorithm computes the top-k communities approximately but with a guaranteed approximation ratio.
Finally, we study the problem of efficiently computing a maximum independent set from a large graph G (a maximum clique in the complement graph of G). We develop a Reducing-Peeling framework which iteratively reduces the graph size by applying reduction rules on vertices with very low degrees (Reducing) and temporarily removing with the highest degree (Peeling) if the reduction rules cannot be applied. Secondly, based on our framework we design two baseline algorithms, a linear-time algorithm and a near-linear time algorithm, by designing new reduction rules and developing techniques for efficiently and incrementally applying reduction rules.