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 TypeMethodDescriptionintexecution(int source, double theta) Performs an execution of the algorithm with given source and threshold.voidinit(int source) Initializes both informed arrays to the state where only a single source is informed.static voidit.unimi.dsi.stat.SummaryStatssimulate(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 intstep()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:
IOExceptioncom.martiansoftware.jsap.JSAPExceptionIllegalArgumentExceptionClassNotFoundExceptionIllegalAccessExceptionInvocationTargetExceptionInstantiationExceptionNoSuchMethodException
-