CiGRAM - Circular Gaussian Random grAph Model

CiGRAM was designed to generate undirected graphs with heterogeneous degree distributions and configurable assortativity and community structure.

CiGRAM is using two wrapped Gaussian distribution functions to determine the probability that a node is selected to form an edge. First, node positions are sampled from the distribution function f (shown in blue below). Each node is given a position (angle) on a unit circle. Then, each node position is scored using the distribution function s (shown in green below). The highest scores are given to the nodes in the least dense regions of the circle.

The scores determine the node degrees. The higher the score, the more likely it is that a node would become a part of an edge. Similar approach is used to determine the community structure, except that the scores determine the community size and influence the probability that a community is selected to form an edge between two communities.

number of nodes (n)

graph density (d)

number of communities (k)

assortativity (a)

node position (σ_f)

node score (σ_s)

inter-community edges (e_k)

community position (Σ_f)

community score (Σ_s)

probability of overlap (p_o)

Examples of real-world networks and best model parameters found with PSO. For each target network only the largest connected component was used.

The goodness of fit was measured by comparison of the real-world network topological properties (clustering coefficient, assortativity, modularity) with the average values of these properties for a sample of 100 random graphs. Also an average Kolmogorov-Smirnoff distance between the cumulative degree distributions was calculated.

network	KS	CC	r	Q	k	a	σ_f	σ_s	e_k	Σ_f	Σ_s	p_o
US Power Grid		0.080	0.003	0.936
model 1	0.002	0.000	0.008	0.740	1	0.083	0.500	1.192	0.000	1.600	1.600	0.000
model 2	0.000	0.073	-0.001	0.861	488	-0.170	1.663	1.369	0.100	0.600	0.708	0.010
model 3	0.000	0.076	-0.000	0.806	380	0.067	1.253	1.494	0.250	0.609	1.800	0.100
Arabidopsis PPI		0.099	-0.197	0.754
model 1	0.006	0.014	-0.206	0.449	1	-1.232	0.854	0.903	0.000	1.600	1.600	0.000
model 2	0.011	0.095	-0.193	0.746	53	-1.416	0.746	0.939	0.100	1.392	0.617	0.010
model 3	0.009	0.104	-0.186	0.656	88	-5.000	1.485	0.724	0.250	1.800	1.796	0.100
Open Flights		0.456	0.049	0.651
model 1	0.008	0.076	0.047	0.236	1	0.865	0.838	0.731	0.000	1.600	1.600	0.000
model 2	0.011	0.469	0.050	0.792	290	4.708	1.360	0.500	0.100	0.798	0.600	0.010
model 3	0.004	0.450	0.021	0.598	53	1.516	1.163	0.610	0.250	0.625	0.894	0.100
PGP		0.266	0.238	0.883
model 1	0.003	0.005	0.233	0.481	1	2.544	0.540	0.723	0.000	1.600	1.600	0.000
model 2	0.010	0.253	0.223	0.889	1068	3.400	0.898	0.764	0.100	0.600	0.716	0.010
model 3	0.008	0.242	0.139	0.724	988	1.857	0.965	0.728	0.250	0.600	0.863	0.100
arXiv astro-ph		0.633	0.201	0.626
model 1	0.027	0.007	0.221	0.217	1	1.322	1.175	0.919	0.000	1.600	1.600	0.000
model 2	0.019	0.551	0.207	0.870	1790	1.000	1.697	0.701	0.100	0.600	0.638	0.010
model 3	0.017	0.617	-0.057	0.676	352	-0.135	1.800	0.638	0.250	0.703	1.216	0.100
SeedNet		0.502	0.177	0.561
model 1	0.036	0.121	0.174	0.116	1	0.407	1.301	0.845	0.000	1.600	1.600	0.000
model 2	0.039	0.358	0.172	0.564	45	1.211	1.731	0.767	0.100	0.800	0.600	0.010
model 3	0.022	0.214	0.100	0.437	7	0.821	1.800	0.832	0.250	1.544	1.273	0.100

To the extent possible under law, the CiGRAM Authors have waived all copyright and related or neighbouring rights
to the CiGRAM example network models.

Requirements

HTML5, CSS3 and canvas/WebGL compatible browser
(e.g. latest Firefox, Chromium/Chrome, Opera, Safari or Internet Explorer 11).

Authors

model design, implementation, parameter optimisation
James Gilbert
visualisation, web development, testing
Paweł Widera
study design, scientific supervision, research funding
Andrew Wood, Andrzej Bargieła, Mike Holdsworth, Natalio Krasnogor

Acknowledgments

boost - C++ libraries (Boost Software Licence)
Python - programming language (PSF Licence)
NumPy - scientific computing library (Modified BSD Licence)
matplotlib - plotting library (matplotlib licence)
bottle - micro web-framework (MIT/X11 Licence)
sigma.js - graph drawing library (MIT/X11 Licence)
jQuery - client-side scripting library (MIT/X11 Licence)

Source code

You can download the source code of the CiGRAM model generator to learn its internals or run it on your own computer. This code is released under the terms of the GNU General Public Licence version 3 (or later).

CiGRAM - Circular Gaussian Random grAph Model

number of nodes (n)

graph density (d)

number of communities (k)

assortativity (a)

node position (σf)

node score (σs)

inter-community edges (ek)

community position (Σf)

community score (Σs)

probability of overlap (po)

Model parameters