Structural community detection in big graphs

Wen, Dong

Structural community detection in big graphs

Wen, Dong

Permalink

Publication Type:: Thesis
Issue Date:: 2018

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download contents and abstractAdobe PDF (269.2 kB)

Adobe PDF

Download thesisAdobe PDF (1.3 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Wen, Dong
dc.date.accessioned	2019-05-08T00:13:45Z
dc.date.available	2019-05-08T00:13:45Z
dc.date.issued	2018
dc.identifier.uri	http://hdl.handle.net/10453/133168
dc.description	University of Technology Sydney. Faculty of Engineering and Information Technology.	en_AU
dc.description.abstract	Community detection in graphs is a fundamental problem widely experienced across industries. Given a graph structure, one popular method to identify communities is classifying the vertices, which is formally named graph clustering. Additionally, community structures are always dense and highly connected in graphs. There are also a large number of research works focusing on mining cohesive subgraphs for community detection. Even though the community detection problem is extensively studied, challenges still exist. With the development of social media, graphs are highly dynamic, and the size of graphs is sharply increasing. The large time and space cost of traditional solutions may hardly be endured in big and dynamic graphs. In this thesis, we propose an index-based algorithm for the structural graph clustering (SCAN). Based on the proposed index structure, the time expended to compute structural clustering depends only on the result size, not on the size of the original graph. The space complexity of the index is bounded by 𝑂(𝑚), where m is the number of edges in the graph. We also propose algorithms and several optimization techniques for maintaining our index in dynamic graphs. For the cohesive subgraph detection, we study both degree-constrained (𝑘-core) and connectivity-constrained (𝑘-VCC) cohesive subgraph metrics. A 𝑘-core is a maximal connected subgraph in which each vertex has degree at least 𝑘. We study I/O efficient core decomposition following a semi-external model, which only allows vertex information to be loaded in memory. We propose an optimized I/O efficient algorithm for both core decomposition and core maintenance. In addition, we extend our algorithm to compute the graph degeneracy order, which is an important graph problem that is highly related to core decomposition. A 𝑘-vertex connected component (𝑘-VCC) is a connected subgraph in which the removal of any 𝑘 − 1 vertices will not disconnect the subgraph. A 𝑘-VCC has many outstanding structural properties, such as high cohesiveness, high robustness, and subgraph overlapping. The state-of-the-art solution enumerates all 𝑘-VCCs following a partition-based framework. It requires high computational cost in connectivity tests. We prove the upper bound of the number of partitions, which implies the polynomial running time of this framework. We propose two effective optimization strategies, namely neighbor sweep and group sweep, to largely reduce the number of local connectivity tests. We conducted extensive performance studies using several large real-world datasets to show the efficiency and effectiveness of all our approaches.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/133168/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.subject	Community detection.
dc.subject	Cluster graph.
dc.subject	Algorithm.
dc.subject	Vertex.
dc.subject	Polynomial time.
dc.subject	Core decomposition.
dc.title	Structural community detection in big graphs	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	open_access

Abstract:

Community detection in graphs is a fundamental problem widely experienced across industries. Given a graph structure, one popular method to identify communities is classifying the vertices, which is formally named graph clustering. Additionally, community structures are always dense and highly connected in graphs. There are also a large number of research works focusing on mining cohesive subgraphs for community detection. Even though the community detection problem is extensively studied, challenges still exist. With the development of social media, graphs are highly dynamic, and the size of graphs is sharply increasing. The large time and space cost of traditional solutions may hardly be endured in big and dynamic graphs. In this thesis, we propose an index-based algorithm for the structural graph clustering (SCAN). Based on the proposed index structure, the time expended to compute structural clustering depends only on the result size, not on the size of the original graph. The space complexity of the index is bounded by 𝑂(𝑚), where m is the number of edges in the graph. We also propose algorithms and several optimization techniques for maintaining our index in dynamic graphs. For the cohesive subgraph detection, we study both degree-constrained (𝑘-core) and connectivity-constrained (𝑘-VCC) cohesive subgraph metrics. A 𝑘-core is a maximal connected subgraph in which each vertex has degree at least 𝑘. We study I/O efficient core decomposition following a semi-external model, which only allows vertex information to be loaded in memory. We propose an optimized I/O efficient algorithm for both core decomposition and core maintenance. In addition, we extend our algorithm to compute the graph degeneracy order, which is an important graph problem that is highly related to core decomposition. A 𝑘-vertex connected component (𝑘-VCC) is a connected subgraph in which the removal of any 𝑘 − 1 vertices will not disconnect the subgraph. A 𝑘-VCC has many outstanding structural properties, such as high cohesiveness, high robustness, and subgraph overlapping. The state-of-the-art solution enumerates all 𝑘-VCCs following a partition-based framework. It requires high computational cost in connectivity tests. We prove the upper bound of the number of partitions, which implies the polynomial running time of this framework. We propose two effective optimization strategies, namely neighbor sweep and group sweep, to largely reduce the number of local connectivity tests. We conducted extensive performance studies using several large real-world datasets to show the efficiency and effectiveness of all our approaches.

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

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