com.yworks.yfiles.algorithms

Class Centrality

java.lang.Object

com.yworks.yfiles.algorithms.Centrality

public final class Centrality
extends 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.

Method Summary

Modifier and Type	Method and Description
static void	closenessCentrality(Graph graph, INodeMap closeness, boolean directed, IDataProvider edgeCosts) Computes the closeness centrality for the nodes of a graph.
static void	degreeCentrality(Graph graph, INodeMap centrality, boolean considerInEdges, boolean considerOutEdges) Computes the degree centrality for the nodes of a given graph.
static void	edgeBetweenness(Graph graph, IEdgeMap centrality, boolean directed, IDataProvider edgeCosts) Computes betweenness centrality for each edge of a given graph.
static void	graphCentrality(Graph graph, INodeMap centrality, boolean directed, IDataProvider edgeCosts) Computes the graph centrality for the nodes of a graph.
static void	nodeBetweenness(Graph graph, INodeMap centrality, boolean directed, IDataProvider edgeCosts) Computes betweenness centrality for each node of a given graph.
static void	nodeEdgeBetweenness(Graph graph, INodeMap nodeCentrality, IEdgeMap edgeCentrality, boolean directed, IDataProvider edgeCosts) Computes betweenness centrality for each node and edge of a given graph.
static void	normalize(Graph graph, IEdgeMap map) Normalizes the double values of a given IEdgeMap by dividing each of them by the maximum of all values (maximum norm).
static void	normalize(Graph graph, INodeMap map) Normalizes the double values of a given INodeMap by dividing each of them by the maximum of all values (maximum norm).
static void	weightCentrality(Graph graph, INodeMap centrality, boolean considerInEdges, boolean considerOutEdges, IDataProvider 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

closenessCentrality

public static final void closenessCentrality(Graph graph,
                                             INodeMap closeness,
                                             boolean directed,
                                             IDataProvider 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 INodeMap 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 IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost

degreeCentrality

public static final void degreeCentrality(Graph graph,
                                          INodeMap 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 INodeMap 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

edgeBetweenness

public static final void edgeBetweenness(Graph graph,
                                         IEdgeMap centrality,
                                         boolean directed,
                                         IDataProvider 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 IEdgeMap 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 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

graphCentrality

public static final void graphCentrality(Graph graph,
                                         INodeMap centrality,
                                         boolean directed,
                                         IDataProvider 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 INodeMap 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 INodeMap 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 IDataProvider that returns a positive double value (cost) or null if the edges are of equal cost

nodeBetweenness

public static final void nodeBetweenness(Graph graph,
                                         INodeMap centrality,
                                         boolean directed,
                                         IDataProvider 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 INodeMap 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 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

nodeEdgeBetweenness

public static final void nodeEdgeBetweenness(Graph graph,
                                             INodeMap nodeCentrality,
                                             IEdgeMap edgeCentrality,
                                             boolean directed,
                                             IDataProvider 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 INodeMap that will be filled during the execution and returns a double value (centrality) for each node

edgeCentrality - the IEdgeMap 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 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

normalize

public static final void normalize(Graph graph,
                                   IEdgeMap map)

Normalizes the double values of a given IEdgeMap 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 IEdgeMap that will be filled during the execution and returns a double value from [0,1] interval

normalize

public static final void normalize(Graph graph,
                                   INodeMap map)

Normalizes the double values of a given INodeMap 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 INodeMap that will be filled during the execution and returns a double value from [0,1] interval

weightCentrality

public static final void weightCentrality(Graph graph,
                                          INodeMap centrality,
                                          boolean considerInEdges,
                                          boolean considerOutEdges,
                                          IDataProvider 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 INodeMap 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 IDataProvider that returns a positive double value (weight) or null if the edges are considered to have uniform weight of 1.0