External-memory network analysis algorithms for naturally sparse graphs

Abstract. In this paper, we present a number of network-analysis al-gorithms in the external-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 this sparsity property holds for any subgraph of such a graph. We give efficient external-memory algorithms for the following problems for such graphs: 1. Finding an approximate d-degeneracy ordering. 2. Finding a cycle of length exactly c. 3. Enumerating all maximal cliques. Such problems are of interest, for example, in the analysis of social networks, where they are used to study network cohesion.