External-Memory Network Analysis Algorithms for Naturally Sparse Graphs

摘要

In this paper, we present a number of network-analysis algorithms in theexternal-memory model. We focus on methods for large naturally sparse graphs,that is, n-vertex graphs that have O(n) edges and are structured so that thissparsity property holds for any subgraph of such a graph. We give efficientexternal-memory algorithms for the following problems for such graphs: -Finding an approximate d-degeneracy ordering; - Finding a cycle of lengthexactly c; - Enumerating all maximal cliques. Such problems are of interest,for example, in the analysis of social networks, where they are used to studynetwork cohesion.