Institute for Software Research
School of Computer Science, Carnegie Mellon University


Random Graph Standard Network
Metrics Distributions in ORA

Kathleen M. Carley, Eunice J. Kim

March 2008

Center for the Computational Analysis of
Social and Organizational Systems (CASOS) Technical Report


Keywords: Random network, distribution, centrality, path length, clustering coefficient

Networks, and the nodes within them, are often characterized using a series of metrics. Illustrative graph level metrics are the characteristic path length and the clustering co-efficient. Illustrative node level metrics are degree centrality, betweenness centrality, closeness centrality, and eigenvector centrality. A key issue in using these metrics is how to interpret the values; e.g., is a degree centrality of .2 high? With normalized values, we now that these metrics go between 0 and 1, and while 0 is low and 1 is high, we don't have much other interpretive information. Here we ask, are these values different than what we would expect in a random graph. We report the distributions of these metrics against the behavior of random graphs and we present the 95% most probable range for each of these metrics. We find that a normal distribution well approximating most metrics, for large slightly dense networks, and that the ranges are centered at the expected mean and the endpoints are two (sample) standard deviations apart from the center.

20 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by