Efficient Subgraph Computing on Large-Scale Graphs

The problem of efficiently computing subgraphs has received much attention from the database research community. In this thesis, we study important problem of efficient graph analysis at a large scale. Three subgraph computation problems are studied. These problems are (1) Triangle Listing, (2) Batch-dynamic Triangle Listing, and (3) Historical K-cores. The first problem, triangle listing, has a fundamental and theoretical significance in graph analytics. Efficient solutions often leverage the orientation framework: the mapping of an undirected graph into a directed acyclic graph for a specified global vertex ordering. We put forward improvement to this framework and present an adaptive orientation technique that satisfies the orientation technique but refines it by selectively traversing incident edges based on the out-degree of the vertices in the oriented graph as the computation of triangles is conducted. The second problem, batch-dynamic triangle listing, studies triangle listing in the context of batch-dynamic graphs. The setting differs from the former by an additional parameter of a batch-update of edges, where only updated triangle solutions are the relevant output for our problem setting. In this thesis, we notice that this problem has yet to be studied systematically and propose an efficient algorithm which (1) only outputs updated triangles and (2) ensures that each triangle solution is identified without the presence of any duplicate solutions. The final problem, historical K-cores, studies the k-cores in temporal graphs where each edge is associated with a timestamp representing its occurrence. We propose and study the efficient querying historical k-cores in temporal graphs. Given an integer k and a time window, we study the problem of computing all k-cores in the graph snapshot over the time window