graph algorithms
-
Improved Algorithms for Edge Colouring in the W-Streaming ModelPaul Liu and Moses Charikar
[pdf] [slides] [video]In the W-streaming model, an algorithm is given $O(n \text{polylog} n)$ space and must process a large graph of up to $O(n^2)$ edges. In this short note we give two algorithms for edge colouring under the W-streaming model. For edge colouring in W-streaming, a colour for every edge must be determined by the time all the edges are streamed. Our first algorithm uses $\Delta+o(\Delta)$ colours in $O(n \log^2 n)$ space when the edges arrive according to a uniformly random permutation. The second algorithm uses $(1+o(1))\Delta^2/s$ colours in $\tilde{O}(ns)$ space when edges arrival adversarially.
-
Retrieving Top Weighted Triangles in GraphsRaunak Kumar*, Paul Liu*, Moses Charikar, Austin Benson
[pdf] [code] [poster] [slides]
Pattern counting in graphs is a fundamental primitive for many network analysis tasks, and a number of methods have been developed for scaling subgraph counting to large graphs. Many real-world networks carry a natural notion of strength of connection between nodes, which are often modeled by a weighted graph, but existing scalable graph algorithms for pattern mining are designed for unweighted graphs. Here, we develop a suite of deterministic and random sampling algorithms that enable the fast discovery of the 3- cliques (triangles) with the largest weight in a graph, where weight is measured by a generalized mean of a triangle’s edges. For example, one of our proposed algorithms can find the top-1000 weighted triangles of a weighted graph with billions of edges in thirty seconds on a commodity server, which is orders of magnitude faster than existing “fast” enumeration schemes. Our methods thus open the door towards scalable pattern mining in weighted graphs.
-
Sampling Methods for Counting Temporal MotifsPaul Liu, Austin Benson, Moses Charikar
[pdf] [code] [poster] [slides]
Subgraph isomorphism is a classic and well studied problem in computer science. However, modern graph datasets now contain richer structure, and incorporating temporal information in particular has become a key part of network analysis. In this work we develop fast sampling algorithms for temporal motif counting (subgraph isomorphism where the subgraph must have edges appearing in a specific order). Our results show that we can achieve one to two orders of magnitude speedup over existing algorithms with minimal and controllable loss in accuracy on a number of datasets.