Graph generation algorithms

The RELISON framework contains the following graph generators:

All the graph generators are configured in the following way:

GraphGenerator<U> gen = new GraphGenerator<>() // Substitute here the corresponding generator
gen.configure(arg1,arg2,...,argN)

Then, the graphs are generated with:

Graph<U> graph = gen.generate()

Complete

The complete graph generator creates a network where every pair of nodes is connected. It is defined in the CompleteGraphGenerator class.

Arguments

The arguments for configuring a complete graph are:

  • directed: if the graph to generate is directed.

  • numNodes: the number of nodes in the network.

  • selfloops: true if we also add links between a node and itself.

  • generator: a node generator.

Empty

The empty graph generator creates a network without links. It is defined in the EmptyGraphGenerator class (and the EmptyMultiGraphGenerator for multigraphs).

Arguments

The arguments for configuring an empty graph are:

  • directed: if the graph to generate is directed.

  • weighted: the number of nodes in the network.

Preferential attachment

This generator starts with a fully connected set of nodes. Then, iteratively, a new node appears in the network, and creates a fixed amount of links to the nodes already in the network. The link destinations are selected with a probability proportional to their in-degree.

Reference: A-L. Barabási, R. Albert. Emergence of Scaling in Random Networks. Science 286(5439), pp. 509-512 (1999)

Arguments

The arguments for configuring a preferential attachment network are:

  • directed: true if the graph we want to generate is directed, false otherwise.

  • initialNodes: the number of initial nodes.

  • numIter: the number of iterations, i.e. the number of additional nodes to add.

  • numEdges: the number of edges to add each iteration.

  • generator: a node generator.

Random

This generator creates a network where the nodes are connected with a certain probability.

Reference: P. Erdös, A. Rényi. On Random Graphs. I, Publicationes Mathematicae Debrecen 6(1), pp. 290-297 (1959)

Arguments

The arguments for configuring a random Erdös-Renyi network are:

  • directed: true if the graph we want to generate is directed, false otherwise.

  • numNodes: the number of nodes in the network.

  • prob: the probability that two nodes are joined with a link.

  • generator: a node generator.

Watts-Strogatz

This generator first creates a ringed network, where each user is connected to other n nodes. Then, with certain probability, each link is randomly reconnected to other node.

Reference: D.J. Watts, S.H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature 393(6684), pp. 440-442 (1998)

Arguments

The arguments for configuring a random Erdös-Renyi network are:

  • directed: true if the graph we want to generate is directed, false otherwise.

  • numNodes: the number of nodes in the network.

  • meanDegree: the average degree of each node in the initial network (only int values).

  • beta: the probability of rewiring an edge.

  • generator: a node generator.