Cohesive Subgraph Computation in Graphs

Download files
Access & Terms of Use
open access
Copyright: Zhang, Chen
Altmetric
Abstract
For many years, graph model has been an important vehicle to many real-world applications. Significant research efforts have been devoted towards efficiently and effectively managing and analysing 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 spatial clique enumeration. Maximal clique enumeration is a fundamental problem in graph database. In this chapter, we investigate this problem in the context of spatial database. We give the definition of clique on spatial graph and propose a backtracking method with pruning techniques based on geometric properties of maximal spatial clique to significantly enhance the computing time. Secondly, we formulate and investigate the problem of skyline k-clique enumeration. We give the skyline k-cliques model over multi-valued attributed graphs and develop efficient algorithms to conduct the computation. To verify the group based dominance between two k-cliques, we make use of maximum bipartite matching and develop a set of optimization techniques to improve the verification efficiency. Then, a progressive computation algorithm is developed which enumerates the k-cliques in an order such that a k-clique is guaranteed not to be dominated by those generated after it. Novel pruning and early termination techniques are developed to exclude unpromising nodes or cliques by investigating the structural and attribute properties of the multi-valued attributed graph. Thirdly, we study the problem of efficiently computing (k,p)-core in graph networks. In this chapter, we propose and study a novel cohesive subgraph model, named (k,p)-core, which is a maximal subgraph where each vertex has at least k neighbours and at least p fraction of network neighbours in the subgraph. We propose an algorithm for(k,p)-core computation and an novel index for (k,p)-core search.
Persistent link to this record
Link to Publisher Version
Link to Open Access Version
Additional Link
Author(s)
Zhang, Chen
Supervisor(s)
Lin, Xuemin
Zhang, Wenjie
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2020
Resource Type
Thesis
Degree Type
PhD Doctorate
UNSW Faculty
Files
download public version.pdf 2.68 MB Adobe Portable Document Format
Related dataset(s)