The onion decomposition of a network
The onion decomposition
of a network is a recently introduced network fingerprinting technique. It can be used to identify structural properties of a network, such as ”tree-like” structure, ”loopy” structure, or the property of having an ”interesting“ sub-network.
Examples of networks that can be analysed in this way include purely mathematical networks; physical networks like transportation networks and power grids; and social networks such as collaboration graphs. The picture shows three mathematical networks: (a) the Cayley tree
, in which all but the terminal nodes are connected to exactly three other nodes; (b) the Erdős–Rényi random graph
; and (c) the square lattice
, in which each node not on the boundary of the network is connected to exactly four others.
Under the picture of each network is its onion spectrum
. This can be thought of as a summary of the onion decomposition of the network, which we describe below. The number and nature of the pieces of the onion spectrum can be used to gain insight into the structure of the original network.
The onion decomposition was defined a few months ago in the paper Network structure at multiple scales via a new network statistic: the onion decomposition
by Laurent Hébert-Dufresne
, Joshua A. Grochow
, and Antoine Allard
), and the picture shown here comes from that paper. The decomposition is a refinement of the previously known k-core decomposition, and it is called the onion decomposition because it is reminiscent of peeling an onion.
To explain how this works, we use concepts from graph theory
. A graph
is a mathematical object that can be used to model a network. A graph consists of a set of nodes, called vertices
, and a set of edges
, which connect pairs of vertices. We do not allow our graphs to contain more than one edge connecting the same pair of vertices, or to have any edges that connect a vertex to itself. The degree
of a vertex is the number of edges emanating from it.
To decompose a graph, one first removes all vertices of degree zero (isolated points); these vertices form the 0-shell
of the graph. To form the 1-shell
, one removes all vertices of degree 1, followed by all the vertices that become vertices of degree 1 as a result of this process, then iterating the procedure again and again until there are no more vertices of degree 0 or 1. The vertices that are removed at each iteration of the construction of the 1-shell are called the layers
of the 1-shell. The construction of the 2-shell (and higher shells) follows a similar procedure: at each iteration, one removes all vertices of degree 2 or lower, until this is no longer possible.
The onion spectrum
shown in the picture shows the relative abundance of vertices in each layer within each shell of the corresponding graph. Each connected piece of the picture is shown in a different colour and corresponds to a shell, and each dot corresponds to each successive layer of that shell. The vertical scale is logarithmic, which means that a straight line corresponds to exponential behaviour. The meaning of the colours in the pictures of the actual networks is different: the size of a vertex corresponds to its degree, and the colour of a vertex shows whether it is shallow or deep in the network. The original k-core decomposition gives less information, because it only keeps track of the k-shells, and not the layers within each shell.
The paper shows how to use the onion spectrum to read off properties of the original network. Exponential decay in the spectrum, like in the Cayley tree case, is indicative of the graph having a tree-like structure, whereas sub-exponential decay, like in the random graph case, suggests that the graph has a lot of circuits. It is a nice exercise to show that the Cayley tree consists of one big 1-shell, and the square lattice consists of one big 2-shell; it follows from this that the onion spectrum of each graph has only one connected component.
Networks like these last two, whose onion spectrum has fewer components than a random graph, tend to be disassortative
, which means that nodes tend to be connected to nodes that are somehow ”unlike” themselves. One way to illustrate this is to colour the vertices of the square lattice in alternating colours, like a chess board; something analogous can be done for the Cayley tree.
Conversely, a network with more components than a random graph will tend to be assortative
, meaning that nodes tend to be connected to nodes that are somehow like themselves. A good example of this that is studied in the paper is the collaboration graph of condensed matter physics papers on the arXiv preprint server. Some other real world graphs that are studied are the graph of a power grid, which is tree-like and assortative, and the network of roads in Pennsylvania. The road network graph has one particular shell that exhibits a change in its decay rate, which is indicative of the network having an interesting sub-network. In fact, the road system consists of several essentially isolated components.Relevant links
Here's another post by me about assortative and disassortative networks: https://plus.google.com/101584889282878921052/posts/cHo5dMTQdsW
That post links to two other relevant posts by me, whose links I provide below for convenience.
A post by me about the mathematics of social networks: https://plus.google.com/101584889282878921052/posts/YV7j9LRqKsX
A post by me about the random graph: https://plus.google.com/101584889282878921052/posts/34guwy4ftWX
Wikipedia has more information about k-cores on its page about degeneracy in graph theory: https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
I'm glad that Google has fixed the discouraging bug that was corrupting the plus-one counts of posts. On the negative side, it looks like the selectedpapers.net
site (which was associated with the spnetwork
hashtag) is no more. Can anyone confirm or deny this?#mathematics #sciencesunday