networkit.generators

This module provides graph generators that produce synthetic networks according to various models.

class networkit.generators.BTERReplicator(G, scale=1)

Bases: object

Wrapper class that calls the BTER graph generator implementation in FEASTPACK from http://www.sandia.gov/~tgkolda/feastpack/ using GNU Octave.

Note that BTER needs the rng method which is unavailable in Octave, but the call in bter.m can be easily replaced.

feastpackPath = '.'
classmethod fit(G, scale=1)
generate()
matlabScript = "\n\taddpath('{0}');\n\tfilename = 'bter_input.mat';\n\tload(filename);\n\taddpath('{1}');\n\ttStart = tic;\n\t[ccd,gcc] = ccperdeg(G);\n\tnd = accumarray(nonzeros(sum(G,2)),1);\n\tnd = nd * {2};\n\ttFit = toc(tStart);\n\ttStart = tic;\n\t[E1,E2] = bter(nd,ccd,'verbose',false,'blowup',10);\n\ttGenerate = toc(tStart);\n\tG_bter = bter_edges2graph(E1,E2);\n\tsave('-v7', '{3}', 'G_bter', 'tFit', 'tGenerate');\n\texit;\n\t"
matlabname = 'octave'
classmethod setPaths(feastpackPath)
class networkit.generators.BarabasiAlbertGenerator

Bases: object

This generator implements the preferential attachment model as introduced by Barabasi and Albert[1]. The original algorithm is very slow and thus, the much faster method from Batagelj and Brandes[2] is implemented and the current default. The original method can be chosen by setting p batagelj to false. [1] Barabasi, Albert: Emergence of Scaling in Random Networks http://arxiv.org/pdf/cond-mat/9910332.pdf [2] ALG 5 of Batagelj, Brandes: Efficient Generation of Large Random Networks https://kops.uni-konstanz.de/bitstream/handle/123456789/5799/random.pdf?sequence=1

k : count
number of edges that come with a new node
nMax : count
maximum number of nodes produced
n0 : count
number of starting nodes
batagelj : bool
Specifies whether to use batagelj’s method or the original one.
fit(type cls, Graph G, scale=1)
generate(self)
class networkit.generators.ChungLuGenerator

Bases: object

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

see Chung, Lu: The average distances in random graphs with given expected degrees and Chung, Lu: Connected Components in Random Graphs with Given Expected Degree Sequences. Aiello, Chung, Lu: A Random Graph Model for Massive Graphs describes a different generative model which is basically asymptotically equivalent but produces multi-graphs.

fit(type cls, Graph G, scale=1)

Fit model to input graph

generate(self)

Generates graph with expected degree sequence seq.

Graph
The generated graph.
class networkit.generators.ClusteredRandomGraphGenerator

Bases: object

The ClusteredRandomGraphGenerator class is used to create 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.

ClusteredRandomGraphGenerator(count, count, pin, pout)

Creates a clustered random graph.

n : count
number of nodes
k : count
number of clusters
pin : double
intra-cluster edge probability
pout : double
inter-cluster edge probability
generate(self)

Generates a clustered random graph with the properties given in the constructor.

Graph
The generated graph.
getCommunities(self)

Returns the generated ground truth clustering.

Partition
The generated ground truth clustering.
networkit.generators.ConfigurationModelGenerator

alias of EdgeSwitchingMarkovChainGenerator

class networkit.generators.DorogovtsevMendesGenerator

Bases: object

Generates a graph according to the Dorogovtsev-Mendes model.

DorogovtsevMendesGenerator(nNodes)

Constructs the generator class.

nNodes : count
Number of nodes in the target graph.
fit(type cls, Graph G, scale=1)
generate(self)

Generates a random graph according to the Dorogovtsev-Mendes model.

Graph
The generated graph.
class networkit.generators.DynamicDorogovtsevMendesGenerator

Bases: object

Generates a graph according to the Dorogovtsev-Mendes model.

DynamicDorogovtsevMendesGenerator()

Constructs the generator class.

generate(self, nSteps)

Generate event stream.

nSteps : count
Number of time steps in the event stream.
class networkit.generators.DynamicForestFireGenerator

Bases: object

Generates a graph according to the forest fire model.
The forest fire generative model produces dynamic graphs with the following properties:

heavy tailed degree distribution communities densification power law shrinking diameter

see Leskovec, Kleinberg, Faloutsos: Graphs over Tim: Densification Laws, Shringking Diameters and Possible Explanations

DynamicForestFireGenerator(double p, bool directed, double r = 1.0)

Constructs the generator class.

p : forward burning probability. directed : decides whether the resulting graph should be directed r : optional, backward burning probability

generate(self, nSteps)

Generate event stream.

nSteps : count
Number of time steps in the event stream.
class networkit.generators.DynamicHyperbolicGenerator

Bases: object

generate(self, nSteps)

Generate event stream.

nSteps : count
Number of time steps in the event stream.
getCoordinates(self)

Get coordinates in the Poincare disk

getGraph(self)
class networkit.generators.DynamicPathGenerator

Bases: object

Example dynamic graph generator: Generates a dynamically growing path.

generate(self, nSteps)
class networkit.generators.DynamicPubWebGenerator

Bases: object

generate(self, nSteps)

Generate event stream.

nSteps : count
Number of time steps in the event stream.
getGraph(self)
class networkit.generators.EdgeSwitchingMarkovChainGenerator

Bases: object

Graph generator for generating a random simple graph with exactly the given degree sequence based on the Edge-Switching Markov-Chain method.

This implementation is based on the paper “Random generation of large connected simple graphs with prescribed degree distribution” by Fabien Viger and Matthieu Latapy, available at http://www-rp.lip6.fr/~latapy/FV/generation.html, however without preserving connectivity (this could later be added as optional feature).

The Havel-Hakami generator is used for the initial graph generation, then the Markov-Chain Monte-Carlo algorithm as described and implemented by Fabien Viger and Matthieu Latapy but without the steps for ensuring connectivity is executed. This should lead to a graph that is drawn uniformly at random from all graphs with the given degree sequence.

Note that at most 10 times the number of edges edge swaps are performed (same number as in the abovementioned implementation) and in order to limit the running time, at most 200 times as many attempts to perform an edge swap are made (as certain degree distributions do not allow edge swaps at all).

degreeSequence : vector[count]
The degree sequence that shall be generated
ignoreIfRealizable : bool, optional
If true, generate the graph even if the degree sequence is not realizable. Some nodes may get lower degrees than requested in the sequence.
fit(type cls, Graph G, scale=1)
generate(self)

Generate a graph according to the configuration model.

Issues a INFO log message if the wanted number of edge swaps cannot be performed because of the limit of attempts (see in the description of the class for details).

Graph
The generated graph.
getRealizable(self)
isRealizable(self)
class networkit.generators.ErdosRenyiGenerator

Bases: object

Creates random graphs in the G(n,p) model. The generation follows Vladimir Batagelj and Ulrik Brandes: “Efficient generation of large random networks”, Phys Rev E 71, 036113 (2005).

ErdosRenyiGenerator(count, double)

Creates G(nNodes, prob) graphs.

nNodes : count
Number of nodes n in the graph.
prob : double
Probability of existence for each edge p.
directed : bool
Generates a directed
fit(type cls, Graph G, scale=1)

Fit model to input graph

generate(self)
class networkit.generators.HavelHakimiGenerator

Bases: object

Havel-Hakimi algorithm for generating a graph according to a given degree sequence.

The sequence, if it is realizable, is reconstructed exactly. The resulting graph usually has a high clustering coefficient. Construction runs in linear time O(m).

If the sequence is not realizable, depending on the parameter ignoreIfRealizable, either an exception is thrown during generation or the graph is generated with a modified degree sequence, i.e. not all nodes might have as many neighbors as requested.

HavelHakimiGenerator(sequence, ignoreIfRealizable=True)

sequence : vector
Degree sequence to realize. Must be non-increasing.
ignoreIfRealizable : bool, optional
If true, generate the graph even if the degree sequence is not realizable. Some nodes may get lower degrees than requested in the sequence.
fit(type cls, Graph G, scale=1)
generate(self)

Generates degree sequence seq (if it is realizable).

Graph
Graph with degree sequence seq or modified sequence if ignoreIfRealizable is true and the sequence is not realizable.
getRealizable(self)
isRealizable(self)
class networkit.generators.HyperbolicGenerator

Bases: object

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.

HyperbolicGenerator(n, k=6, gamma=3, T=0)

n : integer
number of nodes
k : double
average degree
gamma : double
exponent of power-law degree distribution
T : double
temperature of statistical model
fit(type cls, Graph G, scale=1)

Fit model to input graph

generate(self)

Generates hyperbolic random graph

Graph

getElapsedMilliseconds(self)
setBalance(self, balance)
setLeafCapacity(self, capacity)
setTheoreticalSplit(self, theoreticalSplit)
class networkit.generators.LFRGenerator

Bases: _NetworKit.Algorithm

The LFR clustered graph generator as introduced by Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi.

The community assignment follows the algorithm described in “Benchmark graphs for testing community detection algorithms”. The edge generation is however taken from their follow-up publication “Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities”. Parts of the implementation follow the choices made in their implementation which is available at https://sites.google.com/site/andrealancichinetti/software but other parts differ, for example some more checks for the realizability of the community and degree size distributions are done instead of heavily modifying the distributions.

The edge-switching markov-chain algorithm implementation in NetworKit is used which is different from the implementation in the original LFR benchmark.

You need to set a degree sequence, a community size sequence and a mu using the additionally provided set- or generate-methods.

n : count
The number of nodes
fit(type cls, Graph G, scale=1, vanilla=False, communityDetectionAlgorithm=PLM, plfit=False)

Fit model to input graph

generate(self, useReferenceImplementation=False)

Generates and returns the graph. Wrapper for the StaticGraphGenerator interface.

Graph
The generated graph.
generatePowerlawCommunitySizeSequence(self, count minCommunitySize, count maxCommunitySize, double communitySizeExp)

Generate a powerlaw community size sequence with the given minimum and maximum size and the given exponent.

minCommunitySize : count
The minimum community size
maxCommunitySize : count
The maximum community size
communitySizeExp : double
The (negative) community size exponent of the power law degree distribution of the community sizes
generatePowerlawDegreeSequence(self, count avgDegree, count maxDegree, double nodeDegreeExp)

Generate and set a power law degree sequence using the given average and maximum degree with the given exponent.

avgDegree : count
The average degree of the created graph
maxDegree : count
The maximum degree of the created graph
nodeDegreeExp : double
The (negative) exponent of the power law degree distribution of the node degrees
getGraph(self)

Return the generated Graph.

Graph
The generated graph.
getPartition(self)

Return the generated Partiton.

Partition
The generated partition.
params = {}
paths = {}
setCommunitySizeSequence(self, vector[count] communitySizeSequence)

Set the given community size sequence.

communitySizeSequence : collections.Iterable
The community sizes that shall be used.
setDegreeSequence(self, vector[count] degreeSequence)

Set the given degree sequence.

degreeSequence : collections.Iterable
The degree sequence that shall be used by the generator
setMu(self, mu)

Set the mixing parameter, this is the fraction of neighbors of each node that do not belong to the node’s own community.

This can either be one value for all nodes or an iterable of values for each node.

mu : double or collections.Iterable
The mixing coefficient(s), i.e. the factor of the degree that shall be inter-cluster degree
setMuWithBinomialDistribution(self, double mu)

Set the internal degree of each node using a binomial distribution such that the expected mixing parameter is the given @a mu.

The mixing parameter is for each node the fraction of neighbors that do not belong to the node’s own community.

mu : double
The expected mu that shall be used.
setPartition(self, Partition zeta)

Set the partition, this replaces the community size sequence and the random assignment of the nodes to communities.

zeta : Partition
The partition to use
setPathToReferenceImplementationDir(type cls, path)
class networkit.generators.PowerlawDegreeSequence

Bases: object

Generates a powerlaw degree sequence with the given minimum and maximum degree, the powerlaw exponent gamma

If a list of degrees or a graph is given instead of a minimum degree, the class uses the minimum and maximum value of the sequence and fits the exponent such that the expected average degree is the actual average degree.

minDeg : count, list or Graph
The minium degree, or a list of degrees to fit or graphs
maxDeg : count
The maximum degree
gamma : double
The powerlaw exponent, default: -2
getDegree(self)

Returns a degree drawn at random with a power law distribution

count
The generated random degree
getDegreeSequence(self, count numNodes)

Returns a degree sequence with even degree sum.

numNodes : count
The number of nodes/degrees that shall be returned
vector[count]
The generated degree sequence
getExpectedAverageDegree(self)

Returns the expected average degree. Note: run needs to be called first.

double
The expected average degree.
getGamma(self)

Get the exponent gamma.

double
The exponent gamma
getMaximumDegree(self)

Get the maximum degree

count
The maximum degree
getMinimumDegree(self)

Returns the minimum degree.

count
The minimum degree
run(self)

Executes the generation of the probability distribution.

setGamma(self, double gamma)

Set the exponent gamma

gamma : double
The exponent to set
setGammaFromAverageDegree(self, double avgDeg, double minGamma=-1, double maxGamma=-6)

Tries to set the powerlaw exponent gamma such that the specified average degree is expected.

avgDeg : double
The average degree that shall be approximated
minGamma : double
The minimum gamma to use, default: -1
maxGamma : double
The maximum gamma to use, default: -6
setMinimumFromAverageDegree(self, double avgDeg)

Tries to set the minimum degree such that the specified average degree is expected.

avgDeg : double
The average degree that shall be approximated
class networkit.generators.PubWebGenerator

Bases: object

Generates a static graph that resembles an assumed geometric distribution of nodes in a P2P network.

The basic structure is to distribute points randomly in the unit torus and to connect vertices close to each other (at most @a neighRad distance and none of them already has @a maxNeigh neighbors). The distribution is chosen to get some areas with high density and others with low density. There are @a numDenseAreas dense areas, which can overlap. Each area is circular, has a certain position and radius and number of points. These values are strored in @a denseAreaXYR and @a numPerArea, respectively.

Used and described in more detail in J. Gehweiler, H. Meyerhenke: A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer. In Proc. 7th High-Performance Grid Computing Workshop (HPGC‘10), in conjunction with 24th IEEE Internatl. Parallel and Distributed Processing Symposium (IPDPS‘10), IEEE, 2010.

PubWebGenerator(numNodes, numberOfDenseAreas, neighborhoodRadius, maxNumberOfNeighbors)

numNodes : count
Up to a few thousand (possibly more if visualization is not desired and quadratic time complexity has been resolved)
numberOfDenseAreas : count
Depending on number of nodes, e.g. [8, 50]
neighborhoodRadius : float
The higher, the better the connectivity [0.1, 0.35]
maxNumberOfNeighbors : count
Maximum degree, a higher value corresponds to better connectivity [4, 40]
generate(self)
class networkit.generators.RegularRingLatticeGenerator

Bases: object

Constructs a regular ring lattice.

RegularRingLatticeGenerator(count nNodes, count nNeighbors)

Constructs the generator.

nNodes : number of nodes in the target graph. nNeighbors : number of neighbors on each side of a node

generate(self)

Generates a rgular ring lattice.

Graph
The generated graph.
class networkit.generators.RmatGenerator

Bases: object

Generates static R-MAT graphs. R-MAT (recursive matrix) graphs are random graphs with n=2^scale nodes and m=nedgeFactor edges. More details at http://www.graph500.org or in the original paper: Deepayan Chakrabarti, Yiping Zhan, Christos Faloutsos: R-MAT: A Recursive Model for Graph Mining. SDM 2004: 442-446.

RmatGenerator(scale, edgeFactor, a, b, c, d)

scale : count
Number of nodes = 2^scale
edgeFactor : count
Number of edges = number of nodes * edgeFactor
a : double
Probability for quadrant upper left
b : double
Probability for quadrant upper right
c : double
Probability for quadrant lower left
d : double
Probability for quadrant lower right
weighted : bool
result graph weighted?
fit(type cls, G, scale=1, initiator=None, kronfit=True, iterations=50)
generate(self)

Graph to be generated according to parameters specified in constructor.

Graph
The generated graph.
paths = {'kronfitPath': None}
setPaths(type cls, kronfitPath)
class networkit.generators.WattsStrogatzGenerator

Bases: object

Generates a graph according to the Watts-Strogatz model.

First, a regular ring lattice is generated. Then edges are rewired
with a given probability.

WattsStrogatzGenerator(count nNodes, count nNeighbors, double p)

Constructs the generator.

nNodes : Number of nodes in the target graph. nNeighbors : number of neighbors on each side of a node p : rewiring probability

generate(self)

Generates a random graph according to the Watts-Strogatz model.

Graph
The generated graph.