Using backbone to draw large and clustered graph

Posted on | Edited on | In ,

Introduction

This is the analysis of paper “Visualizing Large and Clustered Networks”[1], which gives us an approach to draw large-scale clustered graph by drawing firstly the heuristic minimum spanning tree(backbone).

Background

  • $G(V,E):$ undirected graph with V the set of vertices and $E \subseteq V \times V$ the set of edges.
  • $n:=|V|, m:=|E|$
  • $N(v):$ neighborhood of vertex v
  • $deg(v):$ degree of v
  • $P(s,t):$ path from s to t
  • $d(s,t):$ distance between two vertices (minimum path length)
  • $d_{E’}(s,t):$ distance between two vertices using only edges in $E’$
  • $T:$ a spanning tree of G

Backbone extraction

The algorithm of finding a minimum spanning tree is an NP problem, so this paper introduces a way to find the spanning tree that is densive (which means all nodes which is connected approaches to each other).

Definitions

$$w_t((u,v))=d_T(u,v)$$
The quality of a spanning tree is thus defined:
$$Q(T)=\sum_{e\in E(G)\backslash T}w_t(e)$$
If Q is the smallest => small tree distance value.

Lower bound of Q (currently considered not very important)

Initial backbone generation

Instead of ramdomly choose vertices and them append edges, two different algorithms are introduced.

  • both algorithms are started with a random selected initial vertex.
  • The vertex with higher degree influences the structure more, which should be added at first.
  • $S:$ selected spanning tree
  • $S_V:$ set of vertices already selected into the spanning tree.
  • $R:=G\backslash S$

Minimized Inner Distance Tree

After having S and the next vertex which should be appended, calculate the hook h from $N(S_V)$ which has the minimum inner distance D(h).
$$D(h)=\sum_{x=N(v)\cap S_V,vh\in S}d_t(h,x)$$
approach: holding an array $D(T)$ of size $n^2$ that keeps the tree distances $d_T(s,t)$ for all s,t in $S_V$.

Minimized Entire Distance Tree

This approach considers the distance to all the nodes, as to the nodes which are not in set $S_V$, we can’t find the tree path, so the alternative path $P’(s,t)$ is introduced.

The alternative path is considered to be seperated into two parts, the first one is composed by vertices only in S and the other one only in set $V\backslash S$
$$P’(s,t)=P(v_S)+P(v_{V\backslash S})$$
So we will choose the hook h which minimizes the following sum:
$$\sum_{w\in N(v)}P’(h,w)$$

Optimization of the backbone

Once add an edge e to T, a cycle will be induced, if we want to maintain a spanning tree, an edge $f$ should be reduced from T.

Since the paths $P_T(s,t)$ will not be changed if $P_T(s,t)\cap f=\emptyset$, only paths concerning f will be considered.

$P_T(e)$ is the original tree path of e, for any non-tree edges (s,t) whose tree paths contain f, it is defined as i, and the original tree path is $P_T(i)$.

$C_T(i,e)$ denotes the shared edges of those two paths:
$$C_T(i,e):=P_T(i)\cap P_T(e)$$

Let $C_T(e)$ denots the circle formed by adding e, so
$$\overline{C_T(i,e)}:=C_T(e)\backslash C_T(i,e)$$
The new tree path of i is :
$$P_{T’}(i)=P_T(i)\cup \overline{C_T(i,e)}\backslash C_T(i,e)$$
The generation of new tree path can be shown in Figure.
generation of new tree path

So the changed distance can be calculated:
$$
\begin{aligned}
\Delta d_T(i,e)&=d_{T’}(i)-d_T(i) \
&=|\overline{C_T(i,e)}|-|C_T(i,e)|\
&=|C_T(e)|-2|C_T(i,e)|
\end{aligned}
$$
Our final purpose of opminizing S is to have a minimum value of the change of quality $Q(T)$
$$\Delta Q(T,e,f)=\sum_i\Delta d_T(i,e,f)$$

Layout

Circulization of a set of nodes

Paper “Interacting with Huge Hierarchies: Beyond Cone Trees”[2] provides a tree layout that forms the nodes under the same root into a circle.

To reduce edge crossing, Baur et al.[3] introduces an approach to reduce crossing in circular layouts.

Circulization of the whole tree

Paper “Circular Tree Drawing by Simulating Network Synchronisation Dynamics and Scaling”[4] introduces an approach to gather the whole tree into a circle.

The mostly used approach is to add a gravity on the center of the layout.

In this paper, the author applys another algorithm, here only the steps are described.

Realization

Only Inner mode is realized.

github:  Backbone

Reference

[1] Lehmann K A, Kottler S. Visualizing Large and Clustered Networks[C]// International Conference on Graph Drawing. Springer-Verlag, 2006:240-251.

[2] Carriere J, Kazman R. Research report: Interacting with huge hierarchies: beyond cone trees[C]// Information Visualization, 1995. Proceedings. IEEE, 1995:74-81.

[3] Baur M, Brandes U. Crossing Reduction in Circular Layouts[C]// International Conference on Graph-Theoretic Concepts in Computer Science. Springer-Verlag, 2004:332-343.

[4] Toosi F G, Nikolov N S. Circular Tree Drawing by Simulating Network Synchronisation Dynamics and Scaling[J]. 2014, 8871.