The authors present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local number of triangles in a fully-dynamic graph represented as an adversarial stream of edge insertions and deletions.
Given a large graph, the authors we aim at producing a concise lossy representation (a summary) that can be stored in main memory and used to approximately answer queries about the original graph much faster than by using the exact representation.
The ABRA suite of algorithms computes and maintains high-quality approximations of the betweenness centrality of all nodes or edges on static and fully dynamic graphs.
TRIÈST is a suite of sampling-based, one-pass algorithms for approximate triangle counting from fully-dynamic edge streams.
Comparing big graph centrality measures, approximation algorithm quality guarantees, and the trade-offs and scalability behaviors of distributed algorithms.
The authors present an algorithm to help detect new information and events in a network by computing an optimal probing schedule that minimizes the average novelty of undetected items.