org.jgrapht.generate

## Class 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
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

All Methods
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
• ### 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