com.net2plan.libraries

Class GraphTheoryMetrics

java.lang.Object

com.net2plan.libraries.GraphTheoryMetrics

public class GraphTheoryMetrics
extends Object

Class to deal with graph-theory metrics computation.

Important: Internal computations (like shortest-paths) are cached in order to improve efficiency.

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo-Zaragoza

Constructor Summary

Constructors

Constructor and Description
GraphTheoryMetrics(List<Node> nodes, List<Link> links, SortedMap<Link,Double> linkCostMap) Default constructor

Method Summary

Modifier and Type	Method and Description
void	configureLinkCostMap(Map<Link,Double> linkCostMap) Re-configures link cost setting.
double	getAlgebraicConnectivity() Returns the algebraic connectivity of the network.
double	getAssortativity() Returns the assortativity of the network.
double	getAverageNeighborConnectivity() Returns the average neighbor connectivity.
double	getAverageOutNodeDegree() Returns the average number of outgoing links per node.
double	getAverageShortestPathDistance() Returns the average shortest path distance among all node-pair shortest paths.
double	getAverageTwoTermReliability() Returns the average two-term reliability (A2TR) of the network.
double	getClusteringCoefficient() Returns the clustering coefficient of the network.
double	getDensity() Returns the density of the network.
double	getDiameter() Returns the diameter of the network.
double	getHeterogeneity() Returns the heterogeneity of the network.
DoubleMatrix1D	getLinkBetweenessCentrality() Returns the betweeness centrality of each link.
int	getLinkConnectivity() Returns the link connectivity.
Collection<Node>	getNeighbors(Node node) Returns the set of nodes reachable from a given node.
DoubleMatrix1D	getNodeBetweenessCentrality() Returns the betweeness centrality of each node.
int	getNodeConnectivity() Returns the node connectivity.
DoubleMatrix1D	getOutNodeDegree() Returns the number of outgoing links for each node.
double	getSpectralRadius() Returns the spectral radius of the network.
double	getSymmetryRatio() Returns the symmetry ratio.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphTheoryMetrics

public GraphTheoryMetrics(List<Node> nodes,
                          List<Link> links,
                          SortedMap<Link,Double> linkCostMap)

Default constructor

Parameters:

nodes - List of odes

links - List of links

linkCostMap - Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required

Method Detail

configureLinkCostMap

public void configureLinkCostMap(Map<Link,Double> linkCostMap)

Re-configures link cost setting. Related information, such as shortest paths, is cleared.

Parameters:

linkCostMap - Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required

getAlgebraicConnectivity

public double getAlgebraicConnectivity()

Returns the algebraic connectivity of the network. The algebraic connectivity is equal to the second smallest eigenvalue of the laplacian matrix.

For symmetric (or undirected) networks, if the algebraic connectivity is different from zero, it is ensured that the network is connected, that is, it is possible to find a path between each node pair.

Returns:

Algebraic connectivity

getAssortativity

public double getAssortativity()

Returns the assortativity of the network.

Returns:

Assortativity

getAverageNeighborConnectivity

public double getAverageNeighborConnectivity()

Returns the average neighbor connectivity.

Returns:

Average neighbor connectivity

getAverageOutNodeDegree

public double getAverageOutNodeDegree()

Returns the average number of outgoing links per node.

Returns:

Average number of outgoing links per node

getAverageShortestPathDistance

public double getAverageShortestPathDistance()

Returns the average shortest path distance among all node-pair shortest paths.

Returns:

Average shortest path distance

getAverageTwoTermReliability

public double getAverageTwoTermReliability()

Returns the average two-term reliability (A2TR) of the network. A2TR is computed as the ratio between the number of node-pair for which a path can be found and the same number when the network is connected (Nx(N-1), where N is the number of nodes in the network). The value is in range [0, 1].

Returns:

Average two-term reliability

getClusteringCoefficient

public double getClusteringCoefficient()

Returns the clustering coefficient of the network.

Returns:

Clustering coefficient

getDensity

public double getDensity()

Returns the density of the network. The density represents the ratio between the number of links in the network and the number of links needed to build a full-mesh network (Nx(N-1), where N is the number of nodes in the network).

Returns:

Density

getDiameter

public double getDiameter()

Returns the diameter of the network. The diameter is the longest path distance among all node-pair shortest paths.

Returns:

Network diameter

getHeterogeneity

public double getHeterogeneity()

Returns the heterogeneity of the network. The heterogeneity is equal to the standard deviation of all node-pair shortest paths divided by the average shortest path distance.

Returns:

Heterogeneity

getLinkBetweenessCentrality

public DoubleMatrix1D getLinkBetweenessCentrality()

Returns the betweeness centrality of each link. The betweeness centrality of a link is equal to the number of node-pair shortest paths which traverses the link.

Internally it makes use of the Brandes' algorithm.

Returns:

Betweeness centrality of each link

getLinkConnectivity

public int getLinkConnectivity()

Returns the link connectivity. The link connectivity is equal to the smallest number of link-disjoint paths between each node pair.

Internally it makes use of the Edmonds-Karp algorithm to compute the maximum flow between each node pair, assuming a link capacity equal to one for every link.

Returns:

Link connectivity

getNeighbors

public Collection<Node> getNeighbors(Node node)

Returns the set of nodes reachable from a given node.

Parameters:

node - Node

Returns:

Collection of reachable nodes

getNodeBetweenessCentrality

public DoubleMatrix1D getNodeBetweenessCentrality()

Returns the betweeness centrality of each node. The betweeness centrality of a node is equal to the number of node-pair shortest paths which traverses the node.

Internally it makes use of the Brandes' algorithm.

Returns:

Betweeness centrality of each node

getNodeConnectivity

public int getNodeConnectivity()

Returns the node connectivity. The node connectivity is equal to the smallest number of node-disjoint paths between each node pair.

Internally it makes use of the (modified) Edmonds-Karp algorithm to compute the maximum flow between each node pair, assuming a link capacity equal to one for every link.

Returns:

Node connectivity

getOutNodeDegree

public DoubleMatrix1D getOutNodeDegree()

Returns the number of outgoing links for each node.

Returns:

Number of outgoing links per node

getSpectralRadius

public double getSpectralRadius()

Returns the spectral radius of the network. The spectral radius is equal to the largest eigenvalue of the adjacency matrix.

Returns:

Spectral radius

getSymmetryRatio

public double getSymmetryRatio()

Returns the symmetry ratio. The symmetry ratio is equal to the number of distinct eigenvalues of the adjacency matrix divided by the network density plus one.

Returns:

Symmetry ratio