Information Technology Reference
In-Depth Information
3
Social Network Analysis Measures
Using social network analysis (SNA) measures to evaluate graphs that are output
from simulations is common. However, a single measure (or a small set of measures)
is unlikely to establish the validity of a simulated network. When a particular measure
captures some aspect that is crucial to the kind of process being investigated, the im-
plicit assumption is that the closer the value of the measure on the synthetic graph is
to that of the reference graph, the more similar the two graphs will be in that respect.
How well this works depends upon what we mean by the 'closeness' of a measure
when comparing networks. For instance, [21] reports on that centrality measures de-
grade gracefully with the introduction of random changes in the network, however,
this result might depend on the topology of the network [27]. Below, we briefly pre-
view some of the most popular approaches [32, 37] used by agent-based modelers.
For a more detailed review on networks in agent-based simulations, we refer to [5, 6],
and for formal definitions and extensive discussions of network measures [31, 37].
Node Degree Distribution:
is the number of edges each node has in a graph. For a
directed graph, this includes incoming, outgoing and total edges; while for undirected
graphs, it means just the total edges of each node has. In order to determine the node
degree distribution of a network, one can measure its deviance from another distribu-
tion using such measures, such as the Least Square Error (LSE) or the Kolmogorov-
Smirnov statistic. When a theoretical distribution is assumed, against which the distri-
bution of a simulated network is compared, maximum likelihood estimation (MLE)
techniques are useful. The degree distribution gives a good idea of the prevalence of
different kinds of node but can be inadequate for validation purposes (e.g., [35]).
Assortativity Mixing:
assortative mixing means that nodes with similar degrees tend
to be connected with each other, calculated by working out the correlation of the de-
grees of all connected node pairs in the graph. It ranges from -1 to 1: a positive value
indicating that nodes tend to connect with others with similar degrees and a negative
value otherwise [7]. Usually, the averaged value of all node pairs is calculated for the
whole graph for comparison - known as the global clustering coefficient. A value
approaching 1 would result from a graph where there are uniformly densely intercon-
nected nodes and other areas that are uniformly but sparsely connected. A negative
value might result from a graph where nodes with a high degree are distributed away
from each other. This measure is useful when the local uniformity of degree distribu-
tion (or otherwise) is being investigated.
Cluster Coefficient:
is the ratio of the number of edges that exist between a node's
immediate neighbors and the maximum number of edges that could exist between
them. If all of one's friends know one another this would result in a cluster coefficient
of 1; in the other extreme, where none knew each other, would result in a value of 0.
This measure is important, for instance, if one had hypothesized that, the process of
making new friends is driven by the “friend of a friend”. The local cluster coefficients
