Efficient and Scalable Listing of Four-Vertex Subgraph
Abstract
Identifying four-vertex subgraphs has long been recognized as a fundamental technique in bioinformatics and social networks. However, listing these structures is a challenging task, especially for graphs that do not fit in RAM. To address this problem, we build a set of algorithms, models, and implementations that can handle massive graphs on commodity hardware. Our technique achieves 4 – 5 orders of magnitude speedup compared to the best prior methods on graphs with billions of edges, with external-memory operation equally efficient.
Citation
Xia, Xiangzhou (2016). Efficient and Scalable Listing of Four-Vertex Subgraph. Master's thesis, Texas A & M University. Available electronically from https : / /hdl .handle .net /1969 .1 /174219.