Cohesive Subgraph Detection on Large Graphs

Yang, Bohua

Cohesive Subgraph Detection on Large Graphs

Yang, Bohua

Permalink

Publication Type:: Thesis
Issue Date:: 2021

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download contents and abstractAdobe PDF (276.95 kB)

Adobe PDF

Download thesisAdobe PDF (1.79 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Yang, Bohua
dc.date.accessioned	2022-01-19T00:41:20Z
dc.date.available	2022-01-19T00:41:20Z
dc.date.issued	2021
dc.identifier.uri	http://hdl.handle.net/10453/153326
dc.description	University of Technology Sydney. Faculty of Engineering and Information Technology.	en_US.UTF-8
dc.description.abstract	Graphs have been widely used to model sophisticated relationships between different entities due to their strong representative properties. Social networks, traffic networks, and biological networks are among the applications that benefit from being expressed as graphs. The cohesive subgraph is an essential structure for understanding the organization of many real-world networks, and cohesive subgraph detection is a crucial problem in network analysis. There are many cohesive subgraph models, such as k-core, strongly connected component, and maximum density subgraph. Uncertain graph management and analysis have attracted much research attention. Among them, computing k-cores in uncertain graphs (aka, (k, eta)-cores) is an important problem and has emerged in many applications. However, the existing algorithms for computing (k, eta)-cores heavily depend on the two input parameters k and eta. In addition, computing and updating the eta-degree for each vertex is the costliest component in the algorithm, and the cost is high. To overcome these drawbacks, we propose an index-based solution for computing (k, eta)-cores. The index size is well-bounded by O(m), where m is the number of edges in the graph. Based on the index, queries for any k and eta can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also discuss the (k, eta)-core computation when graphs cannot be entirely stored in memory. We adopt the semi-external setting, which allows O(n) memory usage, where n is the number of vertices in the graph. This assumption is reasonable in practice, and it has been widely adopted in massive graph analysis. We design an index-based solution for I/O efficient (k, eta)-core computation. Given the frequent updates in many real-world graphs, detecting strongly connected components (SCC) in dynamic graphs is a very complicated problem. In the thesis, we study the fully dynamic depth-first search (DFS) problem in directed graphs, which is a crucial basis of dynamic SCC detection. In the literature, most works focus on the dynamic DFS problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on several large real-world graphs to practically evaluate the performance of all proposed algorithms.	en_US.UTF-8
dc.format	Thesis (PhD)
dc.language.iso	en_US	en_US.UTF-8
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/153326/2/02whole.pdf
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	au.edu.uts.lib/ppc
dc.rights	info:eu-repo/semantics/openAccess
dc.title	Cohesive Subgraph Detection on Large Graphs	en_US.UTF-8
dc.type	Thesis
utslib.copyright.status	open_access	*

Abstract:

Graphs have been widely used to model sophisticated relationships between different entities due to their strong representative properties. Social networks, traffic networks, and biological networks are among the applications that benefit from being expressed as graphs. The cohesive subgraph is an essential structure for understanding the organization of many real-world networks, and cohesive subgraph detection is a crucial problem in network analysis. There are many cohesive subgraph models, such as k-core, strongly connected component, and maximum density subgraph. Uncertain graph management and analysis have attracted much research attention. Among them, computing k-cores in uncertain graphs (aka, (k, eta)-cores) is an important problem and has emerged in many applications. However, the existing algorithms for computing (k, eta)-cores heavily depend on the two input parameters k and eta. In addition, computing and updating the eta-degree for each vertex is the costliest component in the algorithm, and the cost is high. To overcome these drawbacks, we propose an index-based solution for computing (k, eta)-cores. The index size is well-bounded by O(m), where m is the number of edges in the graph. Based on the index, queries for any k and eta can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also discuss the (k, eta)-core computation when graphs cannot be entirely stored in memory. We adopt the semi-external setting, which allows O(n) memory usage, where n is the number of vertices in the graph. This assumption is reasonable in practice, and it has been widely adopted in massive graph analysis. We design an index-based solution for I/O efficient (k, eta)-core computation. Given the frequent updates in many real-world graphs, detecting strongly connected components (SCC) in dynamic graphs is a very complicated problem. In the thesis, we study the fully dynamic depth-first search (DFS) problem in directed graphs, which is a crucial basis of dynamic SCC detection. In the literature, most works focus on the dynamic DFS problem in undirected graphs and directed acyclic graphs. However, their methods cannot easily be applied in the case of general directed graphs. Motivated by this, we propose a framework and corresponding algorithms for both edge insertion and deletion in general directed graphs. We further give several optimizations to speed up the algorithms. We conduct extensive experiments on several large real-world graphs to practically evaluate the performance of all proposed algorithms.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/153326