Hairball Graphs (data)

Dataset Description

A simple model generating random graphs with cohesive groups that are connected into a small world is the planted partition model (PPM).

Let ${𝒞}=\{C_1,\dots ,C_k\}$ be a partition of $V$ for a graph $G=(V,E)$. Then ${𝒞}$ is called a clustering of $G$ with class $c(v)\in {𝒞}$ for a vertex $v\in V$. The probability of an edge $(u,v)$ is $p_{\text{in}}$ if $c(u)=c(v)$ and $p_{\text{out}}$ if $c(u)\ne c(v)$.

$p(u,v)=\{\begin{array}{ll}{p}_{\text{in}}& \text{if }c(u)=c(v)\text{ (intra-cluster)}\\ p_{\text{out}}& \text{if }c(u)\ne c(v)\text{ (inter-cluster)}\end{array}.$

We generated 50 graphs from a PPM with $500$ vertices, $k=9$, $p_{in}=0.3$, and $p_{out}=0.01$. On top of that, we ran a random noise model with $p_{in}=p_{out}=0.1$ to obfuscate the underlying groups. The resulting graphs are very dense, have a low diameter, and are real hairballs without any visible structure when laid out using force-directed methods.

Download

graphml format: Hairball-Graphs-PPM500.zip (11 MB)