{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# NetworKit Graph Generators"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this notebook we will cover some algorithms to generate random graphs implemented in the `generators` module of NetworKit. Graph generators generate graphs that match certain user-defined parameters. It is particularly useful in cases when one does not have real graphs at hand (or none that matches specific properties). All algorithms in the `generators` module implement a `generate` function that must be called after the specific algorithm has been initialized which returns a [networkit.Graph](https://networkit.github.io/dev-docs/python_api/networkit.html?highlight=graph#networkit.Graph).\n",
"\n",
"As a first step we import NetworKit:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import networkit as nk"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Erdős-Rényi Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Erdős-Rényi generator creates a random graph in the G(n, p) model, i.e., a graph with `n` nodes connected randomly. Each edge is included in the graph with probability `p` independently from every other edge.\n",
"\n",
"Its constructor [ErdosRenyiGenerator(count nNodes, double prob, directed = False, selfLoops = False)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=erdos#networkit.generators.ErdosRenyiGenerator) expects the number of nodes there will be in the graph via the parameter `nNodes`, and the probability of existence for each edge `prob` as mandatory parameters. If `directed` is set to true, a directed graph will be generated. If `selfLoops` is true and the graph is directed, the graph may have self loops."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"erg = nk.generators.ErdosRenyiGenerator(200, 0.2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"ergG = erg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(ergG.numberOfNodes(), ergG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Rmat Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Rmat generator generates static R-MAT (Recursive MATrix) graphs by operating on the graph's adjacency matrix in a recursive manner. R-MAT graphs are random graphs with $n$ = $2^{scale}$ nodes and $n * edgeFactor$ edges. More details can be found in the original paper: `Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos: R-MAT: A Recursive Model for Graph Mining. SDM 2004: 442-446.`. \n",
"\n",
"The constructor, [RmatGenerator(scale, edgeFactor, a, b, c, d, weighted=False, reduceNodes=0)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=rmat#networkit.generators.RmatGenerator), expects the number of nodes `n` via the `scale` parameter; $n$ = $2^{scale}$. `edgeFactor` specifies the number of edges `m` there should be in the graph and is computed using the following equation: $m$ = $n * edgeFactor$. The parameters `a, b, c, d` are probabilities that an edge should be in the upper left, upper right, lower left or lower right quadrant of the matrix respectively. The total sum of the four probabilities should be 1. Set `weighted` to true if the resulting graph should be weighted. The `reduceNodes` parameter dictates the number of random nodes to delete to achieve a given node count. By default it is set to 0.\n",
"\n",
"We can create a graph with 64 nodes and 192 edges as follows:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"rmat = nk.generators.RmatGenerator(6, 3, 0.1, 0.2, 0.5, 0.2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"rmatG = rmat.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(rmatG.numberOfNodes(), rmatG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Barabási - Albert Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Barabási–Albert model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. The network begins with an initial connected network of $n_0$ nodes, and new nodes are added to the network one at a time. This generator implements the preferential attachment model as introduced by [Barabási and Albert ](http://arxiv.org/pdf/cond-mat/9910332.pdf). The original algorithm is very slow and thus, the much faster method from [Batagelj and Brandes ](https://kops.uni-konstanz.de/bitstream/handle/123456789) is implemented and the current default in NetworKit.\n",
"\n",
"The constructor [BarabasiAlbertGenerator(k, nMax, n0=0, batagelj=True)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=barabasi#networkit.generators.BarabasiAlbertGenerator) expects the parameter `k`, the number of attachments per node, and `nMax`, the maximum number of nodes in the graph as mandatory paramaters. `n0` is the number of connected nodes to begin with. Set `batagelj`to false if you want to use the original preferential attachment model."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"bag = nk.generators.BarabasiAlbertGenerator(3, 1000)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"bagG = bag.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(bagG.numberOfNodes(), bagG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Hyperbolic Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Hyperbolic generator distributes points in hyperbolic space and adds edges between points with a probability depending on their distance. The resulting graphs have a power-law degree distribution, small diameter and high clustering coefficient. For a temperature of 0, the model resembles a unit-disk model in hyperbolic space.\n",
"\n",
"The constructor [HyperbolicGenerator(n=10000, k=6, gamma=3, T=0)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=hyperbolic#networkit.generators.HyperbolicGenerator) expects the number of nodes via the parameter `n`, the target average degree of each node which is specified by `k`, the target exponent of power-law distribution which is passed via the `gamma` parameter , and `T` which is the temperature."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"hg = nk.generators.HyperbolicGenerator(5000, 16, 7)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"hgG = hg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(hgG.numberOfNodes(), hgG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## LFR Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"LFR benchmark is an algorithm that generates benchmark networks. The node degrees are distributed according to a power law with different exponents. \n",
"\n",
"The [LFR(n)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=lfr#networkit.generators.LFRGenerator) constructor only expects the number of nodes the generated graph should have. However, before generating the graph one needs to set a [degree sequence](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=degreese#networkit.generators.LFRGenerator.setDegreeSequence), [community size sequence](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=communitysi#networkit.generators.LFRGenerator.setCommunitySizeSequence) and [ mu](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=setm#networkit.generators.LFRGenerator.setMu) or generate the sequences using the provided [generate-methods](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=generatepower#networkit.generators.LFRGenerator.generatePowerlawCommunitySizeSequence). \n",
"\n",
"For this example, we generate the sequences a power-law degree sequence with average degree 20, maximum degree 50, and exponent of the node degree distribution -2. We also generate a power-law community size sequence with minimum size 10, maximum size 50, and exponent of the community size distribution -2. Finally, we set the mixing parameter `mu` to 0.5."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"lfr = nk.generators.LFRGenerator(500)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Generate sequences\n",
"lfr.generatePowerlawDegreeSequence(20, 50, -2)\n",
"lfr.generatePowerlawCommunitySizeSequence(10, 50, -1)\n",
"lfr.setMu(0.5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"lfrG = lfr.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(lfrG.numberOfNodes(), lfrG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Clustered Random Graph Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The clustered random graph generates a clustered random graph. The number of nodes and the number of edges are adjustable as well as the probabilities for intra-cluster and inter-cluster edges.\n",
"\n",
"The constructor [ClusteredRandomGraphGenerator(n, k, pin, pout)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=clustered#networkit.generators.ClusteredRandomGraphGenerator) expects the number of nodes `n` and the number of clusters `k` followed by the intra-cluster edge probability and the inter-cluster edge probability as `pin` and `pout` respectively.\n",
"\n",
"\n",
"A graph with 100 nodes grouped in 10 clusters with intra-cluster edge probability 0.5 and inter-cluster edge probability 0.01 can be generated as follows:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initialize algorithm\n",
"crg = nk.generators.ClusteredRandomGraphGenerator(100, 10, 0.5, 0.01)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"crgG = crg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(crgG.numberOfNodes(), crgG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Dorogovtsev-Mendes Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This generator creates graphs using the Dorogovtsev-Mendes algorithm. It starts by creating three nodes and tree edges, and then adding one node at a time. Each time a node is added, an edge is chosen randomly and the node is connected via two new edges to the two ends of the chosen edge.\n",
"\n",
"The number of nodes the generated graph should have is passed to the constructor, [DorogovtsevMendesGenerator(nNodes)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=dorog#networkit.generators.DorogovtsevMendesGenerator), via the `nNodes` parameter."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"dmg = nk.generators.DorogovtsevMendesGenerator(100)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"dmgG = dmg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(dmgG.numberOfNodes(), dmgG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Chung-Lu Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Given an arbitrary degree sequence, the Chung-Lu generative model will produce a random graph with the same expected degree sequence if possible.\n",
"\n",
"The constructor [ChungLuGenerator(degreeSequence)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=chung#networkit.generators.ChungLuGenerator) expects a degree sequence as a parameter.\n",
"\n",
"In order to create a graph with 5 nodes, we first need to generate a degree sequence that will be passed to the constructor. In order to create a graph with 5 nodes, we first need to generate a degree sequence that will be passed to the constructor. Note that the degree sequence is not required to be sorted."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Generate degree sequence\n",
"degSeq = [4, 3, 2, 1, 1, 1]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"clg = nk.generators.ChungLuGenerator(degSeq)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"clgG = clg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"chungLuSeq = []\n",
"for u in range (clgG.upperNodeIdBound()):\n",
" chungLuSeq.append(clgG.degree(u))\n",
"print(chungLuSeq)\n",
"\n",
"print(clgG.numberOfNodes(), clgG.numberOfEdges())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Havel-Hakimi Generator "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Havel-Hakimi algorithm for generating a graph according to a given degree sequence $(d_1, d_2,...,d_n)$. The degree sequence must be non-increasing, i.e., $d_1$ must be the highest degree. \n",
"\n",
"\"The contructor [HavelHakimiGenerator(sequence, ignoreIfRealizable=True)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=havel#networkit.generators.HavelHakimiGenerator) expects the degree sequence as a mandatory parameter. If `ignoreIfRealizable` is true, the graph is generated even if the degree sequence is not realizable. Some nodes may then get lower degrees than requested in the sequence. If `ignoreIfRealizable` is false and the sequence is not realizable, an exception is thrown and the graph cannot be generated.\""
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Generate degree sequence\n",
"sequence = []\n",
"for i in range (20):\n",
" sequence.append(20-i)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"hhg = nk.generators.HavelHakimiGenerator(sequence, ignoreIfRealizable=False)\n",
"\n",
"# Check if sequence is realiziable\n",
"print(\"Sequence is realiziable: \", hhg.isRealizable())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As the generated sequence is not realizable, a graph cannot be generated. We can either set `ignoreIfRealizable` to true, or try with another sequence. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Generate degree sequence\n",
"sequence = [1, 2, 1, 2, 2]\n",
"\n",
"# Initalize algorithm\n",
"hhg = nk.generators.HavelHakimiGenerator(sequence, ignoreIfRealizable=False)\n",
"\n",
"# Check if sequence is realiziable\n",
"print(\"Sequence is realiziable \", hhg.isRealizable())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"hhgG = hhg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify\n",
"print(hhgG.numberOfNodes(), hhgG.numberOfEdges())\n",
"for u in range (hhgG.upperNodeIdBound()):\n",
" assert(sequence[u] == hhgG.degree(u))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Mocnik Generator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Mocnik graph generator creates random spatial graphs according to the Mocnik model. \n",
"\n",
"The constructor [MocnikGenerator(dim, n, k, weighted)](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=mocnik#networkit.generators.MocnikGenerator) expects the parameters `dim` which dictates the dimension of the space, the number of nodes`n` and the density parameter `k`. The density parameter determines the ratio of edges to nodes. Set `weighted` to true if the generated graph should be weighted."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Initalize algorithm\n",
"mg = nk.generators.MocnikGenerator(3, 10000, 2.6)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Run algorithm\n",
"mgG = mg.generate()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Verify \n",
"print(mgG.numberOfNodes(), mgG.numberOfEdges())"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}