public class PageRank extends Object implements DynamicAlgorithm, org.graphstream.stream.ElementSink
The PageRank is an algorithm that measures the "importance" of the nodes in a
graph. It assigns to each node a rank. This rank corresponds to the
probability that a "random surfer" visits the node. The surfer goes from node
to node in the following way: with probability setDampingFactor(double)
). The ranks are real
numbers between 0 and 1 and sum up to one.
This implementation uses a variant of the power iteration algorithm to
compute the node ranks. It computes the approximate ranks iteratively going
closer to the exact values at each iteration. The accuracy can be controlled
by a precision parameter (see setPrecision(double)
). When the L1
norm of the difference between two consecutive rank vectors becomes less than
this parameter, the result is considered precise enough and the computation
stops.
This implementation works with both directed and undirected edges. An undirected edge acts as two directed arcs.
The graph dynamics is taken into account and the ranks are not computed from
scratch at each modification in the structure of the graph. However, the
ranks become less and less accurate after each modification. To establish the
desired precision, one must either explicitly call compute()
or ask
for a rank of a node by calling getRank(Node)
.
The computed ranks are stored in node attribute. The name of this attribute
can be changed by a call to setRankAttribute(String)
but only before
the call to init(Graph)
. Another way to obtain the ranks is to call
getRank(Node)
. The second method is preferable because it will
update the ranks if needed and will always return values within the desired
precision.
Graph graph = new SingleGraph("test"); graph.addAttribute("ui.antialias", true); graph.addAttribute("ui.stylesheet", "node {fill-color: red; size-mode: dyn-size;} edge {fill-color:grey;}"); graph.display(); DorogovtsevMendesGenerator generator = new DorogovtsevMendesGenerator(); generator.setDirectedEdges(true, true); generator.addSink(graph); PageRank pageRank = new PageRank(); pageRank.init(graph); generator.begin(); while (graph.getNodeCount() < 100) { generator.nextEvents(); for (Node node : graph) { double rank = pageRank.getRank(node); node.addAttribute("ui.size", 5 + Math.sqrt(graph.getNodeCount() * rank * 20)); node.addAttribute("ui.label", String.format("%.2f%%", rank * 100)); } Thread.sleep(1000); }
Modifier and Type | Field and Description |
---|---|
static double |
DEFAULT_DAMPING_FACTOR
Default damping factor
|
static double |
DEFAULT_PRECISION
Default precision
|
static String |
DEFAULT_RANK_ATTRIBUTE
Default rank attribute
|
Constructor and Description |
---|
PageRank()
Creates a new instance.
|
PageRank(double dampingFactor,
double precision,
String rankAttribute)
Creates a new instance.
|
Modifier and Type | Method and Description |
---|---|
void |
compute()
Run the algorithm.
|
void |
edgeAdded(String sourceId,
long timeId,
String edgeId,
String fromNodeId,
String toNodeId,
boolean directed) |
void |
edgeRemoved(String sourceId,
long timeId,
String edgeId) |
double |
getDampingFactor()
Returns the current damping factor.
|
int |
getIterationCount()
Returns the total number of iterations.
|
double |
getPrecision()
Returns the currently used numeric precision
|
double |
getRank(org.graphstream.graph.Node node)
Returns the rank of a node.
|
String |
getRankAttribute()
Returns the current rank attribute
|
void |
graphCleared(String sourceId,
long timeId) |
void |
init(org.graphstream.graph.Graph graph)
Initialization of the algorithm.
|
void |
nodeAdded(String sourceId,
long timeId,
String nodeId) |
void |
nodeRemoved(String sourceId,
long timeId,
String nodeId) |
void |
setDampingFactor(double dampingFactor)
Sets the damping factor.
|
void |
setPrecision(double precision)
Sets the numeric precision.
|
void |
setRankAttribute(String rankAttribute)
Sets the rank attribute.
|
void |
setVerbose(boolean verbose)
Switches on or off the verbose mode.
|
void |
stepBegins(String sourceId,
long timeId,
double step) |
void |
terminate()
Terminate the dynamic algorithm.
|
public static final double DEFAULT_DAMPING_FACTOR
public static final double DEFAULT_PRECISION
public static final String DEFAULT_RANK_ATTRIBUTE
public PageRank()
public PageRank(double dampingFactor, double precision, String rankAttribute)
dampingFactor
- Damping factorprecision
- Numeric precisionrankAttribute
- Rank attributepublic double getDampingFactor()
public void setDampingFactor(double dampingFactor) throws IllegalArgumentException
dampingFactor
- The new damping factorIllegalArgumentException
- If the damping factor is less than 0.01 or greater than 0.99public double getPrecision()
public void setPrecision(double precision) throws IllegalArgumentException
precision
- The new precisionIllegalArgumentException
- if the precision is less than 1.0e-7public String getRankAttribute()
public void setRankAttribute(String rankAttribute) throws IllegalStateException
rankAttribute
- The node attribute used to store the computed ranksIllegalStateException
- if the algorithm is already initializedpublic void setVerbose(boolean verbose)
verbose
- Verbose modepublic void init(org.graphstream.graph.Graph graph)
Algorithm
Algorithm.compute()
method to initialize or reset the algorithm according
to the new given graph.public void compute()
Algorithm
Algorithm.init(Graph)
method has to be called
before computing.compute
in interface Algorithm
Algorithm.init(Graph)
public void terminate()
DynamicAlgorithm
terminate
in interface DynamicAlgorithm
Algorithm.init(org.graphstream.graph.Graph)
public void nodeAdded(String sourceId, long timeId, String nodeId)
nodeAdded
in interface org.graphstream.stream.ElementSink
public void nodeRemoved(String sourceId, long timeId, String nodeId)
nodeRemoved
in interface org.graphstream.stream.ElementSink
public void edgeAdded(String sourceId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
edgeAdded
in interface org.graphstream.stream.ElementSink
public void edgeRemoved(String sourceId, long timeId, String edgeId)
edgeRemoved
in interface org.graphstream.stream.ElementSink
public void graphCleared(String sourceId, long timeId)
graphCleared
in interface org.graphstream.stream.ElementSink
public void stepBegins(String sourceId, long timeId, double step)
stepBegins
in interface org.graphstream.stream.ElementSink
public double getRank(org.graphstream.graph.Node node)
node
- A nodepublic int getIterationCount()
compute()
. It is reset to zero in the calls to
init(Graph)
.Copyright © 2015. All rights reserved.