NetworKit Graph Generators¶

Erdős-Rényi Generator¶

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.

Its constructor ErdosRenyiGenerator(count nNodes, double prob, directed = False, selfLoops = False) 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.

[2]:

# Initalize algorithm
erg = nk.generators.ErdosRenyiGenerator(200, 0.2)

[3]:

# Run algorithm
ergG = erg.generate()

[4]:

# Verify
print(ergG.numberOfNodes(), ergG.numberOfEdges())

200 4018

Rmat Generator¶

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..

The constructor, RmatGenerator(scale, edgeFactor, a, b, c, d, weighted=False, reduceNodes=0), 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.

We can create a graph with 64 nodes and 192 edges as follows:

[5]:

# Initalize algorithm
rmat = nk.generators.RmatGenerator(6, 3, 0.1, 0.2, 0.5, 0.2)

[6]:

# Run algorithm
rmatG = rmat.generate()

[7]:

# Verify
print(rmatG.numberOfNodes(), rmatG.numberOfEdges())

64 192

Barabási - Albert Generator¶

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. The original algorithm is very slow and thus, the much faster method from Batagelj and Brandes is implemented and the current default in NetworKit.

The constructor BarabasiAlbertGenerator(k, nMax, n0=0, batagelj=True) 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 batageljto false if you want to use the original preferential attachment model.

[8]:

# Initalize algorithm
bag = nk.generators.BarabasiAlbertGenerator(3, 1000)

[9]:

# Run algorithm
bagG = bag.generate()

[10]:

# Verify
print(bagG.numberOfNodes(), bagG.numberOfEdges())

1000 2994

Hyperbolic Generator¶

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.

The constructor HyperbolicGenerator(n=10000, k=6, gamma=3, T=0) 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.

[11]:

# Initalize algorithm
hg = nk.generators.HyperbolicGenerator(5000, 16, 7)

[12]:

# Run algorithm
hgG = hg.generate()

[13]:

# Verify
print(hgG.numberOfNodes(), hgG.numberOfEdges())

5000 40249

LFR Generator¶

LFR benchmark is an algorithm that generates benchmark networks. The node degrees are distributed according to a power law with different exponents.

The LFR(n) constructor only expects the number of nodes the generated graph should have. However, before generating the graph one needs to set a degree sequence, community size sequence and mu or generate the sequences using the provided generate-methods.

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.

[14]:

# Initalize algorithm
lfr = nk.generators.LFRGenerator(500)

[15]:

# Generate sequences
lfr.generatePowerlawDegreeSequence(20, 50, -2)
lfr.generatePowerlawCommunitySizeSequence(10, 50, -1)
lfr.setMu(0.5)

[15]:

<networkit.generators.LFRGenerator at 0x7f73fe212510>

[16]:

# Run algorithm
lfrG = lfr.generate()

[17]:

# Verify
print(lfrG.numberOfNodes(), lfrG.numberOfEdges())

500 4989

Clustered Random Graph Generator¶

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.

The constructor ClusteredRandomGraphGenerator(n, k, pin, pout) 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.

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:

[18]:

# Initialize algorithm
crg = nk.generators.ClusteredRandomGraphGenerator(100, 10, 0.5, 0.01)

[19]:

# Run algorithm
crgG = crg.generate()

[20]:

# Verify
print(crgG.numberOfNodes(), crgG.numberOfEdges())

100 266

Dorogovtsev-Mendes Generator¶

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.

The number of nodes the generated graph should have is passed to the constructor, DorogovtsevMendesGenerator(nNodes), via the nNodes parameter.

[21]:

# Initalize algorithm
dmg = nk.generators.DorogovtsevMendesGenerator(100)

[22]:

# Run algorithm
dmgG = dmg.generate()

[23]:

# Verify
print(dmgG.numberOfNodes(), dmgG.numberOfEdges())

100 197

Chung-Lu Generator¶

Given an arbitrary degree sequence, the Chung-Lu generative model will produce a random graph with the same expected degree sequence if possible.

The constructor ChungLuGenerator(degreeSequence) expects a degree sequence as a parameter.

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.

[24]:

# Generate degree sequence
degSeq = [4, 3, 2, 1, 1, 1]

[25]:

# Initalize algorithm
clg = nk.generators.ChungLuGenerator(degSeq)

[26]:

# Run algorithm
clgG = clg.generate()

[27]:

# Verify
chungLuSeq = []
for u in range (clgG.upperNodeIdBound()):
    chungLuSeq.append(clgG.degree(u))
print(chungLuSeq)

print(clgG.numberOfNodes(), clgG.numberOfEdges())

[4, 1, 1, 1, 0, 1]
6 4

Havel-Hakimi Generator¶

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.

“The contructor HavelHakimiGenerator(sequence, ignoreIfRealizable=True) 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.”

[28]:

# Generate degree sequence
sequence = []
for i in range (20):
    sequence.append(20-i)

[29]:

# Initalize algorithm
hhg = nk.generators.HavelHakimiGenerator(sequence, ignoreIfRealizable=False)

# Check if sequence is realiziable
print("Sequence is realiziable: ", hhg.isRealizable())

Sequence is realiziable:  False

As the generated sequence is not realizable, a graph cannot be generated. We can either set ignoreIfRealizable to true, or try with another sequence.

[30]:

# Generate degree sequence
sequence = [1, 2, 1, 2, 2]

# Initalize algorithm
hhg = nk.generators.HavelHakimiGenerator(sequence, ignoreIfRealizable=False)

# Check if sequence is realiziable
print("Sequence is realiziable ", hhg.isRealizable())

Sequence is realiziable  True

[31]:

# Run algorithm
hhgG = hhg.generate()

[32]:

# Verify
print(hhgG.numberOfNodes(), hhgG.numberOfEdges())
for u in range (hhgG.upperNodeIdBound()):
    assert(sequence[u] == hhgG.degree(u))

5 4

Mocnik Generator¶

The Mocnik graph generator creates random spatial graphs according to the Mocnik model.

The constructor MocnikGenerator(dim, n, k, weighted) expects the parameters dim which dictates the dimension of the space, the number of nodesn 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.

[33]:

# Initalize algorithm
mg = nk.generators.MocnikGenerator(3, 10000, 2.6)

[34]:

# Run algorithm
mgG = mg.generate()

[35]:

# Verify
print(mgG.numberOfNodes(), mgG.numberOfEdges())

10000 163646