Class PushPullGossip

java.lang.Object
it.unimi.dsi.webgraph.scratch.PushPullGossip

public class PushPullGossip extends Object
Simulates the push-pull gossiping algorithm with a single source on a given undirected graph. The algorithm works in rounds: at each round, some nodes possess an information, and some other do not (at the beginning, the information is possessed by a single node, called the source). At each round, every node x chooses one of its neighbors x'; if x is informed, it communicates the information to x', that thereby becomes informed (push); if x is not informed, it tries to get the information from x', and thereby becomes informed if x' was (pull). The algorithm terminates when a certain fraction θ of the nodes have the information (in the original version, θ=1, which requires the graph to be connected). The algorithm is performed a certain number of times, and the distribution of rounds required for termination is considered.
Author:
Paolo Boldi
  • Constructor Summary

    Constructors
    Constructor
    Description
    PushPullGossip(ImmutableGraph g, Random r, it.unimi.dsi.logging.ProgressLogger pl)
    Creates a new instance for the algorithm execution.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    execution(int source, double theta)
    Performs an execution of the algorithm with given source and threshold.
    void
    init(int source)
    Initializes both informed arrays to the state where only a single source is informed.
    static void
    main(String[] arg)
     
    it.unimi.dsi.stat.SummaryStats
    simulate(int source, double theta, int numberExperiments)
    Simulates the algorithm many times on the same graph and returs statistics about the number of iterations required.
    protected int
    Performs a step of execution.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • PushPullGossip

      public PushPullGossip(ImmutableGraph g, Random r, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new instance for the algorithm execution.
      Parameters:
      g - the graph on which the algorithm is going to be run.
      pl - the progress logger to be used, if any.
  • Method Details

    • step

      protected int step()
      Performs a step of execution.
      Returns:
      the number of nodes that have become informed after this step.
    • init

      public void init(int source)
      Initializes both informed arrays to the state where only a single source is informed.
    • execution

      public int execution(int source, double theta)
      Performs an execution of the algorithm with given source and threshold.
      Parameters:
      source - the only node that is informed at the beginning.
      theta - the fraction of nodes that need to be informed (the algorithm stops as soon as this many nodes have been informed).
      Returns:
      the number of execution steps performed.
    • simulate

      public it.unimi.dsi.stat.SummaryStats simulate(int source, double theta, int numberExperiments)
      Simulates the algorithm many times on the same graph and returs statistics about the number of iterations required.
      Parameters:
      source - the only node that is informed at the beginning of each execution (if negative, it is generated every time at random).
      theta - the fraction of nodes that need to be informed.
      numberExperiments - the number of experiments to be performed.
      Returns:
      a bin containing data about the number of iterations performed during each simulation.
    • main

      Throws:
      IOException
      com.martiansoftware.jsap.JSAPException
      IllegalArgumentException
      ClassNotFoundException
      IllegalAccessException
      InvocationTargetException
      InstantiationException
      NoSuchMethodException