netkit.util
Class GraphMetrics

java.lang.Object
  netkit.util.GraphMetrics

public class GraphMetrics
extends java.lang.Object

Nested Class Summary

class

GraphMetrics.AdjacencyMatrix This is a wrapper class for the COLT DoubleMatrix2D object such that NetKit does not require the colt library in its classpath.

Field Summary

Graph	graph
protected static java.util.logging.Logger	logger
java.lang.String	nodeType
int	numEdges
int	numNodes

Constructor Summary

GraphMetrics(Graph g)
Compute metrics over all nodes in the graph

GraphMetrics(Graph g, java.lang.String nodeType)
Compute certain metrics only over nodes of the given node type

Method Summary

boolean	calcCentralityActive()
double	calcCentralityProgress()
boolean	calcClusterActive()
double	calcClusterProgress()
boolean	calcComponentActive()
double	calcComponentProgress()
void	calculateCentralityStat() This calculates the all-pairs closest distances
void	calculateClusterStat()
void	calculateComponentStat()
void	calculateDegreeStat()
static double[]	calculateEdgeBasedAssortativityCoeff(Classification known)
static double[]	calculateEdgeBasedAssortativityCoeff(Classification known, EdgeType et)
double[]	calculateEdgeBasedAssortativityCoeff(java.lang.String nodeType, AttributeCategorical attribute)
double[]	calculateEdgeBasedAssortativityCoeff(java.lang.String nodeType, AttributeCategorical attribute, EdgeType et)
void	calculateEdgeStat()
static double[]	calculateNodeBasedAssortativityCoeff(Classification known)
static double[]	calculateNodeBasedAssortativityCoeff(Classification known, EdgeType et)
double[]	calculateNodeBasedAssortativityCoeff(java.lang.String nodeType, AttributeCategorical attribute)
double[]	calculateNodeBasedAssortativityCoeff(java.lang.String nodeType, AttributeCategorical attribute, EdgeType et)
static double	computeAssortativityFromMatrix(double[][] matrix) Utility method which can be used by any sub-class
GraphMetrics.AdjacencyMatrix	getAdjacencyMatrix(boolean unweighted) Get the (possibly unweighted) adjacency matrix of this graph in the COLT sparseMatrix2D format.
double	getAlphaCentralityAlpha()
double	getAlphaCentralityDelta()
ApproximateCentralities	getApproximateCentralities()
double	getBetweennessCentrality(Node n) Get the betweenness centrality for the given node.
double	getCharacteristicPathLength()
double	getClosenessCentrality(Node n) Get the closeness centrality for the given node.
ModularityClusterer.Cluster	getCluster(int idx)
int	getCluster(Node node)
ModularityClusterer	getClusterer()
int	getComponent(Node node)
int	getComponentSize(int componentNum)
HistogramDiscrete	getDegreeDistribution() Return the histogram of (unweighted) edge degrees for nodes in the graph.
double	getDist(Node src, Node dst)
double	getEfficiency() Not implemented yet.
double	getGlobalClusterCoeff()
double	getGraphCentrality() Get the graph centrality.
double	getGraphCentrality(Node n) Get the graph centrality for a specific node.
double	getGraphDensity() Return the density of the graph as defined by: |E|/(|N|*(|N)-1)), where |E| is the number of edges and |N| is the number of nodes in the graph.
double	getInformationCentrality(Node n) Not implemented yet.
double	getLocalClusterCoeff()
int	getMaxComponentIdx()
int	getMaxComponentSize()
double	getMaxDegree()
double	getMaxDist()
double	getMaxEdgeWeight()
double	getMaxWeightedDegree()
double	getMeanDegree()
double	getMeanDist()
double	getMeanEdgeWeight()
double	getMeanWeightedDegree()
double	getMinDegree()
double	getMinEdgeWeight()
double	getMinWeightedDegree()
int	getNodeIndex(Node n)
int	getNumClusters()
int	getNumComponents()
double	getNumEdges()
double	getNumNodes()
int	getNumPath2()
int	getNumSingletons()
int	getNumtriangles()
double	getPagerankAlpha()
double	getPagerankDelta()
double	getTotalEdgeWeights()
double	getWeightedBetweennessCentrality(Node n) Get the betweenness centrality for the given node.
double	getWeightedCharacteristicPathLength()
double	getWeightedClosenessCentrality(Node n) Get the closeness centrality for the given node.
double	getWeightedDist(Node src, Node dst)
double	getWeightedGraphCentrality() Get the graph centrality.
double	getWeightedGraphCentrality(Node n) Get the graph centrality for a specific node.
double	getWeightedInformationCentrality(Node n) Not implemented yet.
double	getWeightedMaxDist()
double	getWeightedMeanDist()
void	setAlphaCentralityAlpha(double alpha) set the alpha used when computing approximate alpha centrality
void	setAlphaCentralityDelta(double delta) set the delta used when computing approximate alpha centrality
void	setPagerankAlpha(double alpha) set the alpha used when computing approximate pagerank centrality
void	setPagerankDelta(double delta) set the delta used when computing approximate pagerank centrality
void	stopCalcCentralityStat()
void	stopCalcClusterStat()
void	stopCalcComponentStat()

Methods inherited from class java.lang.Object

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

Field Detail

logger

protected static java.util.logging.Logger logger

graph

public final Graph graph

nodeType

public final java.lang.String nodeType

numNodes

public final int numNodes

numEdges

public final int numEdges

Constructor Detail

GraphMetrics

public GraphMetrics(Graph g)

Compute metrics over all nodes in the graph

Parameters:

g -

GraphMetrics

public GraphMetrics(Graph g,
                    java.lang.String nodeType)

Compute certain metrics only over nodes of the given node type

Parameters:

g -

nodeType -

Method Detail

getClusterer

public ModularityClusterer getClusterer()

getCluster

public int getCluster(Node node)

Parameters:

node - The node whose cluster index is sought after

Returns:

the cluster index of the given node as clustered by ModularityClusterer

getNumClusters

public int getNumClusters()

Returns:

the number of clusters found by ModularityClusterer

getCluster

public ModularityClusterer.Cluster getCluster(int idx)

Returns:

the specified cluster as found by ModularityClusterer

calcClusterProgress

public double calcClusterProgress()

calcClusterActive

public boolean calcClusterActive()

stopCalcClusterStat

public void stopCalcClusterStat()

calculateClusterStat

public void calculateClusterStat()

getLocalClusterCoeff

public double getLocalClusterCoeff()

Returns:

The local clustering coefficient (computed as average over all triangles)

getGlobalClusterCoeff

public double getGlobalClusterCoeff()

Returns:

The global clustering coefficient

getNumtriangles

public int getNumtriangles()

Returns:

The number of triangles in the graph

getNumPath2

public int getNumPath2()

Returns:

The number of paths of length two that are not triangles

calculateEdgeStat

public void calculateEdgeStat()

getMinEdgeWeight

public double getMinEdgeWeight()

Returns:

The min edge weight

getMaxEdgeWeight

public double getMaxEdgeWeight()

Returns:

The max edge weight

getMeanEdgeWeight

public double getMeanEdgeWeight()

Returns:

The average edge weight

getTotalEdgeWeights

public double getTotalEdgeWeights()

Returns:

The sum of all edges using their edge weight

getNumEdges

public double getNumEdges()

Returns:

The number of edges in the graph

getNumNodes

public double getNumNodes()

Returns:

The number of nodes in the graph

calculateDegreeStat

public void calculateDegreeStat()

getAdjacencyMatrix

public GraphMetrics.AdjacencyMatrix getAdjacencyMatrix(boolean unweighted)

Get the (possibly unweighted) adjacency matrix of this graph in the COLT sparseMatrix2D format.

Returns:

the (possibly unweighted) adjacency matrix of this graph in the COLT sparseMatrix2D format.

getDegreeDistribution

public HistogramDiscrete getDegreeDistribution()

Return the histogram of (unweighted) edge degrees for nodes in the graph.

Returns:

the histogram of (unweighted) edge degrees for nodes in the graph.

getMinDegree

public double getMinDegree()

Returns:

The min node degree when calculated ignoring edge weights

getMaxDegree

public double getMaxDegree()

Returns:

The max node degree when calculated ignoring edge weights

getMeanDegree

public double getMeanDegree()

Returns:

The average node degree when calculated ignoring edge weights

getMinWeightedDegree

public double getMinWeightedDegree()

Returns:

The minimum node degree when calculated using the weights of the edges

getMaxWeightedDegree

public double getMaxWeightedDegree()

Returns:

The max node degree when calculated using the weights of the edges

getMeanWeightedDegree

public double getMeanWeightedDegree()

Returns:

The average node degree when calculated using the weights of the edges

calcComponentProgress

public double calcComponentProgress()

calcComponentActive

public boolean calcComponentActive()

stopCalcComponentStat

public void stopCalcComponentStat()

calculateComponentStat

public void calculateComponentStat()

getComponent

public int getComponent(Node node)

Parameters:

node - The node whose component index is sought after

Returns:

The component index of the specified node

getNumComponents

public int getNumComponents()

Returns:

the number of connected components in the graph (includes singletons)

getNumSingletons

public int getNumSingletons()

Returns:

the number of singleton nodes in the graph

getMaxComponentSize

public int getMaxComponentSize()

Returns:

the size (number of nodes) of the largest connected component

getComponentSize

public int getComponentSize(int componentNum)

Parameters:

componentNum - The component whose size to get

Returns:

the number of nodes belonging to the specified connected component

getMaxComponentIdx

public int getMaxComponentIdx()

Returns:

index into largest connected component in the graph

getNodeIndex

public int getNodeIndex(Node n)

calcCentralityProgress

public double calcCentralityProgress()

calcCentralityActive

public boolean calcCentralityActive()

stopCalcCentralityStat

public void stopCalcCentralityStat()

calculateCentralityStat

public void calculateCentralityStat()

This calculates the all-pairs closest distances

getDist

public double getDist(Node src,
                      Node dst)

getWeightedDist

public double getWeightedDist(Node src,
                              Node dst)

getMeanDist

public double getMeanDist()

Returns:

average weighted path-length between nodes

getWeightedMeanDist

public double getWeightedMeanDist()

Returns:

average weighted path-length between nodes

getMaxDist

public double getMaxDist()

Returns:

weighted diameter of graph

getWeightedMaxDist

public double getWeightedMaxDist()

Returns:

weighted diameter of graph

computeAssortativityFromMatrix

public static double computeAssortativityFromMatrix(double[][] matrix)

Utility method which can be used by any sub-class

Parameters:

matrix - The assortativity matrix

Returns:

assortativity

calculateEdgeBasedAssortativityCoeff

public static double[] calculateEdgeBasedAssortativityCoeff(Classification known)

calculateNodeBasedAssortativityCoeff

public static double[] calculateNodeBasedAssortativityCoeff(Classification known)

calculateNodeBasedAssortativityCoeff

public static double[] calculateNodeBasedAssortativityCoeff(Classification known,
                                                            EdgeType et)

calculateEdgeBasedAssortativityCoeff

public static double[] calculateEdgeBasedAssortativityCoeff(Classification known,
                                                            EdgeType et)

calculateEdgeBasedAssortativityCoeff

public double[] calculateEdgeBasedAssortativityCoeff(java.lang.String nodeType,
                                                     AttributeCategorical attribute)

calculateNodeBasedAssortativityCoeff

public double[] calculateNodeBasedAssortativityCoeff(java.lang.String nodeType,
                                                     AttributeCategorical attribute)

calculateEdgeBasedAssortativityCoeff

public double[] calculateEdgeBasedAssortativityCoeff(java.lang.String nodeType,
                                                     AttributeCategorical attribute,
                                                     EdgeType et)

calculateNodeBasedAssortativityCoeff

public double[] calculateNodeBasedAssortativityCoeff(java.lang.String nodeType,
                                                     AttributeCategorical attribute,
                                                     EdgeType et)

getEfficiency

public double getEfficiency()

Not implemented yet.

Returns:

getGraphDensity

public double getGraphDensity()

Return the density of the graph as defined by: |E|/(|N|*(|N)-1)), where |E| is the number of edges and |N| is the number of nodes in the graph.

Returns:

the density of the graph

getClosenessCentrality

public double getClosenessCentrality(Node n)

Get the closeness centrality for the given node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the closeness centrality for the given node.

getWeightedClosenessCentrality

public double getWeightedClosenessCentrality(Node n)

Get the closeness centrality for the given node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the closeness centrality for the given node.

getInformationCentrality

public double getInformationCentrality(Node n)

Not implemented yet.

Returns:

getWeightedInformationCentrality

public double getWeightedInformationCentrality(Node n)

Not implemented yet.

Returns:

getBetweennessCentrality

public double getBetweennessCentrality(Node n)

Get the betweenness centrality for the given node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the betweenness centrality for the given node.

getWeightedBetweennessCentrality

public double getWeightedBetweennessCentrality(Node n)

Get the betweenness centrality for the given node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the betweenness centrality for the given node.

getGraphCentrality

public double getGraphCentrality()

Get the graph centrality. For details on this, see Linton C. Freeman, "A Set of Measures of Centrality Based on Betweenness," Sociometry, Vol 40, No 1, pg. 35-41, 1977.

Returns:

the graph centrality.

getWeightedGraphCentrality

public double getWeightedGraphCentrality()

Get the graph centrality. For details on this, see Linton C. Freeman, "A Set of Measures of Centrality Based on Betweenness," Sociometry, Vol 40, No 1, pg. 35-41, 1977.

Returns:

the graph centrality.

getGraphCentrality

public double getGraphCentrality(Node n)

Get the graph centrality for a specific node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the graph centrality for a specific node.

getWeightedGraphCentrality

public double getWeightedGraphCentrality(Node n)

Get the graph centrality for a specific node. For details on this, see Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality," (2001).

Returns:

the graph centrality for a specific node.

getCharacteristicPathLength

public double getCharacteristicPathLength()

Returns:

median of all average shortest-path-lengths of all nodes

getWeightedCharacteristicPathLength

public double getWeightedCharacteristicPathLength()

Returns:

median of all average shortest-path-lengths of all nodes

getAlphaCentralityAlpha

public double getAlphaCentralityAlpha()

Returns:

the alpha used when computing approximate alpha centrality

setAlphaCentralityAlpha

public void setAlphaCentralityAlpha(double alpha)

set the alpha used when computing approximate alpha centrality

getAlphaCentralityDelta

public double getAlphaCentralityDelta()

Returns:

the delta used when computing approximate alpha centrality

setAlphaCentralityDelta

public void setAlphaCentralityDelta(double delta)

set the delta used when computing approximate alpha centrality

getPagerankAlpha

public double getPagerankAlpha()

Returns:

the alpha used when computing approximate pagerank centrality

setPagerankAlpha

public void setPagerankAlpha(double alpha)

set the alpha used when computing approximate pagerank centrality

getPagerankDelta

public double getPagerankDelta()

Returns:

the delta used when computing approximate pagerank centrality

setPagerankDelta

public void setPagerankDelta(double delta)

set the delta used when computing approximate pagerank centrality

getApproximateCentralities

public ApproximateCentralities getApproximateCentralities()