Category Graph Algorithms

Denoising binary images

Data science is transforming the world: we already see self-driving cars moving from research to production, data-driven cancer diagnostic systems, machine learning trader bots and lots of other exciting technologies because the corresponding problems have been reduced to understanding data. While the science of data for centuries was known as statistics, computer scientists, together with […]

Writing history in about 20 minutes

    Here is an abstract from an interview with Edsger Dijkstra about his shortest path algorithm. There’s a curious story behind your “shortest path” algorithm. In 1956 I did two important things, I got my degree and we had the festive opening of the ARMAC.c We had to have a demonstration. Now the ARRA, […]

Dense subgraph discovery applications

Recently, I compiled a collection of applications that rely on dense subgraph discovery for my KDD’15 tutorial with Aris Gionis. In general, dense subgraph discovery is a key graph mining primitive. While by “dense” we generally mean subgraphs which are large enough and contain many edges, the exact notion of dense is application dependent.  The […]

Maintaining a random sample of edges on a dynamic graph

Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, […]

k-clique densest subgraph problem

Motivation: Suppose you are given a large “who-calls-whom” network. This is a network where each vertex represents a human and we have an (undirected) edge between two humans if and only if they exchanged a phone call. An important problem that comes up in anomaly detection is finding sets of vertices that “look like” cliques. […]

Giant component with Depth First Search

I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph exhibits a phase transition around . When then the largest component has size […]

Edge-disjoint spanning subgraphs of large degree

Prove the following: you can always find in a simple undirected graph of minimum degree two spanning edge disjoint subgraphs of minimum degree at least . Give also an algorithmic procedure to find such subgraphs.