CentralityAlgorithm

This class provides methods to determine various centrality indices of nodes or edges of a graph.

Inheritance Hierarchy

CentralityAlgorithm

Remarks

Note: Methods of this class work with instances of Graph. To calculate centrality measures for IGraph instances use one of the following classes instead:

Centrality indices serve to quantify an intuitive feeling that in most networks some nodes or edges are "more central" than others. The provided methods assign a double value to each node or edge of a graph that represents its centrality. The higher an assigned value, the more central the element is considered by the algorithm.

Also, this class provides convenience methods that normalize the returned centrality values such that they lie within the interval [0,1].

Definitions

Betweenness centrality is a measure for how often a node/edge lies on a shortest path between each pair of nodes in the graph.
Closeness centrality is the reciprocal of the sum of shortest path distances of a node to all other nodes in the graph.
Graph centrality is the reciprocal of the maximum of all shortest path distances from a node to all other nodes in the graph.
Degree centrality is the number of the incoming, outgoing or overall edges incident to a node (measures incoming, outgoing and overall degree).
Weight centrality measures the weight associated with incoming, outgoing, or all edges of a node.
Eigenvector centrality measures the influence of a node by means of a dominant eigenvector of the graph's adjacency matrix.
Page rank measures the relative importance of a node in the graph which is determined based on the edges adjacent to a node. The basic idea is that nodes that are linked to by many other nodes are important.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.Centrality

Static Methods

closenessCentrality

(graph: Graph, closeness: INodeMap, directed: boolean, edgeCosts: IDataProvider)

Computes the closeness centrality for the nodes of a graph.

Remarks

Note: This method works with instances of Graph. To calculate closeness centrality for edges in an IGraph use ClosenessCentrality instead.

Closeness centrality is defined as the reciprocal of the sum of shortest path distances of a node to all other nodes in the graph. Therefore, a node with high closeness centrality has short distances to all other nodes of a graph. If the sum of the shortest path distances is 0, the closeness of a node is set to Number.POSITIVE_INFINITY.

Complexity

O(graph.N()^2 + graph.N() * graph.E()) for unweighted graphs
O((graph.N() * graph.E()) + graph.N()^2 * log(graph.N())) for weighted graphs

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

closeness - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCosts - IDataProvider

the IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost

Domain	Edge
Values	number	a positive value that represents the centrality cost of each edge or `null` if the edges are of equal cost

For non-connected graphs, the centrality values of all nodes will be zero, since the distance to some nodes is infinite.

degreeCentrality

(graph: Graph, centrality: INodeMap, considerInEdges: boolean, considerOutEdges: boolean)

Computes the degree centrality for the nodes of a given graph.

Remarks

Note: This method works with instances of Graph. To calculate degree centrality for edges in an IGraph use DegreeCentrality instead.

Degree centrality is the number of the incoming, outgoing or overall edges incident to a node (measures incoming, outgoing and overall degree).

Complexity

O(graph.N())

Preconditions

At least one of the flags considerInEdges and considerOutEdges must be true.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

centrality - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

considerInEdges - boolean

true if the incoming edges should be considered, false otherwise

considerOutEdges - boolean

true if the outgoing edges should be considered, false otherwise

edgeBetweenness

(graph: Graph, centrality: IEdgeMap, directed: boolean, edgeCosts: IDataProvider)

Computes betweenness centrality for each edge of a given graph.

Remarks

Note: This method works with instances of Graph. To calculate betweenness centrality for nodes and edges in an IGraph use BetweennessCentrality instead.

Betweenness centrality is a measure for how often an edge lies on a shortest path between each pair of nodes in the graph. Removing a central edge will cause many shortest paths to change.

Complexity

O(graph.N() * graph.E()) for unweighted graphs
O(graph.N() * (graph.E() + graph.N()) * log(graph.N()) for weighted graphs

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

centrality - IEdgeMap

the IEdgeMap that will be filled during the execution and returns a double value (centrality) for each edge

Domain	Edge
Values	number	a non-negative value representing the centrality of each edge

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCosts - IDataProvider

the IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost; for invalid input values the algorithm uses cost 1.0

Domain	Edge
Values	number	a positive value that represents the centrality cost of each edge or `null` if the edges are of equal cost

eigenvectorCentrality

(graph: Graph, centralityMap: INodeMap, precision?: number) : boolean

Computes an eigenvector centrality for each node of a given undirected graph.

Remarks

Note: This method works with instances of Graph. To calculate the eigenvector centrality for nodes in an IGraph use EigenvectorCentrality instead.

The centrality values are scaled so that the largest centrality value is 1.0.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the undirected input graph

centralityMap - INodeMap

a node map that can store values of type double. It is used for returning the resulting centrality values (in the interval [0,1]) for each node

Domain	YNode
Values	number	a value between `0.0` and `1.0` that stores the centrality found for this node

precision - number

specifies the precision used during the calculation of the power iteration method (i.e. the maximum possible difference to consider two values as equal)

Returns

↪boolean: whether or not an eigenvector could be found and centralityMap contains valid entries

For some input graphs the power iteration method that is used to calculate the dominant eigenvector doesn't converge and, thus, this method doesn't find a valid solution. This is indicated by the return value of this method. In such cases, we recommend to switch to the pageRank algorithm.

graphCentrality

(graph: Graph, centrality: INodeMap, directed: boolean, edgeCosts: IDataProvider)

Computes the graph centrality for the nodes of a graph.

Remarks

Note: This method works with instances of Graph. To calculate graph centrality for edges in an IGraph use GraphCentrality instead.

Graph centrality is defined as the reciprocal of the maximum of all shortest path distances from a node to all other nodes in the graph. Nodes with high graph centrality have short distances to all other nodes in the graph.

Complexity

O(graph.N()^2 + graph.N() * graph.E()) for unweighted graphs
O((graph.N() * graph.E()) + graph.N()^2 * log(graph.N())) for weighted graphs

Preconditions

A must be given as input that returns for each a zero value that represents the initial closeness centrality.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

centrality - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCosts - IDataProvider

the IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost

Domain	Edge
Values	number	a positive value that represents the centrality cost of each edge or `null` if the edges are of equal cost

For non-connected graphs, the centrality values of all nodes will be zero since the distance to some nodes is infinite.

nodeBetweenness

(graph: Graph, centrality: INodeMap, directed: boolean, edgeCosts: IDataProvider)

Computes betweenness centrality for each node of a given graph.

Remarks

Note: This method works with instances of Graph. To calculate betweenness centrality for nodes and edges in an IGraph use BetweennessCentrality instead.

Betweenness centrality is a measure for how often a node lies on a shortest path between each pair of nodes in the graph. Removing a central edge will cause many shortest paths to change.

Complexity

O(graph.N() * graph.E()) for unweighted graphs
O(graph.N() * (graph.E() + graph.N()) * log(graph.N()) for weighted graphs

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

centrality - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCosts - IDataProvider

the IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost; for invalid input values the algorithm uses cost 1.0

Domain	Edge
Values	number	a positive value that represents the centrality cost of each edge or `null` if the edges are of equal cost

nodeEdgeBetweenness

(graph: Graph, nodeCentrality: INodeMap, edgeCentrality: IEdgeMap, directed: boolean, edgeCosts: IDataProvider)

Computes betweenness centrality for each node and edge of a given graph.

Remarks

Note: This method works with instances of Graph. To calculate betweenness centrality for nodes and edges in an IGraph use BetweennessCentrality instead.

Betweenness centrality is a measure for how often a node/edge lies on a shortest path between each pair of nodes in the graph. Removing a central node/edge will cause many shortest paths to change.

Complexity

O(graph.N() * graph.E()) for unweighted graphs
O(graph.N() * (graph.E() + graph.N()) * log(graph.N()) for weighted graphs

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

nodeCentrality - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

edgeCentrality - IEdgeMap

the IEdgeMap that will be filled during the execution and returns a double value (centrality) for each edge

Domain	Edge
Values	number	a non-negative value representing the centrality of each edge

directed - boolean

true if the graph should be considered as directed, false otherwise

edgeCosts - IDataProvider

the IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost; for invalid input values the algorithm uses cost 1.0

Domain	Edge
Values	number	a positive value that represents the centrality cost of each edge or `null` if the edges of equal cost

normalizeEdgeMap

(graph: Graph, map: IEdgeMap)

Normalizes the double values of a given IEdgeMap by dividing each of them by the maximum of all values (maximum norm).

Preconditions

For each edge e: map.getDouble(e) >= 0

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

map - IEdgeMap

the IEdgeMap that will be filled during the execution and returns a double value from [0,1] interval

Domain	Edge
Values	number	a value from `[0,1]` interval for each edge representing the normalized centrality value

If the maximum value is Double.POSITIVE_INFINITY, all values other than Double.POSITIVE_INFINITY are set to 0.

normalizeNodeMap

(graph: Graph, map: INodeMap)

Normalizes the double values of a given INodeMap by dividing each of them by the maximum of all values (maximum norm).

Preconditions

For each node n: map.getDouble(n) >= 0

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

map - INodeMap

the INodeMap that will be filled during the execution and returns a double value from [0,1] interval

Domain	YNode
Values	number	a value from `[0,1]` interval for each node representing the normalized centrality value

If the maximum value is Double.POSITIVE_INFINITY, all values other than Double.POSITIVE_INFINITY are set to 0.

pageRank

(graph: Graph, pageRank: INodeMap, initialPageRank?: IDataProvider, nodeWeight?: IDataProvider, edgeWeight?: IDataProvider, edgeDirectedness?: IDataProvider, dampingFactor?: number, precision?: number) : number

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

Remarks

Note: This method works with instances of Graph. To calculate the page rank for nodes in an IGraph use PageRank instead.

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 (see IDataProvider initialPageRank). 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 (see data provider edgeWeight and node weights (see data provider nodeWeight 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 data provider nodeWeight). 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 IDataProvider 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.

Complexity

O(graph.N() + graph.E())

ParametersOptions Overload

options - Object
A map of options to pass to the method.

graph - Graph

the graph to calculate the ranks for

pageRank - INodeMap

the INodeMap that will be filled during the execution with the rank value for each node

Domain	YNode
Values	number	a value between `0.0` and `1.0` that stores the page rank for each node

initialPageRank - IDataProvider

The IDataProvider that specifies the initial page rank for each node

Domain	YNode
Values	number	the initial page rank of a node which has to be non-negative

nodeWeight - IDataProvider

the IDataProvider that specifies the weight for each node

Domain	YNode
Values	number	the weight of a node

edgeWeight - IDataProvider

the IDataProvider that specifies the weight for each edge

Domain	Edge
Values	number	the weight of an edge

edgeDirectedness - IDataProvider

IDataProvider that stores the directedness of the edges

Domain	Edge
Values	number	the directedness of an edge

dampingFactor - number

a value between 0 and 1 denoting the factor of a node's rank that shall be distributed to its successors (a good default value is 0.85)

precision - number

the non-negative precision of the calculated page ranks (a good default value is 0.001)

Returns

↪number: the sum of all node ranks

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.

If IDataProvider initialPageRank is null, the algorithm assumes that all nodes have an initial rank of 1.0.

If IDataProvider nodeWeight is null, the algorithm assumes that all nodes have weight 1.0.

If IDataProvider edgeWeight is null, the algorithm assumes that all edges have weight 1.0.

If IDataProvider edgeDirectedness is null, the algorithm assumes that all edges have directedness 1.0, i.e. are directed from source to target.

weightCentrality

(graph: Graph, centrality: INodeMap, considerInEdges: boolean, considerOutEdges: boolean, edgeWeights: IDataProvider)

Computes the weight centrality for the nodes of a graph.

Remarks

Note: This method works with instances of Graph. To calculate weight centrality for edges in an IGraph use WeightCentrality instead.

Weight centrality measures the weight associated with incoming, outgoing, or all edges of a node.

Complexity

O(graph.E())

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

centrality - INodeMap

the INodeMap that will be filled during the execution and returns a double value (centrality) for each node

Domain	YNode
Values	number	a non-negative value representing the centrality of each node

considerInEdges - boolean

true if the incoming edges should be considered, false otherwise

considerOutEdges - boolean

true if the outgoing edges should be considered, false otherwise

edgeWeights - IDataProvider

the IDataProvider that returns a positive double value (weight) or null if the edges are considered to have uniform weight of 1.0

Domain	Edge
Values	number	a positive value that represents the weight of each edge or `null` if the edges are considered to have uniform weight of `1.0`

Weight centrality degenerates to degree centrality when the edges have uniform weight. In particular, when parameter edgeWeights is null, then degreeCentrality is invoked instead.