Measuring the sampling robustness of complex networks

Katchaguy Areekijseree, Sucheta Soundarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

When studying a network, it is often of interest to understand the robustness of that network to noise. Network robustness has been studied in a variety of contexts, examining network properties such as the number of connected components and the lengths of shortest paths. In this work, we present a new network robustness measure, which we refer to as ‘sampling robustness’. The goal of the sampling robustness measure is to quantify the extent to which a network sample collected from a graph with errors is a good representation of a network sample collected from that same graph, but without errors. These errors may be introduced by humans or by the system (e.g., mistakes from the respondents or a bug in an API program), and may affect the performance of a data collection algorithm and the quality of the obtained sample. Thus, when data analysts analyze the sampled network, they may wish to know whether such errors will affect future analysis results. We demonstrate that sampling robustness is dependent on a few, easily-computed properties of the network: the leading eigenvalue, average node degree and clustering coefficient. In addition, we introduce regression models for estimating sampling robustness given an obtained sample. As a result, our models can estimate the sampling robustness with MSE < 0.0015 and the model has an R-squared of up to 75%.

Original languageEnglish (US)
Title of host publicationProceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019
EditorsFrancesca Spezzano, Wei Chen, Xiaokui Xiao
PublisherAssociation for Computing Machinery, Inc
Pages294-301
Number of pages8
ISBN (Electronic)9781450368681
DOIs
StatePublished - Aug 27 2019
Event11th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019 - Vancouver, Canada
Duration: Aug 27 2019Aug 30 2019

Publication series

NameProceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019

Conference

Conference11th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019
CountryCanada
CityVancouver
Period8/27/198/30/19

ASJC Scopus subject areas

  • Communication
  • Computer Networks and Communications
  • Information Systems and Management
  • Sociology and Political Science

Fingerprint Dive into the research topics of 'Measuring the sampling robustness of complex networks'. Together they form a unique fingerprint.

  • Cite this

    Areekijseree, K., & Soundarajan, S. (2019). Measuring the sampling robustness of complex networks. In F. Spezzano, W. Chen, & X. Xiao (Eds.), Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019 (pp. 294-301). (Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2019). Association for Computing Machinery, Inc. https://doi.org/10.1145/3341161.3342873