
CMUISRI05117
Institute for Software Research International
School of Computer Science, Carnegie Mellon University
CMUISRI05117
Relating Network Topology to the
Robustness of Centrality Measures
Terrill L. Frantz, Kathleen M. Carley
May 2005
Center for Computational Analysis of Social and Organizational Systems
CASOS Technical Report
CMUISRI05117.pdf
Keywords: Social networks, data error, centrality, robustness, sensitivity, simulation
This paper reports on a simulation study of social networks that
investigated how network topology relates to the robustness of
measures of systemlevel node centrality. This association is
important to understand as data collected for social network
analysis is often somewhat erroneous and may  to an unknown degree 
misrepresent the actual true network. Consequently the values
for measures of centrality calculated from the collected network data
may also vary somewhat from those of the true network, possibly leading
to incorrect suppositions. To explore the robustness, i.e., sensitivity,
of network centrality measures in this circumstance, we conduct
Monte Carlo experiments whereby we generate an initial network,
perturb its copy with a specific type of error, then compare the
centrality measures from two instances. We consider the initial
network to represent a true network, while the perturbed represents
the observed network. We apply a sixfactor fullfactorial block
design for the overall methodology. We vary several control variables
(network topology, size and density, as well as error type, form and
level) to generate 10,000 samples each from both the set of all
possible networks and possible errors within the parameter space.
Results show that the topology of the true network can dramatically
affect the robustness profile of the centrality measures. We found
that across all permutations that cellular networks had a nearly
identical profile to that of uniformrandom networks, while the
coreperiphery networks had a considerably different profile.
The centrality measures for the coreperiphery networks are highly
sensitive to small levels of error, relative to uniform and cellular
topologies. Except in the case of adding edges, as the error increases,
the robustness level for the 3 topologies deteriorate and ultimately
converges.
24 pages
