y.algo
Class Centrality

java.lang.Object
  y.algo.Centrality

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