documentationfor yFiles for HTML 2.5

PageRank

Computes page rank values for all nodes based on their attached edges.

Inheritance Hierarchy
PageRank

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 edge weights and node weights 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:

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)))
})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)))
})

Type Details

yfiles module
view-layout-bridge
yfiles-umd modules
view-layout-bridge
Legacy UMD name
yfiles.analysis.PageRank

See Also

If no initialPageRank is set all nodes have an initial rank of 1.0.
If no nodeWeights are provided, the algorithm assumes that all nodes have weight 1.0.
If no edgeWeights are provided, the algorithm assumes that all edges have weight 1.0.
The damping factor has to lie between 0 and 1 where 0 means all the rank of 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.

Constructors

Properties

Methods