Package it.unimi.dsi.webgraph.scratch
Class PushPullGossip
java.lang.Object
it.unimi.dsi.webgraph.scratch.PushPullGossip
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
ConstructorsConstructorDescriptionPushPullGossip
(ImmutableGraph g, Random r, it.unimi.dsi.logging.ProgressLogger pl) Creates a new instance for the algorithm execution. -
Method Summary
Modifier and TypeMethodDescriptionint
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
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
step()
Performs a step of execution.
-
Constructor Details
-
PushPullGossip
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
public static void main(String[] arg) throws IOException, com.martiansoftware.jsap.JSAPException, IllegalArgumentException, ClassNotFoundException, IllegalAccessException, InvocationTargetException, InstantiationException, NoSuchMethodException - Throws:
IOException
com.martiansoftware.jsap.JSAPException
IllegalArgumentException
ClassNotFoundException
IllegalAccessException
InvocationTargetException
InstantiationException
NoSuchMethodException
-