Please use this identifier to cite or link to this item:
Title: Enumeration of substructure patterns from large graphs
Authors: Chu, Shumo.
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2013
Abstract: Graph is a ubiquitous data model and can be used to represent complex entities and their relationships, such as bioinformatics and biochemistry networks, traffic networks, communication networks, social networks, etc. This thesis study the problem of enumeration of fundamental substructure patterns in graphs. The enumeration of substructure patterns of graphs plays an important role in network analysis, since these problems are crucial to the understanding of complex networks and integral parts of many more advanced techniques of graph analysis. In recent years, we have seen a dramatic increase in the number, the size, and the variety of networks. For example, there are over 800 million active users in Facebook and there are over 1 billion webpages in WWW according to Google. How to handle big data becomes a very challenging problem for graph analysis. Due to the large volume, large graphs cannot fit into main memory of a single computer any longer. And due to the huge gap between the efficiency of accessing data from external memory and from main memory, (in terms of bandwidth and random access time), existing algorithms on enumerating substructures become inefficient or even infeasible for large graphs. In this thesis, we study the problem of enumerating substructures of large disk-resident graph. We make the following major contributions. -We developed the first I/O-efficient algorithms for listing triangles in massive networks and applied them in the computation of clustering coefficient, transitivity, triangular connectivity, etc. For the same dataset, our algorithm outperform existing algorithm by orders of magnitude. -We developed a general algorithm framework to guarantee performance in networks with different characteristics and worked out a non-trivial parallel version of this algorithm. This algorithm is up to 1,000 times faster than the state-of-the-art algorithms for clique enumeration in disk-resident networks with a single machine and shows near linear scale up given more machines.
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Theses

Files in This Item:
File Description SizeFormat 
  Restricted Access
Main Article886.91 kBAdobe PDFView/Open

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.