org.jgrapht.generate

Class PlantedPartitionGraphGenerator<V,E>

java.lang.Object

org.jgrapht.generate.PlantedPartitionGraphGenerator<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

public class PlantedPartitionGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>

Create a random $l$-planted partition graph. An $l$-planted partition graph is a random graph on $n = l \cdot k$ vertices subdivided in $l$ groups with $k$ vertices each. Vertices within the same group are connected by an edge with probability $p$, while vertices belonging to different groups are connected by an edge with probability $q$.

The $l$-planted partition model is a special case of the Stochastic Block Model. If the probability matrix is a constant, in the sense that $P_{ij}=p$ for all $i,j$, then the result is the Erdős–Rényi model $\mathcal G(n,p)$. This case is degenerate—the partition into communities becomes irrelevant— but it illustrates a close relationship to the Erdős–Rényi model. For more information on planted graphs, refer to:

1. Condon, A. Karp, R.M. Algorithms for graph partitioning on the planted partition model, Random Structures and Algorithms, Volume 18, Issue 2, p.116-140, 2001
2. Fortunato, S. Community Detection in Graphs, Physical Reports Volume 486, Issue 3-5 p. 75-174, 2010

Since:

April 2018

Author:

Emilio Cruciani

Constructor Summary

Constructors

Constructor and Description
PlantedPartitionGraphGenerator(int l, int k, double p, double q) Construct a new PlantedPartitionGraphGenerator.
PlantedPartitionGraphGenerator(int l, int k, double p, double q, boolean selfLoops) Construct a new PlantedPartitionGraphGenerator.
PlantedPartitionGraphGenerator(int l, int k, double p, double q, long seed) Construct a new PlantedPartitionGraphGenerator.
PlantedPartitionGraphGenerator(int l, int k, double p, double q, long seed, boolean selfLoops) Construct a new PlantedPartitionGraphGenerator.
PlantedPartitionGraphGenerator(int l, int k, double p, double q, Random rng, boolean selfLoops) Construct a new PlantedPartitionGraphGenerator.

Method Summary

Modifier and Type	Method and Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap) Generate an $l$-planted partition graph.
List<Set<V>>	getCommunities() Get the community structure of the graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph, generateGraph, generateGraph

Constructor Detail

PlantedPartitionGraphGenerator

public PlantedPartitionGraphGenerator(int l,
                                      int k,
                                      double p,
                                      double q)

Construct a new PlantedPartitionGraphGenerator.

Parameters:

l - number of groups

k - number of nodes in each group

p - probability of connecting vertices within a group

q - probability of connecting vertices between groups

Throws:

IllegalArgumentException - if number of groups is negative

IllegalArgumentException - if number of nodes in each group is negative

IllegalArgumentException - if p is not in [0,1]

IllegalArgumentException - if q is not in [0,1]

PlantedPartitionGraphGenerator

public PlantedPartitionGraphGenerator(int l,
                                      int k,
                                      double p,
                                      double q,
                                      boolean selfLoops)

Construct a new PlantedPartitionGraphGenerator.

Parameters:

l - number of groups

k - number of nodes in each group

p - probability of connecting vertices within a group

q - probability of connecting vertices between groups

selfLoops - true if the graph allows self loops

Throws:

IllegalArgumentException - if number of groups is negative

IllegalArgumentException - if number of nodes in each group is negative

IllegalArgumentException - if p is not in [0,1]

IllegalArgumentException - if q is not in [0,1]

PlantedPartitionGraphGenerator

public PlantedPartitionGraphGenerator(int l,
                                      int k,
                                      double p,
                                      double q,
                                      long seed)

Construct a new PlantedPartitionGraphGenerator.

Parameters:

l - number of groups

k - number of nodes in each group

p - probability of connecting vertices within a group

q - probability of connecting vertices between groups

seed - seed for the random number generator

Throws:

IllegalArgumentException - if number of groups is negative

IllegalArgumentException - if number of nodes in each group is negative

IllegalArgumentException - if p is not in [0,1]

IllegalArgumentException - if q is not in [0,1]

PlantedPartitionGraphGenerator

public PlantedPartitionGraphGenerator(int l,
                                      int k,
                                      double p,
                                      double q,
                                      long seed,
                                      boolean selfLoops)

Construct a new PlantedPartitionGraphGenerator.

Parameters:

l - number of groups

k - number of nodes in each group

p - probability of connecting vertices within a group

q - probability of connecting vertices between groups

seed - seed for the random number generator

selfLoops - true if the graph allows self loops

Throws:

IllegalArgumentException - if number of groups is negative

IllegalArgumentException - if number of nodes in each group is negative

IllegalArgumentException - if p is not in [0,1]

IllegalArgumentException - if q is not in [0,1]

PlantedPartitionGraphGenerator

public PlantedPartitionGraphGenerator(int l,
                                      int k,
                                      double p,
                                      double q,
                                      Random rng,
                                      boolean selfLoops)

Construct a new PlantedPartitionGraphGenerator.

Parameters:

l - number of groups

k - number of nodes in each group

p - probability of connecting vertices within a group

q - probability of connecting vertices between groups

rng - random number generator

selfLoops - true if the graph allows self loops

Throws:

IllegalArgumentException - if number of groups is negative

IllegalArgumentException - if number of nodes in each group is negative

IllegalArgumentException - if p is not in [0,1]

IllegalArgumentException - if q is not in [0,1]

Method Detail

generateGraph

public void generateGraph(Graph<V,E> target,
                          Map<String,V> resultMap)

Generate an $l$-planted partition graph. Note that the method can be called only once. Must instantiate another PlantedPartitionGraphGenerator object in order to generate another $l$-planted partition graph.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - target graph

resultMap - result map

Throws:

IllegalArgumentException - if target is directed

IllegalArgumentException - if self loops are requested but target does not allow them

IllegalStateException - if generateGraph() is called more than once

getCommunities

public List<Set<V>> getCommunities()

Get the community structure of the graph. The method returns a list of communities, represented as sets of nodes.

Returns:

the community structure of the graph

Throws:

IllegalStateException - if getCommunities() is called before generating the graph