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.
The graph generation failed. Perhaps you found a bug!
To help us fix it, please tell us what you were doing.
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.
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).