# Huge Graph Visualization

% Remco Bloemen % 2014-05-07

\newcommand{\bindingOperator}[3]{\mathrm{#1}^{#3}_{#2}} \newcommand{\set}[1]{\mathcal #1} \newcommand{\Σ}[2][]{\bindingOperator{{\scriptstyle\raise{.2em}\sum}}{#1}{#2}}

## The plan

- Sort nodes so that related nodes are closest
- Points along a space filling curve

Rapid Graph Layout Using Space Filling Curves http://vis.cs.ucdavis.edu/papers/muelder_ma_rgl_2008.pdf Network data frequently arises in a wide variety of fields, and node-link diagrams are a very natural and intuitive represen- tation of such data. In order for a node-link diagram to be effective, the nodes must be arranged well on the screen. While many graph layout algorithms exist… Large-Scale Graph Visualization and Analytics http://vis.cs.ucdavis.edu/papers/computer2013-graphvis.pdf Novel approaches to network visualization and analytics use sophisticated metrics that enable rich interactive network views and node grouping and filtering. A survey of graph layout and simplification methods reveals considerable progress in these new directions. "Fast Modularity" Community Structure Inference Algorithm http://cs.unm.edu/~aaron/research/fastmodularity.htm This page documents and supports the fast modularity maximization algorithm I developed jointly with Mark Newman and Cristopher Moore. This algorithm is being widely used in the community of complex network researchers…

## The Peano-Gosper curve

### Producing the curve

The matrix

$$ \frac{1}{14} \begin{bmatrix} -\sqrt{3} & 5 \\ 0.2474 & 4 \end{bmatrix} $$

The source

```
static const double CAsin = -0.12371791482634837810910331010756231192448608955788433057541; // -sqrt(3) / 14
static const double CAcos = 5.0 / 14.0;
static const double CBsin = 0.247435829652696756218206620215124623848972179115768661150829;
static const double CBcos = 2.0 / 7.0;
```

### The Flowsnake in C++

Aperiodic space-filling curves?

Write a curve in recursive aperiodic titles? https://en.wikipedia.org/wiki/Penrose_tiling

Alternative:

Place points using Poisson disk. Create a weighted graph out of the distances. Apply linearisation to the weight matrix. Now the points are sorted and can be used as in the space-filling case.

https://en.wikipedia.org/wiki/Low-discrepancy_sequence

### Full graph

This reminds me of electron diffraction patterns in crystals, also very beautiful.

Right, back to our main goal.

### Locality

The graph has roughly 17 thousand nodes and 34 thousand edges.

## Test data

## Walktrap ordering

## Balancing the binary tree

Let’s now look at the community hierarchy:

## Sorting the binary tree

## Separating the communities

Compared to the first plot, the community structure suffered from sorting, because now the interacting communities are forced closer together.

TODO:

- Recursive cluster