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 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:

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

    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 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:
      java.lang.IllegalArgumentException - if number of groups is negative
      java.lang.IllegalArgumentException - if number of nodes in each group is negative
      java.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 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:
      java.lang.IllegalArgumentException - if number of groups is negative
      java.lang.IllegalArgumentException - if number of nodes in each group is negative
      java.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 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:
      java.lang.IllegalArgumentException - if number of groups is negative
      java.lang.IllegalArgumentException - if number of nodes in each group is negative
      java.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 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:
      java.lang.IllegalArgumentException - if number of groups is negative
      java.lang.IllegalArgumentException - if number of nodes in each group is negative
      java.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 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:
      java.lang.IllegalArgumentException - if number of groups is negative
      java.lang.IllegalArgumentException - if number of nodes in each group is negative
      java.lang.IllegalArgumentException - if p is not in [0,1]
      java.lang.IllegalArgumentException - if q is not in [0,1]

  • Method Details

    • 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 interface GraphGenerator<V,​E,​V>
      Parameters:
      target - target graph
      resultMap - result map
      Throws:
      java.lang.IllegalArgumentException - if target is directed
      java.lang.IllegalArgumentException - if self loops are requested but target does not allow them
      java.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