Search this API

## y.algo Class Centrality

```java.lang.Object
y.algo.Centrality
```

`public class Centralityextends java.lang.Object`

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

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.

Method Summary
`static void` ```closenessCentrality(Graph graph, NodeMap closeness, boolean directed, DataProvider edgeCosts)```
Computes the closeness centrality for the nodes of a graph.
`static void` ```degreeCentrality(Graph graph, NodeMap centrality, boolean considerInEdges, boolean considerOutEdges)```
Computes the degree centrality for the nodes of a given graph.
`static void` ```edgeBetweenness(Graph graph, EdgeMap centrality, boolean directed, DataProvider edgeCosts)```
Computes betweenness centrality for each edge of a given graph.
`static boolean` ```eigenvectorCentrality(Graph graph, NodeMap centralityMap)```
Computes an eigenvector centrality for each node of a given undirected, unweighted graph.
`static boolean` ```eigenvectorCentrality(Graph graph, NodeMap centralityMap, double precision)```
Computes an eigenvector centrality for each node of a given undirected graph.
`static void` ```graphCentrality(Graph graph, NodeMap centrality, boolean directed, DataProvider edgeCosts)```
Computes the graph centrality for the nodes of a graph.
`static void` ```nodeBetweenness(Graph graph, NodeMap centrality, boolean directed, DataProvider edgeCosts)```
Computes betweenness centrality for each node of a given graph.
`static void` ```nodeEdgeBetweenness(Graph graph, NodeMap nodeCentrality, EdgeMap edgeCentrality, boolean directed, DataProvider edgeCosts)```
Computes betweenness centrality for each node and edge of a given graph.
`static void` ```normalize(Graph graph, EdgeMap map)```
Normalizes the `double` values of a given `EdgeMap` by dividing each of them by the maximum of all values (maximum norm).
`static void` ```normalize(Graph graph, NodeMap map)```
Normalizes the `double` values of a given `NodeMap` by dividing each of them by the maximum of all values (maximum norm).
`static double` ```pageRank(Graph graph, NodeMap pageRank)```
Computes page rank values for all nodes based on their attached edges.
`static double` ```pageRank(Graph graph, NodeMap pageRank, DataProvider initialPageRank, DataProvider nodeWeight, DataProvider edgeWeight, DataProvider edgeDirectedness)```
Computes page rank values for all nodes based on their attached edges.
`static double` ```pageRank(Graph graph, NodeMap pageRank, DataProvider initialPageRank, DataProvider nodeWeight, DataProvider edgeWeight, DataProvider edgeDirectedness, double dampingFactor, double precision)```
Computes page rank values for all nodes based on their attached edges.
`static void` ```weightCentrality(Graph graph, NodeMap centrality, boolean considerInEdges, boolean considerOutEdges, DataProvider edgeWeights)```
Computes the weight centrality for the nodes of a graph.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### nodeBetweenness

```public static void nodeBetweenness(Graph graph,
NodeMap centrality,
boolean directed,
DataProvider edgeCosts)```
Computes betweenness centrality for each node of a given graph.

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:
`graph` - the input graph
`centrality` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCosts` - the `DataProvider` 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`

### edgeBetweenness

```public static void edgeBetweenness(Graph graph,
EdgeMap centrality,
boolean directed,
DataProvider edgeCosts)```
Computes betweenness centrality for each edge of a given graph.

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:
`graph` - the input graph
`centrality` - the `EdgeMap` that will be filled during the execution and returns a double value (centrality) for each edge
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCosts` - the `DataProvider` 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`

### nodeEdgeBetweenness

```public static void nodeEdgeBetweenness(Graph graph,
NodeMap nodeCentrality,
EdgeMap edgeCentrality,
boolean directed,
DataProvider edgeCosts)```
Computes betweenness centrality for each node and edge of a given graph.

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:
`graph` - the input graph
`nodeCentrality` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`edgeCentrality` - the `EdgeMap` that will be filled during the execution and returns a double value (centrality) for each edge
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCosts` - the `DataProvider` 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`

### closenessCentrality

```public static void closenessCentrality(Graph graph,
NodeMap closeness,
boolean directed,
DataProvider edgeCosts)```
Computes the closeness centrality for the nodes of a graph.

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 `Double.POSITIVE_INFINITY`.

For non-connected graphs, the centrality values of all nodes will be zero, since the distance to some nodes is infinite.
Precondition:
The graph must be `connected`.
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
Parameters:
`graph` - the input graph
`closeness` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCosts` - the `DataProvider` that returns a positive double value (cost) or `null` if the edges are of equal cost

### graphCentrality

```public static void graphCentrality(Graph graph,
NodeMap centrality,
boolean directed,
DataProvider edgeCosts)```
Computes the graph centrality for the nodes of a graph.

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.

For non-connected graphs, the centrality values of all nodes will be zero since the distance to some nodes is infinite.
Precondition:
A `NodeMap` must be given as input that returns for each `Node` a zero value that represents the initial closeness centrality.
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
Parameters:
`graph` - the input graph
`centrality` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`edgeCosts` - the `DataProvider` that returns a positive double value (cost) or `null` if the edges are of equal cost

### degreeCentrality

```public static void degreeCentrality(Graph graph,
NodeMap centrality,
boolean considerInEdges,
boolean considerOutEdges)```
Computes the degree centrality for the nodes of a given graph.

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

Precondition:
At least one of the flags `considerInEdges` and `considerOutEdges` must be `true`.
Complexity:
`O(graph.N())`
Parameters:
`graph` - the input graph
`centrality` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`considerInEdges` - `true` if the incoming edges should be considered, `false` otherwise
`considerOutEdges` - `true` if the outgoing edges should be considered, `false` otherwise

### weightCentrality

```public static void weightCentrality(Graph graph,
NodeMap centrality,
boolean considerInEdges,
boolean considerOutEdges,
DataProvider edgeWeights)```
Computes the weight centrality for the nodes of a graph.

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

Weight centrality degenerates to degree centrality when the edges have uniform weight. In particular, when parameter `edgeWeights` is `null`, then `degreeCentrality` is invoked instead.
Complexity:
`O(graph.E())`
Parameters:
`graph` - the input graph
`centrality` - the `NodeMap` that will be filled during the execution and returns a double value (centrality) for each node
`considerInEdges` - `true` if the incoming edges should be considered, `false` otherwise
`considerOutEdges` - `true` if the outgoing edges should be considered, `false` otherwise
`edgeWeights` - the `DataProvider` that returns a positive double value (weight) or `null` if the edges are considered to have uniform weight of `1.0`

### normalize

```public static void normalize(Graph graph,
NodeMap map)```
Normalizes the `double` values of a given `NodeMap` by dividing each of them by the maximum of all values (maximum norm).

If the maximum value is `Double.POSITIVE_INFINITY`, all values other than `Double.POSITIVE_INFINITY` are set to `0`.
Precondition:
For each node `n`: `map.getDouble(n) >= 0`
Parameters:
`graph` - the input graph
`map` - the `NodeMap` that will be filled during the execution and returns a double value from `[0,1]` interval

### normalize

```public static void normalize(Graph graph,
EdgeMap map)```
Normalizes the `double` values of a given `EdgeMap` by dividing each of them by the maximum of all values (maximum norm).

If the maximum value is `Double.POSITIVE_INFINITY`, all values other than `Double.POSITIVE_INFINITY` are set to `0`.
Precondition:
For each edge `e`: `map.getDouble(e) >= 0`
Parameters:
`graph` - the input graph
`map` - the `EdgeMap` that will be filled during the execution and returns a double value from `[0,1]` interval

### eigenvectorCentrality

```public static boolean eigenvectorCentrality(Graph graph,
NodeMap centralityMap)```
Computes an eigenvector centrality for each node of a given undirected, unweighted graph.

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

The `PageRank` algorithm is also based on eigenvector centrality but allows for more configuration options.
Parameters:
`graph` - the undirected input graph
`centralityMap` - 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
Returns:
whether or not an eigenvector could be found and `centralityMap` contains valid entries

### eigenvectorCentrality

```public static boolean eigenvectorCentrality(Graph graph,
NodeMap centralityMap,
double precision)```
Computes an eigenvector centrality for each node of a given undirected graph.

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

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.
Parameters:
`graph` - the undirected input graph
`centralityMap` - 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
`precision` - 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:
whether or not an eigenvector could be found and `centralityMap` contains valid entries

### pageRank

```public static double pageRank(Graph graph,
NodeMap pageRank)```
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.

Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the graph to calculate the ranks for
`pageRank` - the `NodeMap` that will be filled during the execution with the rank value for each node
Returns:
the sum of all node ranks

### pageRank

```public static double pageRank(Graph graph,
NodeMap pageRank,
DataProvider initialPageRank,
DataProvider nodeWeight,
DataProvider edgeWeight,
DataProvider edgeDirectedness)```
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 (see `DataProvider` `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`).

After each iteration, the relative change of each node's page rank ((newRank - oldRank)/oldRank) is calculated. If all page rank changes are below some threshold or if the maximal iterations are reached, the algorithm stops.

The `edgeDirectedness` `DataProvider` 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.

If `DataProvider` `initialPageRank` is `null`, the algorithm assumes that all nodes have an initial rank of `1.0`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the graph to calculate the ranks for
`pageRank` - the `NodeMap` that will be filled during the execution with the rank value for each node
`initialPageRank` - The `DataProvider` that specifies the initial page rank for each node
`nodeWeight` - the `DataProvider` that specifies the weight for each node
`edgeWeight` - the `DataProvider` that specifies the weight for each edge
`edgeDirectedness` - `DataProvider` that stores the directedness of the edges
Returns:
the sum of all node ranks

### pageRank

```public static double pageRank(Graph graph,
NodeMap pageRank,
DataProvider initialPageRank,
DataProvider nodeWeight,
DataProvider edgeWeight,
DataProvider edgeDirectedness,
double dampingFactor,
double precision)```
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 (see `DataProvider` `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` `DataProvider` 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.

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 `DataProvider` `initialPageRank` is `null`, the algorithm assumes that all nodes have an initial rank of `1.0`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the graph to calculate the ranks for
`pageRank` - the `NodeMap` that will be filled during the execution with the rank value for each node
`initialPageRank` - The `DataProvider` that specifies the initial page rank for each node
`nodeWeight` - the `DataProvider` that specifies the weight for each node
`edgeWeight` - the `DataProvider` that specifies the weight for each edge
`edgeDirectedness` - `DataProvider` that stores the directedness of the edges
`dampingFactor` - 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` - the non-negative precision of the calculated page ranks (a good default value is `0.001`)
Returns:
the sum of all node ranks