Sensitivity and Reliability in Incomplete Networks: Centrality Metrics to Community Scoring Functions

Soumya Sarkar, Sanjukta Bhowmick, Suhansanu Kumar, Animesh MukherjeearXiv 2016 · arXiv

In the world of network science, data is rarely perfect. Whether you're mapping social interactions, biological pathways, or transportation grids, you're likely dealing with "incomplete networks"—graphs where some edges are missing due to sampling errors or data gathering limitations.

This paper, "Sensitivity and Reliability in Incomplete Networks," explores a critical question: how does this "noise" (missing edges) affect the metrics we use to analyze these systems? The authors find that a relatively new metric called permanence is a standout performer, offering a unique combination of sensitivity and reliability that traditional metrics lack.

TL;DR

This paper evaluates how missing edges (noise) impact centrality and community scoring metrics. The authors discover that permanence is the most effective metric because it is highly sensitive to network degradation (making it a great noise detector) while remaining remarkably reliable for tasks like message spreading.

What Problem Does This Paper Address?

Network analysis relies on metrics to rank nodes (centrality) or identify groups (community scoring). However, these metrics are often calculated on incomplete data. The authors identify a gap in our understanding of how these metrics behave as noise increases. They define two key properties for a "good" metric under noise:

  1. Sensitivity: The metric should change noticeably as edges are removed. A sensitive metric acts as an early warning system, indicating that the network's topology has significantly shifted.
  2. Reliability: Despite the noise, the metric should still perform well in practical applications. For example, if we use a metric to pick "seed" nodes for spreading a message, those seeds should still be effective even if the network is missing edges.

Methods

The researchers compared several standard metrics across three different noise models (uniform, crawled, and censored):

  • Centrality Metrics: Closeness, Betweenness, and PageRank.
  • Community Scoring Metrics: Modularity, Cut-ratio, and Conductance.
  • The Hybrid: Permanence, a vertex-based community scoring metric that measures how strongly a node belongs to its own community relative to its connections with others.

They evaluated sensitivity by measuring the slope of metric value changes as noise increased from 0% to 30%. They evaluated reliability by simulating message spreading, using the top-ranked nodes of each metric as starting points (seeds) and measuring how many rounds it took to reach the whole network.

Datasets

The study utilized both real-world and synthetic benchmarks:

  • Football: A network of American college football games between teams.
  • Railway: A network representing the Indian railway system.
  • LFR Benchmark: A standard synthetic network generator used to create graphs with known, ground-truth community structures.

Key Insights and Ideas

  • The Permanence Paradox: Usually, sensitivity and reliability are at odds. If a metric's value changes a lot (sensitive), you'd expect its rankings to be unstable (unreliable). Permanence breaks this rule. While its cumulative value drops sharply as edges disappear, the identities of its top-ranked nodes remain stable.
  • Community Metrics are "Noise-Blind": Traditional metrics like Modularity and Conductance are surprisingly insensitive. Their values remain relatively flat even as 30% of edges are removed, meaning they fail to signal that the network model is degrading.
  • Closeness is a Strong Runner-Up: Among traditional centrality measures, closeness centrality proved to be the most sensitive to noise, making it a decent alternative for detecting network changes.

Key Results

  • High Sensitivity: As shown in Figure 1, permanence (the red line) consistently exhibits the steepest slope across different noise models and networks, proving it is the most sensitive indicator of missing edges.
Sensitivity of different metrics. Permanence (red) shows the highest sensitivity to noise.
  • Superior Reliability: In message-spreading experiments (Figure 2), seeds chosen via permanence often resulted in the fastest broadcast times (fewer rounds) under noise, outperforming random selection and often beating traditional centrality measures.
Reliability in message spreading. Lower "Rounds" indicates better performance.
  • Rank Stability: The authors used the Jaccard Index to measure how much the set of top-20 ranked nodes changed under noise. Figure 4 shows that permanence (red) maintains a much higher overlap between the original and noisy networks compared to other metrics, explaining why it remains so reliable.
Jaccard Index showing the stability of top-ranked nodes. Permanence (red) is the most stable.

Limitations and Future Work

The authors acknowledge that while they have empirically demonstrated the strengths of permanence, the underlying analytical reasons for the stability of high-permanence nodes under noise require further investigation.

Future work aims to develop algorithms that can automatically identify the specific "noise threshold"—the point at which a network becomes so incomplete that even robust metrics like permanence begin to fail.

Summary updated

Abstract

Network analysis is an important tool in understanding the behavior of complex systems of interacting entities. However, due to the limitations of data gathering technologies, some interactions might be missing from the network model. This is a ubiquitous problem in all domains that use network analysis, from social networks to hyper-linked web networks to biological networks. Consequently, an important question in analyzing networks is to understand how increasing the noise level (i.e. percentage of missing edges) affects different network parameters. In this paper we evaluate the effect of noise on community scoring and centrality-based parameters with respect to two different aspects of network analysis: (i) sensitivity, that is how the parameter value changes as edges are removed and (ii) reliability in the context of message spreading, that is how the time taken to broadcast a message changes as edges are removed. Our experiments on synthetic and real-world networks and three different noise models demonstrate that for both the aspects over all networks and all noise models, permanence qualifies as the most effective metric. For the sensitivity experiments closeness centrality is a close second. For the message spreading experiments, closeness and betweenness centrality based initiator selection closely competes with permanence. This is because permanence has a dual characteristic where the cumulative permanence over all vertices is sensitive to noise but the ids of the top-rank vertices, which are used to find seeds during message spreading remain relatively stable under noise.
BibTeX
@misc{sarkar2016sensitivity,
  author = {Soumya Sarkar and Sanjukta Bhowmick and Suhansanu Kumar and Animesh Mukherjee},
  title = {{Sensitivity and Reliability in Incomplete Networks: Centrality Metrics to Community Scoring Functions}},
  year = {2016},
  eprint = {1608.05295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1608.05295},
}
Figure