Detravisualizer

A 3D graph layout and visualization tool for large power-law networks, built in C++ with OpenGL. The core contribution is Treecapitator: a degree-based layout algorithm designed specifically for graphs that exhibit small-world characteristics and a power-law degree sequence.

Results

The following renders show Treecapitator running on networks at different scales. Colors encode community structure via degree-propagated HSV assignment; alpha blending exposes connection density even in graphs with tens of millions of edges.

Barabási–Albert, 10 million nodes — structured hubs emerge clearly:

Left: Treecapitator on 10M node BA network (b=120, c=0). Right: Graphia on 1M node BA network. The stock algorithm collapses all nodes into an undifferentiated mass.

Factor Graph, 150,000 nodes — deterministic and randomized variants:

Left: Treecapitator on the Factor Graph model (150k nodes). The divisibility-based structure creates characteristic bubble clusters. Right: Graphia collapses the same network into a featureless ball.

Rendering parameters — alpha and perspective:

Effect of alpha transparency on a dense Barabási–Albert network. Low alpha reveals internal structure that full-opacity rendering hides entirely.

Demo

The Problem with Power-Law Graphs

Real-world networks — social graphs, web link graphs, citation networks, linguistic dependency trees — consistently exhibit a power-law degree distribution: a small number of nodes have very high degree (hubs) while most nodes have very few connections. Formally, for a graph $G = (V, E)$, the degree distribution follows:

$$P(\deg(u) = k) \propto k^{-\gamma}$$

for some exponent $\gamma > 1$.

Standard layout algorithms (force-directed, spring-embedded, Fruchterman–Reingold) treat all nodes equally. Applied to a power-law graph, the high-degree hubs exert enormous attractive forces on their neighbors, pulling the entire network toward the center. The result is an impenetrable central mass with no readable structure.

The five research questions this work set out to answer are:

A New Power-Law Model — Factor Graph

To test the layout at scale, a new synthetic power-law graph generator was built alongside the visualizer. I call it the Factor Graph model.

Traditional power-law models (Barabási–Albert, preferential attachment) simulate network growth step by step: each new node is connected to existing nodes with probability proportional to their degree. This makes large-scale generation expensive.

The Factor Graph instead evaluates edge connectivity between any two nodes in $O(1)$ using a closed-form divisibility rule.

Definition

We first define a labelling function $\ell$ that maps each vertex to a natural number from a continuous range over $[2, |V|]$:

$$\ell : V \xrightarrow{\sim} \{2, 3, 4, \ldots, |V|\}$$

Each node $u$ is associated with a consecutive label starting from 2. The edge set is then defined by a divisibility connectivity rule:

$$E \subset \bigl\{(u,v) \mid \exists\, k \in \mathbb{N} \text{ such that } u = k\, v^\gamma \bigr\}$$

where $\gamma$ is a constant controlling the power-law exponent. This rule connects a pair $(u, v)$ if and only if either $u$ divides $v$ or $v$ divides $u$ in this $\gamma$-weighted sense.

Randomization

To remove the deterministic structure introduced by integer labeling, a hashing function (random bijective mapping) can be applied:

$$E \subset \bigl\{(u,v) \mid \exists\, k \in \mathbb{N} \text{ such that } hash(u) = k\, v^\gamma \bigr\}$$

This randomizes the endpoints while preserving the small-world statistical properties.

Left: deterministic Factor Graph (150k nodes) — the divisibility structure is directly visible as discrete bubble clusters. Right: randomized Factor Graph (50k nodes) — the clustering dissolves under the hash permutation while the heavy-tail degree distribution is preserved.

Statistical Analysis

For a node with label $u$, define the right-neighbor set as all nodes $v$ such that $v^\gamma$ divides $u$:

$$R(u) = \bigl\{v \mid \exists\, k \in \mathbb{N} \text{ such that } v = k\, u^\gamma \bigr\}$$

The expected size of $R(u)$ is the number of values whose $\gamma$-power does not exceed $|V|$:

$$|R(u)| = \lfloor |V| \cdot u^{-\gamma} \rfloor$$

For the left-neighbor set $L(u) = \{v \mid \exists k \text{ such that } u = kv^\gamma\}$, the probability that $i^\gamma$ divides a uniformly random label $U$ is:

$$\mathbb{P}(X_i = 1) = \frac{\lfloor |V| / i^\gamma \rfloor}{|V|} = \frac{1}{i^\gamma} + o(1)$$

Therefore the expected size of $L(u)$ converges when $\gamma > 1$:

$$\mathbb{E}[|L(u)|] = \sum_{i \leq |V|^{1/\gamma}} \mathbb{E}[X_i] \sim \sum_{i=1}^{\infty} \frac{1}{i^\gamma} = O(\zeta(\gamma))$$

The average degree of a vertex then satisfies:

$$\mathbb{E}[\deg(u)] = O(\zeta(\gamma)) + |V| \cdot U^{-\gamma}$$

This establishes the heavy-tail behaviour characteristic of power-law graphs. The model follows a strict power-law distribution until a breaking point beyond which the tail decreases at a lower rate than expected — a 2-regime function that distinguishes it from standard preferential attachment.

Treecapitator — The Layout Algorithm

The algorithm sorts all nodes in descending degree order and processes each node heuristically, looking only at the node's degree and its immediate connections. For each node $u$, it computes three position vectors $A(u)$, $B(u)$, and $C(u)$, then blends them into a final 3D position.

Notation

Let $d_i$ denote the degree of node $i$, and $p_i$ its 3D position. For a node set $S = \{i_1, i_2, \ldots, i_{|S|}\}$ with fixed ordering, define:

$$d(S) = (d_{i_1}, d_{i_2}, \ldots, d_{i_{|S|}})$$

$$p(S) = (p_{i_1}, p_{i_2}, \ldots, p_{i_{|S|}})$$

For each node $u$ we also need $R(u)$ — the set of neighbors with strictly higher degree than $u$:

$$R(u) = \{v \mid v \in N(u) \land d_v > d_u\}$$

Component A(u) — Attraction to Higher-Degree Neighbors

$A(u)$ places a node close to its highest-degree neighbor. The softmin function provides a differentiable approximation to argmin, controlled by temperature $\tau$:

$$\tilde{w}_i = \exp\!\left(-\frac{x_i - \min_j x_j}{\tau}\right), \quad \text{softmin}_\tau(\mathbf{x})_i = \frac{\tilde{w}_i}{\sum_{k=1}^{n} \tilde{w}_k}$$

Then:

$$A(u) = \text{softmin}\!\bigl(D(R(u))\bigr)^\top P(R(u))$$

The rationale is that a low-degree node is unlikely to find a structurally significant connection outside its local hub. Placing it close to the minimum-degree member of $R(u)$ (its most local hub) preserves local topology while allowing hubs to determine the global structure.

Component B(u) — Degree-Proportional Scatter

$B(u)$ spreads nodes away from the origin in a random direction, scaled by parameter $b$:

$$B(u) = \text{randdir}() \cdot b$$

For high-degree nodes, $B(u)$ dominates the final position. This is the mechanism that pushes hubs outward — in direct contrast to force-directed methods that pull hubs toward the center.

Component C(u) — Anti-Determinism Jitter

$C(u)$ adds a small random displacement to prevent degenerate configurations where many nodes share identical adjacency lists and would otherwise collapse to the same position:

$$C(u) = \text{randdir}() \cdot c$$

From the definition $b \gg c$.

Position Blending

The final 3D position for node $u$ is a linear interpolation over the normalized degree $l(u)$:

$$l(u) = \frac{d(u)}{\max(D(V))}$$

$$P(u) = B(u) \cdot l(u) + A(u) \cdot (1 - l(u)) + C(u)$$

For the highest-degree nodes ($l(u) \to 1$), the position is dominated by $B(u)$: they are placed far from the origin in a random direction. For the lowest-degree nodes ($l(u) \to 0$), the position is dominated by $A(u)$: they cluster around their local hubs. The result is a natural hierarchical separation where hub degree directly corresponds to spatial isolation.

Optimization Pass

High-degree hubs placed by $B(u)$ may end up spatially close to unrelated hubs purely by chance. An optional force-directed optimization corrects this for the top-$h$ fraction of degree holders. Select the hub set:

$$H = \{u \mid d_u > \max(D(V)) \cdot h\}$$

Then apply Euler integration of repulsive forces between all pairs in $H$:

$$f_i(u) = \sum_{v \in H \setminus \{u\}} k \cdot \frac{d_u \cdot d_v}{\max(D(V))^2 \cdot \|p_{i-1}(u) - p_{i-1}(v)\|^2}$$

$$v_i(u) = p_{i-1}(u) + v_i(u) \cdot dt, \quad p_i(u) = c\!\left(p_{i-1}(u),\; p_{i-1}(u) + v_i(u) \cdot dt\right)$$

where $c(x, y) = \|x\| \cdot \frac{y}{\|y\|}$ constrains each hub to its initial sphere, preventing scale collapse. Iteration continues until convergence:

$$\sum_{u \in H} \|p_i(u) - p_{i-1}(u)\|^2 < \varepsilon$$

Node Colouring

The colour of a node follows the same positional logic. Define $Ac(u)$ and $Bc(u)$ as analogues to $A(u)$ and $B(u)$ but in HSV colour space (random Hue, fixed Saturation and Value = 1) rather than 3D position space. The final colour:

$$Pc(u) = Ac(u) \cdot (1 - t) + Bc(u) \cdot t$$

where $t = l(u)$. High-degree nodes receive a unique random colour; low-degree nodes inherit a blend of their hub's colour. This allows color to serve as a visual proxy for community membership — nodes connected to the same hub cluster in both space and colour.

Tunable parameters summary:

Results — Synthetic Networks

Networks were generated with the following default parameters unless otherwise noted: $b = 100$, $c = 2$, $\tau = 4$.

Barabási–Albert vs. Erdős–Rényi

The most revealing comparison is between BA and ER models. BA exhibits preferential attachment (power-law), while ER has a binomial degree distribution.

Left: BA model (Treecapitator) — hubs disperse, color communities clearly visible. Right: ER model (p=0.5, Treecapitator) — nodes distribute uniformly on a sphere surface with no structure, correctly reflecting the absence of power-law degree distribution.

This contrast validates the algorithm's design: when there are no hubs ($A(u)$ has no preferred direction), $B(u)$ dominates and all nodes scatter uniformly on a sphere.

Erdős–Rényi — Varying Connectivity Probability

Erdős–Rényi with N=1000 nodes and p ∈ {0.088, 0.5, 0.957}. As p increases (every node approaches the same high degree), the sphere fills in from the inside. Decreasing p scatters sparse nodes outward from an empty center.

Watts–Strogatz — Varying Rewiring Probability β

Watts–Strogatz (N=5000, k=4) with β ∈ {0, 0.1, 1}. At β=0 all nodes share degree 4 and B(u) dominates every position, producing a perfect sphere. As β → 1 (full rewiring toward BA-like structure) internal organization appears.

A key theoretical consequence: in a regular graph where all nodes have the same degree, $l(u) = 1$ for every node, meaning $P(u) = B(u) + C(u)$ everywhere. The result is a sphere of radius $b$ with jitter $c$ — which is exactly what the β=0 result shows.

Barabási–Albert — Varying γ Exponent

γ ∈ {2.82, 2.83, 2.86}. Even a marginal increase in the power-law exponent produces a rapid fall in perceived structure. As γ increases, the degree distribution becomes more uniform and the layout loses its hub-and-spoke character.

Watts–Strogatz vs. Graphia

Watts–Strogatz (N=5000). Treecapitator produces a compact sphere at β≈0, reflecting the near-uniform degree distribution. Graphia applies a force-directed approach and produces a ring — structurally different but arguably more informative for this specific model.

Results — Natural Networks

Four real-world networks from the Stanford SNAP dataset were tested.

Email Network (email-EuAll)

A directed communication graph from a large European research institution (Oct 2003 – May 2005). Each node is an email address; an edge from $i$ to $j$ means $i$ sent at least one message to $j$.

Left and center: Treecapitator (nodes only / with edges). Right: Graphia. Treecapitator detects high-degree hubs and organizes smaller email clusters (bubbles) around them. Graphia produces a more compact but less interpretable layout.

Road Network (roadNet-CA)

California road network: intersections are nodes, road segments are undirected edges.

Road networks have a near-uniform degree distribution (most intersections connect to exactly 2–4 roads). Treecapitator correctly identifies this and produces a sphere with no internal structure — visually uninterpretable but statistically honest. Graphia produces a geographically-shaped blob that captures spatial topology better.

Google WebGraph

876k web pages, 5.1M directed hyperlinks.

Treecapitator identifies some high-degree hubs (major web portals) and separates them from the dense low-degree majority, but overall interpretability is limited. Graphia collapses everything into a blue mass — essentially unreadable.

Catalan Linguistic Dependency Graph

Derived from the syntactic dependency trees of Universal Dependencies, AnCora Catalan corpus. Each unique token is a node; two nodes are connected if there is any syntactic dependency between their tokens in the corpus.

The linguistic graph has a high average degree (15.91) and a mix of very-high-degree function words (articles, prepositions) and low-degree content words. Treecapitator produces small satellite clusters analogous to the email case, though with less clear separation. Graphia shows a similar clustering tendency.

Parameter Study

Parameter b — Overall Scale

$b$ controls the radius of the sphere within which hubs are scattered ($b \gg c$ throughout). Increasing $b$ expands the layout proportionally. The relevant quantity is the ratio $b/c$: when $b \to 0$ every node collapses toward its $A(u)$ neighborhood; the jitter $C(u)$ dominates and the layout degenerates.

BA network (50k nodes) with b ∈ {2, 10, 100}. Scale has been normalized for comparison; the structural shape remains stable — b primarily controls the radius and therefore the visual density.

Parameter c — Jitter / Bubble Separation

$c$ controls the influence of $C(u)$: it prevents collapse of nodes with identical adjacency lists. Its most visible effect is on the Factor Graph model, where many nodes share the exact same neighbor set due to the deterministic divisibility rule.

BA network (10M nodes) with c ∈ {0, 1.358, 4.482}. Increasing c blurs the network by distributing nodes away from their structural position — at high c the layout degenerates into a uniform cloud.

Factor Graph (150k nodes) with c ∈ {0, 1.094, 6.218}. The bubble clusters (groups of nodes sharing the same adjacency list) remain distinctly separated by jitter c. At c=0 they are point-like; increasing c expands the bubbles while preserving the inter-bubble structure.

Parameter τ — Softmin Temperature

$\tau$ controls how greedy the $A(u)$ placement is. At $\tau \to 0$, softmin degenerates to argmin and every node is placed exactly at the position of its lowest-degree hub neighbor. At higher $\tau$, the selection softens across the neighborhood.

BA network (50k nodes) with τ ∈ {4, 1, 0}. At τ=0 the fractalized, self-similar structure of the Barabási–Albert model becomes most apparent — the layout acquires a characteristic branching pattern. This is one of the more visually striking results of the algorithm.

The τ=0 result on BA networks reveals a self-similar structure that may relate to the fractal dimension of the network's degree sequence. Quantifying this precisely with a box-counting algorithm is left as future work.

Rendering Parameters

Alpha Blending

Alpha blending is the single most important rendering parameter for dense graphs. Without it, overlapping node points form an opaque wall; with it, the local density of nodes is directly visible as brightness.

Alpha ∈ {0.11, 0.50, 1.0}. Low alpha reveals internal density structure. Full opacity hides it. For graphs with millions of nodes, α ≈ 0.1 is typically the most informative.

Edge Thickness

Edge thickness ∈ {0.000018, 0.000064, 0.000598}. Edge rendering is most informative at low thickness on dense networks; thick edges saturate the render and obscure the node distribution. The optimal value is graph-specific.

Conclusions

RQ1 — Visual clarity for power-law graphs

Partially. The email, WebGraph, and linguistic networks show meaningful interpretable structure. Road networks are completely opaque to this approach. The layout is most informative for graphs with a strong power-law degree sequence and a mix of very-high and very-low degree nodes.

RQ2 — Usefulness

Limited, but interesting. The algorithm creates visually distinctive forms for Barabási–Albert and Watts–Strogatz networks and reveals "bubble" communities (collections of nodes connected to exactly one hub). On natural networks the utility is still quite lacking, though it provides a unique way to see connectivity relationships between nodes not present in standard tools.

RQ3 — Behaviour on non-power-law graphs

On graphs that do not follow a power-law degree sequence (tested on ER binomial), Treecapitator produces spheres of varying thickness as a function of average degree — an honest representation of degree uniformity with no false structure imposed.

RQ4 — Improvement over stock algorithms

Minimal improvement is observed for WebGraph and Barabási–Albert, where the algorithm produces a more legible layout than Graphia's force-directed approach. For road networks the algorithm offers nothing useful; the geographic structure captured by force-directed methods is significantly more informative.

RQ5 — Parameter sensitivity

• $b$ is a scaling constant; the relevant quantity is $b/c$. Its shape effect only appears at extreme values.
• $c$ only meaningfully impacts networks with high numbers of nodes sharing the same adjacency list (Factor Graph model). For other graphs, $c = 0$ gives the clearest result.
• $\tau$ is the most structurally significant parameter for Barabási–Albert networks. Setting $\tau \to 0$ reveals a self-similar fractalized layout. For all other tested networks, $\tau$ should be set near 0 for clearest results.

Final Assessment

This model is visually compelling and provides a fast $O(N \log N)$ layout algorithm, but it fails to efficiently lay out and render large power-law graphs with competitive interpretability relative to established tools. It is not a replacement for Graphia or similar force-directed systems on most real-world graphs.

Its most interesting results are in the study of synthetic graphs that follow Barabási–Albert structure, where the fractalized layout at $\tau = 0$ and the bubble organization of the Factor Graph reveal structural properties not visible in conventional layouts. These remain open questions for further study.

Implementation

The visualizer is implemented in C++ with OpenGL, using CMake as the build system. It accepts graph data as edge-list pairs in plain text or compressed Gzip (SNAP format) and CoNLL-U dependency files (which it aggregates into a graph automatically).

Data validation is built in: the tool displays node-count and edge-count statistics alongside degree plots in both linear and log scale, making it straightforward to verify that the algorithm is correctly placing higher-degree nodes as described.