Cohesive Subgraph Computation in Graphs

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.

Grantor dc:publisher

UNSW, Sydney

Year dc:date

2020

Author dc:creator

• Zhang, Chen

• Graph model
• Cohesive subgraph computation

Statement dc:rights

• open access
• CC BY-NC-ND 3.0
• free_to_read

Licence

• https://purl.org/coar/access_right/c_abf2
• https://creativecommons.org/licenses/by-nc-nd/3.0/au/

Language dc:language

EN

Identifier

https://doi.org/10.26190/unsworks/21659

OAI identifier oai:identifier

oai:unsworks.library.unsw.edu.au:1959.4/65002