Main-memory triangle computations for very large (sparse (power-law)) graphs

DOI10.1016/j.tcs.2008.07.017zbMath1152.68045OpenAlexW2016311778MaRDI QIDQ955020

Matthieu Latapy

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.017

zbMATH Keywords

algorithmsgraphscomplex networkstriangles

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Analyzing the maritime transportation system in Greece: a complex network approach ⋮ iTri: index-based triangle listing in massive graphs ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ Efficient Computation of the Weighted Clustering Coefficient ⋮ Leave or not leave? Group members' departure prediction in dynamic information networks ⋮ Scalable approximate Bayesian computation for growing network models via extrapolated and sampled summaries ⋮ Colorful triangle counting and a \textsc{MapReduce} implementation ⋮ Summarized bit batch-based triangle listing in massive graphs ⋮ On linear algebraic algorithms for the subgraph matching problem and its variants ⋮ Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian ⋮ FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams ⋮ An efficient exact algorithm for triangle listing in large graphs ⋮ Main-memory triangle computations for very large (sparse (power-law)) graphs ⋮ Complex Networks and Link Streams for the Empirical Analysis of Large Software ⋮ Parameterized aspects of triangle enumeration ⋮ Why Do Simple Algorithms for Triangle Enumeration Work in the Real World? ⋮ Finding weighted \(k\)-truss communities in large networks ⋮ Complex network filtering and compression algorithm based on triangle-subgraph ⋮ Efficient computation of the Weighted Clustering Coefficient

Uses Software

• Pajek
• UbiCrawler
• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Network analysis. Methodological foundations.
• Color-coding
• Statistical mechanics of complex networks
• Approximating Clustering Coefficient and Transitivity
• Radix Sorting with No Extra Space
• Every monotone graph property is testable
• Arboricity and Subgraph Listing Algorithms
• Finding a Minimum Circuit in a Graph
• Matrix measures for transitivity and balance*
• Coupling Scale-Free and Classical Random Graphs
• Collective dynamics of ‘small-world’ networks
• Algorithms – ESA 2004
• Codes for the World Wide Web
• Experimental and Efficient Algorithms
• Computing and Combinatorics

This page was built for publication: Main-memory triangle computations for very large (sparse (power-law)) graphs