y.algo
Class Centrality

java.lang.Object
  y.algo.Centrality

public 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 value of type double 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 to lie within the interval [0..1].

Constructor Summary

Centrality()

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 graph.
static void	edgeBetweenness(Graph graph, EdgeMap centrality, boolean directed, DataProvider edgeCosts) Computes betweenness centrality for each edge of a given 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) Like normalize(Graph, NodeMap), but for EdgeMap.
static void	normalize(Graph graph, NodeMap map) This method normalizes the double values of a node map by dividing all values by the maximum of all values (maximum norm).
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

Constructor Detail

Centrality

public Centrality()

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 node will cause many shortest paths to change.

Parameters:

graph - the input graph.

centrality - return value. A NodeMap which will holds a non-negative centrality value of type double for each node.

directed - whether to consider the edges of the graph as directed or undirected. If false, the algorithm traverse every edge in both direction regardless of the direction of the edge.

edgeCosts - if null the edges of the graph are considered to have equal cost. Otherwise it must provide a strictly positive double value (its cost) for every edge. Invalid values are assumed to be 1.0.

Complexity:

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

Precondition:

NodeMap centrality with values initially zero

edgeBetweenness

public static void edgeBetweenness(Graph graph,
                                   EdgeMap centrality,
                                   boolean directed,
                                   DataProvider edgeCosts)

Computes betweenness centrality for each edge of a given graph. Like nodeBetweenness(Graph, NodeMap, boolean, DataProvider) but applied to edges.

Parameters:

centrality - return value. A EdgeMap which will hold a non-negative centrality value of type double for each edge.

Precondition:

EdgeMap centrality with values initially zero

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. Like nodeBetweenness(Graph, NodeMap, boolean, DataProvider) but applied to both nodes and edges.

Parameters:

nodeCentrality - return value. A NodeMap which will hold the centrality value of type double for every node.

edgeCentrality - return value. A EdgeMap which will hold the centrality value of type double for every edge.

Preconditions:

NodeMap nodeCentrality with values initially zero

EdgeMap edgeCentrality with values initially zero

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. Also note, that for unconnected graphs the centrality values of all nodes will be zero, since the distance to some nodes is infinite.

Parameters:

graph - the input graph.

closeness - return value. A map which hold the centrality value of type double for every node.

directed - whether to consider the edges of the graph as directed or undirected.

edgeCosts - when null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.

Complexity:

O(graph.N()^2 + graph.N()*graph.E()) for unweighted graphs, O( (graph.N()*graph.E()) + graph.N()^2 *log(graph.N()))
or: O(graph.N()) * O(Uniform) for unweighted, O(allPairs) for weighted graphs

Precondition:

GraphChecker.isConnected(graph)

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. Also note, that for unconnected graphs the centrality values of all nodes will be zero, since the distance to some nodes is infinite.

Parameters:

graph - the input graph.

centrality - return value. A map which hold the centrality value of type double for every node.

directed - whether to consider the edges of the graph as directed or undirected.

edgeCosts - when null the edges of the graph are considered to have equal cost. Otherwise it must provide a non-negative double value (its cost) for every edge.

Complexity:

O(graph.N()^2 + graph.N()*graph.E()) for unweighted graphs, O( (graph.N()*graph.E()) + graph.N()^2 *log(graph.N())) or: O(graph.N()) * O(Uniform) for unweighted, O(allPairs) for weighted graphs

degreeCentrality

public static void degreeCentrality(Graph graph,
                                    NodeMap centrality,
                                    boolean considerInEdges,
                                    boolean considerOutEdges)

Computes the degree centrality for the nodes of a graph. Degree centrality measures in-, out- or overall degree of a node.

Parameters:

graph - the input graph.

centrality - return value. A map which provides the degree centrality as double value for every node.

considerInEdges -

considerOutEdges -

Complexity:

O(graph.N())

Precondition:

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

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.

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

Parameters:

graph - The input graph.

centrality - Return value. A map which provides the value centrality as double value for every node.

considerInEdges - Whether the weights associated with incoming edges should be considered.

considerOutEdges - Whether the weights associated with outgoing edges should be considered.

edgeWeights - When null the edges of the graph are considered to have uniform weight of 1.0. Otherwise it must provide a non-negative double value (the weight) for every edge.

Complexity:

O(graph.E())

normalize

public static void normalize(Graph graph,
                             NodeMap map)

This method normalizes the double values of a node map by dividing all values by the maximum of all values (maximum norm). Note, if the maximum value is Double.POSITIVE_INFINITY, all values other than Double.POSITIVE_INFINITY are set to 0.

Parameters:

graph - the input graph

map - return value that holds double values between zero and one.

Precondition:

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

normalize

public static void normalize(Graph graph,
                             EdgeMap map)

Like normalize(Graph, NodeMap), but for EdgeMap.

Parameters:

graph - the input graph

map - return value that holds double values between zero and one.

Precondition:

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