com.net2plan.libraries

Class GraphTheoryMetrics

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.

Since:

0.2.0

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo-Zaragoza

Constructor Summary

Constructors

Constructor and Description
GraphTheoryMetrics(Set<Long> nodeIds, Map<Long,Pair<Long,Long>> linkMap, Map<Long,Double> linkCostMap) Default constructor.

Method Summary

Methods

Modifier and Type	Method and Description
void	configureLinkCostMap(Map<Long,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.
Map<Long,Double>	getLinkBetweenessCentrality() Returns the betweeness centrality of each link.
int	getLinkConnectivity() Returns the link connectivity.
Collection<Long>	getNeighbors(long nodeId) Returns the set of nodes reachable from a given node.
Map<Long,Double>	getNodeBetweenessCentrality() Returns the betweeness centrality of each node.
int	getNodeConnectivity() Returns the node connectivity.
Map<Long,Integer>	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 Object

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

Constructor Detail

GraphTheoryMetrics

public GraphTheoryMetrics(Set<Long> nodeIds,
                  Map<Long,Pair<Long,Long>> linkMap,
                  Map<Long,Double> linkCostMap)

Default constructor.

Parameters:

nodeIds - Set of node identifiers. It is mandatory that can be iterated in ascending order of node identifier (i.e. using TreeSet or those Set objects returned from Net2Plan object

linkMap - Map of links, where the key is the unique link identifier and the value is a Pair representing the origin node and the destination node of the link, respectively. It is mandatory that can be iterated in ascending order of link identifier (i.e. using TreeMap or those Map objects returned from Net2Plan object

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

Since:

0.3.0

Method Detail

configureLinkCostMap

public void configureLinkCostMap(Map<Long,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

Since:

0.3.0

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

Since:

0.2.0

getAssortativity

public double getAssortativity()

Returns the assortativity of the network.

Returns:

Assortativity

Since:

0.2.0

getAverageNeighborConnectivity

public double getAverageNeighborConnectivity()

Returns the average neighbor connectivity.

Returns:

Average neighbor connectivity

Since:

0.2.0

getAverageOutNodeDegree

public double getAverageOutNodeDegree()

Returns the average number of outgoing links per node.

Returns:

Average number of outgoing links per node

Since:

0.2.0

getAverageShortestPathDistance

public double getAverageShortestPathDistance()

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

Returns:

Average shortest path distance

Since:

0.2.0

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

Since:

0.2.0

getClusteringCoefficient

public double getClusteringCoefficient()

Returns the clustering coefficient of the network.

Returns:

Clustering coefficient

Since:

0.2.0

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

Since:

0.2.0

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

Since:

0.2.0

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

Since:

0.2.0

getLinkBetweenessCentrality

public Map<Long,Double> 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

Since:

0.3.0

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

Since:

0.2.0

getNeighbors

public Collection<Long> getNeighbors(long nodeId)

Returns the set of nodes reachable from a given node.

Parameters:

nodeId - Node identifier

Returns:

Set of reachable nodes

Since:

0.3.0

getNodeBetweenessCentrality

public Map<Long,Double> 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

Since:

0.3.0

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

Since:

0.2.0

getOutNodeDegree

public Map<Long,Integer> getOutNodeDegree()

Returns the number of outgoing links for each node.

Returns:

Number of outgoing links per node

Since:

0.2.0

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

Since:

0.2.0

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

Since:

0.2.0