
CMUISR08103
Institute for Software Research
School of Computer Science, Carnegie Mellon University
CMUISR08103
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
CMUISR08103.pdf
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 coefficient. 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
