public class PageRank extends Object implements DynamicAlgorithm, 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 |
---|---|
protected double |
dampingFactor
Current damping factor
|
static double |
DEFAULT_DAMPING_FACTOR
Default damping factor
|
static double |
DEFAULT_PRECISION
Default precision
|
static String |
DEFAULT_RANK_ATTRIBUTE
Default rank attribute
|
protected Graph |
graph
Our graph
|
protected int |
iterationCount
total iteration count
|
protected List<Double> |
newRanks
Used to temporary store the new ranks during an iteration
|
protected double |
normDiff
The L1 norm of the difference between two consecutive rank vectors
|
protected double |
precision
Current numeric precision
|
protected String |
rankAttribute
Current rank attribute
|
protected boolean |
upToDate
Am I up to date ?
|
protected boolean |
verbose
Verbose mode
|
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)
An edge was inserted in graph.
|
void |
edgeRemoved(String sourceId,
long timeId,
String edgeId)
An edge of graph was removed.The nodes the edge connects may already have
been removed from the graph.
|
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(Node node)
Returns the rank of a node.
|
String |
getRankAttribute()
Returns the current rank attribute
|
void |
graphCleared(String sourceId,
long timeId)
The whole graph was cleared.
|
void |
init(Graph graph)
Initialization of the algorithm.
|
protected void |
iteration() |
void |
nodeAdded(String sourceId,
long timeId,
String nodeId)
A node was inserted in the given graph.
|
void |
nodeRemoved(String sourceId,
long timeId,
String nodeId)
A node was removed from the graph.
|
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)
Since dynamic graphs are based on discrete event modifications, the
notion of step is defined to simulate elapsed time between events.
|
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
protected double dampingFactor
protected double precision
protected String rankAttribute
protected boolean upToDate
protected double normDiff
protected int iterationCount
protected boolean verbose
public PageRank()
public 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(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)
ElementSink
nodeAdded
in interface ElementSink
sourceId
- Identifier of the graph where the node was added.nodeId
- Identifier of the added node.public void nodeRemoved(String sourceId, long timeId, String nodeId)
ElementSink
nodeRemoved
in interface ElementSink
sourceId
- Identifier of the graph where the node will be removed.nodeId
- Identifier of the removed node.public void edgeAdded(String sourceId, long timeId, String edgeId, String fromNodeId, String toNodeId, boolean directed)
ElementSink
edgeAdded
in interface ElementSink
sourceId
- Identifier of the graph where the edge was added.edgeId
- Identifier of the added edge.fromNodeId
- Identifier of the first node of the edge.toNodeId
- Identifier of the second node of the edge.directed
- If true, the edge is directed.public void edgeRemoved(String sourceId, long timeId, String edgeId)
ElementSink
edgeRemoved
in interface ElementSink
sourceId
- The graph where the edge will be removed.edgeId
- The edge that will be removed.public void graphCleared(String sourceId, long timeId)
ElementSink
graphCleared
in interface ElementSink
sourceId
- The graph cleared.public void stepBegins(String sourceId, long timeId, double step)
ElementSink
Since dynamic graphs are based on discrete event modifications, the notion of step is defined to simulate elapsed time between events. So a step is a event that occurs in the graph, it does not modify it but it gives a kind of timestamp that allow the tracking of the progress of the graph over the time.
This kind of event is useful for dynamic algorithms that listen to the dynamic graph and need to measure the time in the graph's evolution.
stepBegins
in interface ElementSink
sourceId
- Identifier of the graph where the step starts.timeId
- A numerical value that may give a timestamp to track the
evolution of the graph over the time.protected void iteration()
public double getRank(Node node)
node
- A nodepublic int getIterationCount()
compute()
. It is reset to zero in the calls to
init(Graph)
.WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses