External-memory network analysis algorithms for naturally sparse graphs

DOI10.1007/978-3-642-23719-5_56MaRDI QIDQ3092269zbMATH OpenOpenAlexFDO

Authors Paweł Pszona, Michael T. Goodrich

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.6336

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we present a number of network-analysis algorithms 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: - Finding an approximate d-degeneracy ordering; - Finding a cycle of length exactly c; - 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.

Recommendations

• Listing all maximal cliques in large sparse real-world graphs
• scientific article; zbMATH DE number 910869
• (Semi-)External Algorithms for Graph Partitioning and Clustering
• Parallel maximum clique algorithms with applications to network analysis
• Computing the degeneracy of large graphs

Cited in

(5)

• Exploiting the formation of maximal cliques in social networks
• Efficient data structures for sparse network representation
• Computing the degeneracy of large graphs
• On linear algebraic algorithms for the subgraph matching problem and its variants
• Brief announcement: improved massively parallel triangle counting in O(1) rounds

This page was built for publication: External-memory network analysis algorithms for naturally sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3092269)