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

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