org.graphstream.algorithm

## Class PageRank

• java.lang.Object
• org.graphstream.algorithm.PageRank
• All Implemented Interfaces:
Algorithm, DynamicAlgorithm, org.graphstream.stream.ElementSink

```public class PageRank
extends java.lang.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 d she chooses a random outgoing arc and with probability 1 - d she "teleports" to a random node (possibly not connected to the current). The probability d is called damping factor. By default it is 0.85 but it can be customized (see `setDampingFactor(double)`). The ranks are real numbers between 0 and 1 and sum up to one.

## Usage

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.

## Example

``` Graph graph = new SingleGraph("test");
"node {fill-color: red; size-mode: dyn-size;} edge {fill-color:grey;}");
graph.display();

DorogovtsevMendesGenerator generator = new DorogovtsevMendesGenerator();
generator.setDirectedEdges(true, true);

PageRank pageRank = new PageRank();
pageRank.init(graph);

generator.begin();
while (graph.getNodeCount() < 100) {
generator.nextEvents();
for (Node node : graph) {
double rank = pageRank.getRank(node);
5 + Math.sqrt(graph.getNodeCount() * rank * 20));
}
}
```
Computational Complexity:
Each iteration takes O(m + n) time, where n is the number of nodes and m is the number of edges. The number of iterations needed to converge depends on the desired precision.
Scientific Reference:
Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. The PageRank citation ranking: Bringing order to the Web. 1999
• ### Field Summary

Fields
Modifier and Type Field and Description
`static double` `DEFAULT_DAMPING_FACTOR`
Default damping factor
`static double` `DEFAULT_PRECISION`
Default precision
`static java.lang.String` `DEFAULT_RANK_ATTRIBUTE`
Default rank attribute
• ### Constructor Summary

Constructors
Constructor and Description
`PageRank()`
Creates a new instance.
```PageRank(double dampingFactor, double precision, java.lang.String rankAttribute)```
Creates a new instance.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Run the algorithm.
`java.lang.String` `defaultResult()`
`void` ```edgeAdded(java.lang.String sourceId, long timeId, java.lang.String edgeId, java.lang.String fromNodeId, java.lang.String toNodeId, boolean directed)```
`void` ```edgeRemoved(java.lang.String sourceId, long timeId, java.lang.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.
`java.lang.String` `getRankAttribute()`
Returns the current rank attribute
`void` ```graphCleared(java.lang.String sourceId, long timeId)```
`void` `init(org.graphstream.graph.Graph graph)`
Initialization of the algorithm.
`void` ```nodeAdded(java.lang.String sourceId, long timeId, java.lang.String nodeId)```
`void` ```nodeRemoved(java.lang.String sourceId, long timeId, java.lang.String nodeId)```
`void` `setDampingFactor(double dampingFactor)`
Sets the damping factor.
`void` `setPrecision(double precision)`
Sets the numeric precision.
`void` `setRankAttribute(java.lang.String rankAttribute)`
Sets the rank attribute.
`void` `setVerbose(boolean verbose)`
Switches on or off the verbose mode.
`void` ```stepBegins(java.lang.String sourceId, long timeId, double step)```
`void` `terminate()`
Terminate the dynamic algorithm.
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### DEFAULT_DAMPING_FACTOR

`public static final double DEFAULT_DAMPING_FACTOR`
Default damping factor
Constant Field Values
• #### DEFAULT_PRECISION

`public static final double DEFAULT_PRECISION`
Default precision
Constant Field Values
• #### DEFAULT_RANK_ATTRIBUTE

`public static final java.lang.String DEFAULT_RANK_ATTRIBUTE`
Default rank attribute
Constant Field Values
• ### Constructor Detail

• #### PageRank

`public PageRank()`
Creates a new instance. The damping factor, the precision and the rank attribute are set to their default values
• #### PageRank

```public PageRank(double dampingFactor,
double precision,
java.lang.String rankAttribute)```
Creates a new instance.
Parameters:
`dampingFactor` - Damping factor
`precision` - Numeric precision
`rankAttribute` - Rank attribute
• ### Method Detail

• #### getDampingFactor

`public double getDampingFactor()`
Returns the current damping factor.
Returns:
The current damping factor
• #### setDampingFactor

```public void setDampingFactor(double dampingFactor)
throws java.lang.IllegalArgumentException```
Sets the damping factor.
Parameters:
`dampingFactor` - The new damping factor
Throws:
`java.lang.IllegalArgumentException` - If the damping factor is less than 0.01 or greater than 0.99
• #### getPrecision

`public double getPrecision()`
Returns the currently used numeric precision
Returns:
The precision
• #### setPrecision

```public void setPrecision(double precision)
throws java.lang.IllegalArgumentException```
Sets the numeric precision. Precision values close to zero lead to more accurate results, but slower convergence
Parameters:
`precision` - The new precision
Throws:
`java.lang.IllegalArgumentException` - if the precision is less than 1.0e-7
• #### getRankAttribute

`public java.lang.String getRankAttribute()`
Returns the current rank attribute
Returns:
The current rank attribute
• #### setRankAttribute

```public void setRankAttribute(java.lang.String rankAttribute)
throws java.lang.IllegalStateException```
Sets the rank attribute. The computed ranks of each node are stored as values of this attribute.
Parameters:
`rankAttribute` - The node attribute used to store the computed ranks
Throws:
`java.lang.IllegalStateException` - if the algorithm is already initialized
• #### setVerbose

`public void setVerbose(boolean verbose)`
Switches on or off the verbose mode. In verbose mode the algorithm prints at each iteration the number of iterations and the L1 norm of the difference between the current and the previous rank vectors.
Parameters:
`verbose` - Verbose mode
• #### init

`public void init(org.graphstream.graph.Graph graph)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`graph` - The graph this algorithm is using.
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
`Algorithm.init(Graph)`
• #### terminate

`public void terminate()`
Description copied from interface: `DynamicAlgorithm`
Terminate the dynamic algorithm.
Specified by:
`terminate` in interface `DynamicAlgorithm`
`Algorithm.init(org.graphstream.graph.Graph)`
• #### defaultResult

`public java.lang.String defaultResult()`

```public void nodeAdded(java.lang.String sourceId,
long timeId,
java.lang.String nodeId)```
Specified by:
`nodeAdded` in interface `org.graphstream.stream.ElementSink`
• #### nodeRemoved

```public void nodeRemoved(java.lang.String sourceId,
long timeId,
java.lang.String nodeId)```
Specified by:
`nodeRemoved` in interface `org.graphstream.stream.ElementSink`

```public void edgeAdded(java.lang.String sourceId,
long timeId,
java.lang.String edgeId,
java.lang.String fromNodeId,
java.lang.String toNodeId,
boolean directed)```
Specified by:
`edgeAdded` in interface `org.graphstream.stream.ElementSink`
• #### edgeRemoved

```public void edgeRemoved(java.lang.String sourceId,
long timeId,
java.lang.String edgeId)```
Specified by:
`edgeRemoved` in interface `org.graphstream.stream.ElementSink`
• #### graphCleared

```public void graphCleared(java.lang.String sourceId,
long timeId)```
Specified by:
`graphCleared` in interface `org.graphstream.stream.ElementSink`
• #### stepBegins

```public void stepBegins(java.lang.String sourceId,
long timeId,
double step)```
Specified by:
`stepBegins` in interface `org.graphstream.stream.ElementSink`
• #### getRank

`public double getRank(org.graphstream.graph.Node node)`
Returns the rank of a node. If the ranks are not up to date, recomputes them
Parameters:
`node` - A node
Returns:
The rank of the node
• #### getIterationCount

`public int getIterationCount()`
Returns the total number of iterations. This number accumulates the number of iterations performed by each call to `compute()`. It is reset to zero in the calls to `init(Graph)`.
Returns:
The number of iterations