Algorithms

Erdos-Renyi Model

This module contains different functions for generating a random graphs using Erdos-Renyi models G(n, p) and G(n, m)

algorithms.erdos_renyi.compare_edge_count(n, p, seed=None)

Compares number of edges of G(n,p) and G(n, m) where m = floor(p*C_2^n)

Parameters:

• n – Number of nodes
• p – Probability of having an edge
• seed – Seed for generating random numbers. If it is not specified, time stamp is used

Returns:

the ratio suze(E(G(n, p))) / size(E(G(n, m)))

algorithms.erdos_renyi.er_nm(n, m, seed=None)

Creates a random graph following Erdos-Renyi G(n,m) model.

Parameters:

• n – Number of nodes
• m – Number of edges
• seed – Seed for generating random numbers. If it is not specified, time stamp is used.

Returns:

a Graph object

algorithms.erdos_renyi.er_np(n, p, seed=None)

Creates a random graph following Erdos-Renyi G(n, p) model.

Parameters:

• n – number of nodes
• p – probability of an edge existing between any pair of nodes
• seed – Seed for generating random number. If it is not specified, time stamp is used.

Returns:

a Graph object

Newman Model

This module contains a functions for generating random graph using configuration model. In configuration model, one represents a graph using degree sequence. The actual graph is obtained by randomly connecting stubs of vertices.

algorithms.newman_model.configure_sequence(degree_seq)

Given a degree sequence, creates a random graph following configuration model, i.e., by connecting stubs of vertices.

Parameters:degree_seq – the degree sequence of a graph Returns:A set of tuples, representing the edges.

algorithms.newman_model.degree_sequence_lognormal(n, mu, sigma)

Generates a degree sequnce following k-regular distribution

Parameters:

• n – Number of vertices.
• mu – The parameter mu for lognormal distribution
• sigma – The parameter sigma for lognormal distribution

Returns:

A list containing n integers representing degrees of vertices following lognormal distribution

algorithms.newman_model.degree_sequence_regular(n, k)

Generates a degree sequnce following k-regular distribution

Parameters:

• n – Number of vertices.
• k – The parameter k for k-regular distribution

Returns:

A list containing n integers representing degrees of vertices following k-regular distribution.

algorithms.newman_model.irregular_edge_count(edges)

Computes ratio of multiedges and loops and simple edges

Parameters:edges – A list of tuples representing the set of edges of a graph. Returns:The ratio described above.

Watts-Strogatz model

This module contains functions for constructing a random graph following the Watts-Strogatz model.

algorithms.watts_strogatz.create_regular_ring_lattice(n, k)

Creates a regular ring lattice graphs.

Parameters:

• n – (integer) Number of vertices.
• k – (integer) Number of neighbours.

Returns:

a Graph instance representing the ring graph.

algorithms.watts_strogatz.watts_strogatz(n, k, beta, seed=1)

Creates a random graph following Watts-Strogatz model.

Parameters:

• n – (integer) Number of vertices.
• k – (integer) Number of neighbours. Must be even.
• beta – (float) Rewiring probability.
• seed – Seed for the random number generator.

Returns:

(Graph) a graph object

Barabasi-Albert Model

This module contains functions for constructing a random graph following the Barabasi-Albert model.

algorithms.barabasi_albert.barabasi_albert(N, m, g=None, n=None, p=None, seed=1)

Creates a random graph following Barabasi-Albert model.

Parameters:

• N – Number of vertices.
• m – Number of neighbors for every new node.
• g – A starting small network. If it is None, a small network is generated using erdos renyi model.

Returns:

An instance of Graph representing the created graph.