Package org.jgrapht.generate
Class PlantedPartitionGraphGenerator<V,E>
- java.lang.Object
-
- org.jgrapht.generate.PlantedPartitionGraphGenerator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphGenerator<V,E,V>
public class PlantedPartitionGraphGenerator<V,E> extends java.lang.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:
- 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
- Fortunato, S. Community Detection in Graphs, Physical Reports Volume 486, Issue 3-5 p. 75-174, 2010
- Author:
- Emilio Cruciani
-
-
Constructor Summary
Constructors Constructor 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, java.util.Random rng, boolean selfLoops)
Construct a new PlantedPartitionGraphGenerator.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
generateGraph(Graph<V,E> target, java.util.Map<java.lang.String,V> resultMap)
Generate an $l$-planted partition graph.java.util.List<java.util.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 groupsk
- number of nodes in each groupp
- probability of connecting vertices within a groupq
- probability of connecting vertices between groups- Throws:
java.lang.IllegalArgumentException
- if number of groups is negativejava.lang.IllegalArgumentException
- if number of nodes in each group is negativejava.lang.IllegalArgumentException
- if p is not in [0,1]java.lang.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 groupsk
- number of nodes in each groupp
- probability of connecting vertices within a groupq
- probability of connecting vertices between groupsselfLoops
- true if the graph allows self loops- Throws:
java.lang.IllegalArgumentException
- if number of groups is negativejava.lang.IllegalArgumentException
- if number of nodes in each group is negativejava.lang.IllegalArgumentException
- if p is not in [0,1]java.lang.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 groupsk
- number of nodes in each groupp
- probability of connecting vertices within a groupq
- probability of connecting vertices between groupsseed
- seed for the random number generator- Throws:
java.lang.IllegalArgumentException
- if number of groups is negativejava.lang.IllegalArgumentException
- if number of nodes in each group is negativejava.lang.IllegalArgumentException
- if p is not in [0,1]java.lang.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 groupsk
- number of nodes in each groupp
- probability of connecting vertices within a groupq
- probability of connecting vertices between groupsseed
- seed for the random number generatorselfLoops
- true if the graph allows self loops- Throws:
java.lang.IllegalArgumentException
- if number of groups is negativejava.lang.IllegalArgumentException
- if number of nodes in each group is negativejava.lang.IllegalArgumentException
- if p is not in [0,1]java.lang.IllegalArgumentException
- if q is not in [0,1]
-
PlantedPartitionGraphGenerator
public PlantedPartitionGraphGenerator(int l, int k, double p, double q, java.util.Random rng, boolean selfLoops)
Construct a new PlantedPartitionGraphGenerator.- Parameters:
l
- number of groupsk
- number of nodes in each groupp
- probability of connecting vertices within a groupq
- probability of connecting vertices between groupsrng
- random number generatorselfLoops
- true if the graph allows self loops- Throws:
java.lang.IllegalArgumentException
- if number of groups is negativejava.lang.IllegalArgumentException
- if number of nodes in each group is negativejava.lang.IllegalArgumentException
- if p is not in [0,1]java.lang.IllegalArgumentException
- if q is not in [0,1]
-
-
Method Detail
-
generateGraph
public void generateGraph(Graph<V,E> target, java.util.Map<java.lang.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 interfaceGraphGenerator<V,E,V>
- Parameters:
target
- target graphresultMap
- result map- Throws:
java.lang.IllegalArgumentException
- if target is directedjava.lang.IllegalArgumentException
- if self loops are requested but target does not allow themjava.lang.IllegalStateException
- if generateGraph() is called more than once
-
getCommunities
public java.util.List<java.util.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:
java.lang.IllegalStateException
- if getCommunities() is called before generating the graph
-
-