Tag Archives: dense subgraph discovery

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 […]

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. […]