Remarks
The original algorithm was proposed by Sergey Brin and Lawrence Page as PageRank algorithm and refined later in several papers:
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine.
Computer Networks and ISDN Systems, 30(1-7):107-117
1998.
The algorithm starts by initializing the rank value for each node. After that it uses multiple iterations to propagate the rank of a node to its successors. The base factor for each successor is 1. These base factors are multiplied by edgeWeights and nodeWeights if specified.
The final node factors are scaled afterwards to sum up to 1 so the overall rank stays the same after each iteration. The old page rank of the node multiplied with these scaled factors are then distributed to the successors.
When a node can't distribute its rank, e.g. because it has no successors, its rank is distributed between all nodes scaled by their weight (see nodeWeights). Furthermore a damping factor is used so that a share of each nodes' rank isn't propagated to the successors but also distributed between all nodes.
After each iteration, the relative change of each node's page rank ((newRank - oldRank)/oldRank) is calculated. If all page rank changes are below the specified precision or if the maximal iterations are reached, the algorithm stops.
The edgeDirectedness defines the direction of the edges. This in consequence defines the propagation direction of ranks. Edges with a positive directedness value propagate the rank from the source to the target node - this is also the default if the given data provider is null. Edges which have a directedness of 0 are considered to be undirected so that propagation happens from source to target and from target to source. Edges with a negative directedness are considered to have the reverse direction such that they propagate ranks only from target to source.
Other Centrality Measures
yFiles for HTML supports a number of other centrality measures:
- GraphCentrality, ClosenessCentrality – emphasize nodes that have short paths to other nodes
- DegreeCentrality – emphasizes nodes with many edges
- WeightCentrality – emphasizes nodes with highly-weighted edges
- BetweennessCentrality – emphasizes nodes and edges that are part of many short paths
- EigenvectorCentrality – computes the influence a node has on a network. The centrality value is higher if more nodes are connected to that node.
Complexity
O(graph.N() + graph.E())Examples
const result = new PageRank({
nodeWeights: (node) => node.layout.width,
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke!.thickness
: 1,
}).run(graph)
// add node labels for centrality values
// and adjust node size according to centrality
result.pageRank.forEach(({ key, value }) => {
const node = key
const centrality = value
graph.addLabel(node, String(centrality))
graph.setNodeLayout(
node,
new Rect(node.layout.center, new Size(centrality, centrality)),
)
})See Also
Developer's Guide
API
- pageRank
Members
Constructors
Properties
0 and 1 where 0 means all the rank of a node is distributed between all nodes based on their node weight and 1 means all the rank of a node is only distributed between its successors. The default is 0.85.Throws
- Exception ({ name: 'ArgumentError' })
- if the value is not between
0and1.
Gets or sets a mapping that stores the directedness of the edges.
0 are considered to be undirected so that propagation happens from source to target and from target to source. Edges with a negative directedness are considered to have the reverse direction such that they propagate ranks only from target to source.Gets or sets a mapping for edge weights.
Gets or sets a mapping that specifies the initial page rank for each node.
1.0.Gets or sets a mapping for node weights.
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
If nothing is set, all edges of the graph will be processed.
If only the excludes are set, all edges in the graph except those provided in the excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the algorithm
const algorithm = new PageRank({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels for centrality values
result.pageRank.forEach(({ key, value }) =>
graph.addLabel(key, String(value)),
)Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
If nothing is set, all nodes of the graph will be processed.
If only the excludes are set, all nodes in the graph except those provided in the excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the algorithm
const algorithm = new PageRank({
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// add labels for centrality values
result.pageRank.forEach(({ key, value }) =>
graph.addLabel(key, String(value)),
)Methods
Computes page rank values for all nodes based on their attached edges.
The original algorithm was proposed by Sergey Brin and Lawrence Page as PageRank algorithm and refined later in several papers:
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine.
Computer Networks and ISDN Systems, 30(1-7):107-117
1998.
The algorithm starts by initializing the rank value for each node. After that it uses multiple iterations to propagate the rank of a node to its successors. The base factor for each successor is 1. These base factors are multiplied by edgeWeights and nodeWeights if specified.
The final node factors are scaled afterwards to sum up to 1 so the overall rank stays the same after each iteration. The old page rank of the node multiplied with these scaled factors are then distributed to the successors.
When a node can't distribute its rank, e.g. because it has no successors, its rank is distributed between all nodes scaled by their weight (see nodeWeights). Furthermore a damping factor is used so that a share of each nodes' rank isn't propagated to the successors but also distributed between all nodes.
After each iteration, the relative change of each node's page rank ((newRank - oldRank)/oldRank) is calculated. If all page rank changes are below the specified precision or if the maximal iterations are reached, the algorithm stops.
The edgeDirectedness defines the direction of the edges. This in consequence defines the propagation direction of ranks. Edges with a positive directedness value propagate the rank from the source to the target node - this is also the default if the given data provider is null. Edges which have a directedness of 0 are considered to be undirected so that propagation happens from source to target and from target to source. Edges with a negative directedness are considered to have the reverse direction such that they propagate ranks only from target to source.
Other Centrality Measures
yFiles for HTML supports a number of other centrality measures:
- GraphCentrality, ClosenessCentrality – emphasize nodes that have short paths to other nodes
- DegreeCentrality – emphasizes nodes with many edges
- WeightCentrality – emphasizes nodes with highly-weighted edges
- BetweennessCentrality – emphasizes nodes and edges that are part of many short paths
1.0.1.0.1.0.0 and 1 where 0 means all the rank of a node is distributed between all nodes based on their node weight and 1 means all the rank of a node is only distributed between its successors.Parameters
- graph: IGraph
- The input graph to run the algorithm on.
Return Value
- PageRankResult
- A PageRankResult from which the calculated centrality values can be obtained. The values are between
0.0and1.0.
Throws
- Exception ({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Complexity
O(graph.N() + graph.E())Examples
const result = new PageRank({
nodeWeights: (node) => node.layout.width,
edgeWeights: (edge) =>
edge.style instanceof PolylineEdgeStyle
? edge.style.stroke!.thickness
: 1,
}).run(graph)
// add node labels for centrality values
// and adjust node size according to centrality
result.pageRank.forEach(({ key, value }) => {
const node = key
const centrality = value
graph.addLabel(node, String(centrality))
graph.setNodeLayout(
node,
new Rect(node.layout.center, new Size(centrality, centrality)),
)
})