Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T07:16:13.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Influence of measurement errors on networks: Estimating the robustness of centrality measures

Published online by Cambridge University Press:  05 August 2019

Christoph Martin  and
Peter Niemeyer
Christoph Martin*
Affiliation:
Institute of Information Systems, Leuphana University of Lüneburg, Universitätsallee 1, 21335 Lüneburg, Germany
Peter Niemeyer
Affiliation:
Institute of Information Systems, Leuphana University of Lüneburg, Universitätsallee 1, 21335 Lüneburg, Germany
*
*Corresponding author. Emails: [email protected], [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Most network studies rely on a measured network that differs from the underlying network which is obfuscated by measurement errors. It is well known that such errors can have a severe impact on the reliability of network metrics, especially on centrality measures: a more central node in the observed network might be less central in the underlying network. Previous studies have dealt either with the general effects of measurement errors on centrality measures or with the treatment of erroneous network data. In this paper, we propose a method for estimating the impact of measurement errors on the reliability of a centrality measure, given the measured network and assumptions about the type and intensity of the measurement error. This method allows researchers to estimate the robustness of a centrality measure in a specific network and can, therefore, be used as a basis for decision-making. In our experiments, we apply this method to random graphs and real-world networks. We observe that our estimation is, in the vast majority of cases, a good approximation for the robustness of centrality measures. Beyond this, we propose a heuristic to decide whether the estimation procedure should be used. We analyze, for certain networks, why the eigenvector centrality is less robust than, among others, the pagerank. Finally, we give recommendations on how our findings can be applied to future network studies.

Keywords

centrality measuresmeasurement errormissing datarobustness
Type
Original Article
Information
Network Science , Volume 7 , Issue 2 , June 2019 , pp. 180 - 195
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© Cambridge University Press 2019

References

Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(October), 509–512.CrossRefGoogle ScholarPubMed
Bollobás, B., & Riordan, O. (2002). Mathematical results on scale-free random graphs. Handbook of graphs and networks: From the genome to the internet, 1–38.CrossRefGoogle Scholar
Bonacich, P. (1987). Power and Centrality: A Family of Measures. American Journal of Sociology, 92(5), 1170–1182.CrossRefGoogle Scholar
Borgatti, S. P., Carley, K. M., & Krackhardt, D. (2006). On the robustness of centrality measures under conditions of imperfect data. Social Networks, 28(2), 124–136.CrossRefGoogle Scholar
Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. In Seventh International World-Wide Web Conference (WWW 1998).CrossRefGoogle Scholar
Butts, C. T. (2003). Network inference, error, and informant (in)accuracy: A Bayesian approach. Social Networks, 25(2), 103–140.CrossRefGoogle Scholar
Costenbader, E., & Valente, T. W. (2003). The stability of centrality measures when networks are sampled. Social Networks, 25(4), 283–307.CrossRefGoogle Scholar
Csardi, G., & Nepusz, T. (2006). The igraph software package for complex network research. Interjournal, Complex Systems, 1695, 1–9.Google Scholar
Erdös, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, 290–297.Google Scholar
Fischer, M., Parkins, K., Maizels, K., Sutherland, D. R., Allan, B. M., Coulson, G., & Di Stefano, J. (2018). Biotelemetry marches on: A cost-effective GPS device for monitoring terrestrial wildlife. Plos One, 13(7), e0199617.CrossRefGoogle ScholarPubMed
Frantz, T. L., & Carley, K. M. (2017). Reporting a network’s most-central actor with a confidence level. Computational and Mathematical Organization Theory, 23(2), 301–312.CrossRefGoogle Scholar
Frantz, T. L., Cataldo, M., & Carley, K. M. (2009). Robustness of centrality measures under uncertainty: Examining the role of network topology. Computational and Mathematical Organization Theory, 15(4), 303–328.CrossRefGoogle Scholar
Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239.CrossRefGoogle Scholar
Gleiser, P. M., & Danon, L. (2003). Community structure in jazz. Advances in Complex Systems, 6(4), 565–573.CrossRefGoogle Scholar
Goodman, L. A., & Kruskal, W. H. (1954). Measures of association for cross classifications. Journal of the American Statistical Association, 49(268), 732–764.Google Scholar
Handcock, M. S., & Gile, K. J. (2010). Modeling social networks from sampled data. The Annals of Applied Statistics, 4(1), 5–25.CrossRefGoogle ScholarPubMed
Huisman, M. (2009). Imputation of missing network data: Some simple procedures. Journal of Social Structure, 10(1), 1–29.Google Scholar
Jeong, H., Mason, S. P., Barabasi, A.-L., & Oltvai, Z. N. (2001). Lethality and centrality in protein networks. Nature, 411(6833), 41–42.CrossRefGoogle ScholarPubMed
Kendall, M. G. (1945). The treatment of ties in ranking problems. Biometrika, 33(3), 239–251.CrossRefGoogle ScholarPubMed
Kim, M., & Leskovec, J. (2011). The network completion problem: Inferring missing nodes and edges in networks. In Siam international conference on data mining, 47–58.CrossRefGoogle Scholar
Kim, P. J., & Jeong, H. (2007). Reliability of rank order in sampled networks. European Physical Journal b, 55(1), 109–114.CrossRefGoogle Scholar
Koschützki, D., Lehmann, K., & Peeters, L. (2005). Centrality Indices. In Brandes, U., & Erlebach, T. (eds.), Network Analysis: Methodological Foundations, 16–61. Springer Berlin Heidelberg.CrossRefGoogle Scholar
Krause, R. W., Huisman, M., Steglich, C., & Sniiders, T. A. (2018, August). Missing Network Data A Comparison of Different Imputation Methods. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 159–163.CrossRefGoogle Scholar
Kunegis, J. (2013). KONECT - The Koblenz network collection. In WWW 2013 Companion - Proceedings of the 22nd International Conference on World Wide Web.CrossRefGoogle Scholar
Lee, J.-S., & Pfeffer, J. (2015). Robustness of network centrality metrics in the context of digital communication data. In Proceedings of the 48th Hawaii international conference on system sciences.CrossRefGoogle Scholar
Leecaster, M., Toth, D. J. A., Pettey, W. B. P., Rainey, J. J., Gao, H., Uzicanin, A., & Samore, M. (2016). Estimates of social contact in a middle school based on self-report and wireless sensor data. Plos One, 11(4).CrossRefGoogle Scholar
Lusseau, D., Schneider, K., Boisseau, O. J., Haase, P., Slooten, E., & Dawson, S. M. (2003). The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology, 54(4), 396–405.CrossRefGoogle Scholar
Newman, M. E. J. (2018). Network structure from rich but noisy data. Nature Physics, 14, 542–545.CrossRefGoogle Scholar
Niu, Q., Zeng, A., Fan, Y., & Di, Z. (2015). Robustness of centrality measures against network manipulation. Physica A: Statistical Mechanics and Its Applications, 438, 124–131.CrossRefGoogle Scholar
Platig, J., Ott, E., & Girvan, M. (2013). Robustness of network measures to link errors. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 88(6).CrossRefGoogle ScholarPubMed
Schulz, J. (2016). Using Monte Carlo simulations to assess the impact of author name disambiguation quality on different bibliometric analyses. Scientometrics, 107(3), 1283–1298.CrossRefGoogle Scholar
Silk, M. J., Jackson, A. L., Croft, D. P., Colhoun, K., & Bearhop, S. (2015). The consequences of unidentifiable individuals for the analysis of an animal social network. Animal Behaviour, 104, 1–11.CrossRefGoogle Scholar
Smith, J. A., & Moody, J. (2013). Structural Effects of Network Sampling Coverage I: Nodes Missing at Random. Social Networks, 35(4).CrossRefGoogle Scholar
Smith, J. A., Moody, J., & Morgan, J. H. (2017). Network sampling coverage II: The effect of non-random missing data on network measurement. Social Networks, 48, 78–99.CrossRefGoogle ScholarPubMed
Valente, T. W., Coronges, K., Lakon, C., & Costenbader, E. (2008). How correlated are network centrality measures? Connections, 28(1), 16–26.Google ScholarPubMed
Wang, C., Butts, C. T., Hipp, J. R., Jose, R., & Lakon, C. M. (2016). Multiple imputation for missing edge data: A predictive evaluation method with application to Add Health. Social Networks, 45, 89–98.CrossRefGoogle ScholarPubMed
Wang, D. J., Shi, X., McFarland, D. A., & Leskovec, J. (2012). Measurement error in network data: A re-classification. Social Networks, 34(4), 396–409.CrossRefGoogle Scholar
Žnidaršič, A., Ferligoj, A., & Doreian, P. (2018). Stability of centrality measures in valued networks regarding different actor non-response treatments and macro-network structures. Network Science, 6(01), 1–33.CrossRefGoogle Scholar