Module org.jgrapht.core
Package 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
Author:
Emilio Cruciani

  • Constructor Details

    • 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 Details

    • 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