Accession Number:

ADA456108

Title:

Relating Network Topology to the Robustness of Centrality Measures

Descriptive Note:

Technical rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Report Date:

2005-05-01

Pagination or Media Count:

25.0

Abstract:

This paper reports on a simulation study of social networks that investigated how network topology relates to the robustness of measures of system-level 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 six-factor full-factorial 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 uniform-random networks, while the core-periphery networks had a considerably different profile. The centrality measures for the core-periphery 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 deteriorates and ultimately converges.

Subject Categories:

  • Statistics and Probability
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE