Information Technology Reference
In-Depth Information
However, it requires that the networks must be of the same size. As discussed in Sec-
tion 4, when the node set does not change, one may use distance measures to compare
features (a set of network characteristics) across different time steps. For example,
Legendi and Gulyas [24] have proposed to study cumulative measures of network
characteristics by applying time-dependent processes of changes in agents' ties in a
network.
To compare networks of varying size that are generated from agent-based models,
Alam et al. [4] proposed the use of the Kolmogorov-Smirnov (KS) statistic as a gen-
eral schema to compare pairwise simulated networks at different time steps by com-
paring distributions of node-statistics from the graphs (e.g., degree distribution). As a
nonparametric test, the KS test does not assume that an underlying normal distribution
and may be applied on entire distributions of network analysis measures. McCulloh
and Carley [26] adopted a technique from statistical control theory called cumulative
sum control chart (
CUSUM
) to detect changes in longitudinal networks. As they
show, this statistical technique can be applied to a variety of network measures to
compare simulated and real networks. Alt et al. [7] used
CUSUM
to detect changes in
agent-based simulated networks by tracking changes in the
betweenness
and
closeness
centrality measures. McCulloh et al. [27] also used spectral analysis in conjunction
with the
CUSUM
statistic to detect periodicity as well as significant changes in
longitudinal networks.
Concerning the handling of dynamic networks, a way forward is to combine non-
parametric tests as above [4] with the kinds of subgraph analysis and change detection
methods discussed in the previous section. An open question is whether motifs identi-
fied in a dynamic social network can, in fact, be coherently interpreted or not [19].
Another possibility may follow from work by Asur et al. [8], who presented an event-
driven framework for analyzing networks where new members join and leave
communities at different time steps.
6
Testing against Exponential Random Graph Models
One set of approaches where the target class and similarity measures are well defined
is under the label “Exponential Random Graph Models” (ERGM). Here the probabili-
ty of any two nodes being directly connected is (indirectly) given a probability, then
one 'fits' this class to some data and constraints, resulting in the most likely network
(or a set of networks) from this class. That is, given an adjacency matrix,
, indicat-
ing the presence of ties between nodes,
0/1
for no tie/tie, then an objective
function,
,
, indicates the preferred 'directions' of change (where
i
is the node
and
x
the network), which gives a probability that
changes to
1
as:
exp
,
∑
exp
,
,
where
denotes the network where
is changed to
1
and
is the
probability of not changing anything [36].
