Hairball Graphs (data)

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

Let ${\mathcal {C}}=\{C_{1},\ldots ,C_{k}\}$ be a partition of $V$ for a graph $G=(V,E)$. Then ${\mathcal {C}}$ is called a clustering of $G$ with class $c(v)\in {\mathcal {C}}$ 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)\neq c(v)$.

$p(u,v)={\begin{cases}p_{\text{in}}&{\mbox{if }}c(u)=c(v){\text{ (intra-cluster)}}\\p_{\text{out}}&{\mbox{if }}c(u)\neq c(v){\text{ (inter-cluster)}}\end{cases}}.$

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.