An epidemics simulator for Kroenecker networks

During a short client work I needed to build a software to construct self-similar networks, which were used as neural network topologies for forecasting models. To draft those networks, I needed a simple tool for manual construction of simple graphs of few nodes and a number of connections. Those seed graphs would then be extended into so called Kronecker networks.

What’s a Kronecker graph?

The basic idea behind Kronecker graphs is that a network is constructed by doing successive Kronecker multiplications of the adjacency matrix of a seed graph. This way the basic topology of the seed is spread through all scales of the constructed network. Depending on the seed graph, this will result in scale-free networks which exhibit many of the properties of real-world networks, e.g. community structures and power-law degree distributions. Kronecker networks are also fittable to observed real-world networks through an effective procedure proposed by J. Leskovec.

The example below illustrates the process of Kronecker network construction, when the seed is a circular graph of 6 nodes and only one Kronecker multiplication is accomplished:seed1

Here is another example of 12 nodes:

seed2As can be seen, the Kronecker networks exhibit similarities with the seeds: the smallest clusters resemble the topology of the seed graph, and the connections between the clusters has also the same topology as introduced by the seed graph. The size of the graph will grow exponentially during the multiplications – the second multiplication would expand this latter network into a network of 1728 nodes and 18788 connections.

To illustrate the difference between the Kronecker networks and random branching networks, below is presented a simple random branching-tree network, for which the number of nodes and the number of connections are approximately of the same magnitude:

branchingNetworks of different sizes can be generated by doing further Kronecker multiplications with the seed graph. For more background information and scientific content, there is a practical pre-print article on Kronecker networks by Jure Leskovec et al.

And the epidemics?

Anyhow, through several coincidences, this simple network construction tool ended up as an epidemics simulator. It is able to simulate epidemic behaviour in highly connected Kronecker networks, or in poorly connected branching networks, which both can be generated using the applet. Feel free to try it out below (see the instructions on the bottom of the linked page): Start the Applet.

interfaceAlthough hardly of any scientific use, I found the applet being a proper stress-relieving toy. However, it can very well demonstrate how an infection spreads quite efficiently through Kronecker networks and very inefficiently through branching networks. This applet was implemented using Processing. The layout animation is based on physics engine by Jeffrey Traer Bernstein.

Published by

Vesa

Flâneuring through experiments in data, science and artsy digital things.