Measuring the sensitivity of graph metrics to missing data

Anita Zakrzewska, David A. Bader

Research output: Contribution to journalConference articlepeer-review


The increasing energy consumption of high performance computing has resulted in rising operational and environmental costs. Therefore, reducing the energy consumption of computation is an emerging area of interest. We study the approach of data sampling to reduce the energy costs of sparse graph algorithms. The resulting error levels for several graph metrics are measured to analyze the trade-off between energy consumption reduction and error. The three types of graphs studied, real graphs, synthetic random graphs, and synthetic small-world graphs, each show distinct behavior. Across all graphs, the error cost is initially relatively low. For example, four of the five real graphs studied needed less than a third of total energy to retain a degree centrality rank correlation coefficient of 0.85 when random vertices were removed. However, the error incurred for further energy reduction grows at an increasing rate, providing diminishing returns.

Original languageEnglish (US)
Pages (from-to)783-792
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8384 LNCS
Issue numberPART 1
StatePublished - 2014
Externally publishedYes
Event10th International Conference on Parallel Processing and Applied Mathematics, PPAM 2013 - Warsaw, Poland
Duration: Sep 8 2013Sep 11 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Energy consumption
  • Graph algorithms
  • Graphs
  • Missing data
  • Power
  • Sensitivity analysis


Dive into the research topics of 'Measuring the sensitivity of graph metrics to missing data'. Together they form a unique fingerprint.

Cite this