Egocentric Effective Conductance Centrality and General Degree

Heman Shakeri, Behnaz Moradijamei, Pietro Poggi-Corradini, Nathan Albin, Caterina M. ScoglioarXiv 2017 · DOI · OpenReview

Abstract

We study the popular centrality measure known as effective conductance or in some circles as information centrality. This is an important notion of centrality for undirected networks, with many applications, e.g., for random walks, electrical resistor networks, epidemic spreading, etc. In this paper, we first reinterpret this measure in terms of modulus (energy) of families of walks on the network. This modulus centrality measure coincides with the effective conductance measure on simple undirected networks, and extends it to much more general situations, e.g., directed networks as well. Secondly, we study a variation of this modulus approach in the egocentric network paradigm. Egonetworks are networks formed around a focal node (ego) with a specific order of neighborhoods. We propose efficient analytical and approximate methods for computing these measures on both undirected and directed networks. Finally, we describe a simple method inspired by the modulus point-of-view, called shell degree, which proved to be a useful tool for network science.

Introduction

In network science, identifying the most influential nodes is a critical task. Effective conductance centrality (or information centrality) is a powerful metric that treats a network as an electrical circuit, accounting for all possible paths between nodes. However, traditional sociocentric approaches face two major challenges: high computational costs ($O(|V|^3)$ for matrix inversion) and the practical difficulty of obtaining a global view of large-scale networks like social media or contact tracing graphs.

Methods and Mathematical Framework

The authors address these limitations by reinterpreting effective conductance through the mathematical framework of the modulus of families of walks. This framework generalizes conductance to directed and weighted graphs where traditional electrical analogies may fail.

Egocentric Approach and Shell Modulus

Instead of analyzing the entire graph, the researchers focus on "egonetworks"—the local neighborhood around a focal node (ego). They partition this neighborhood into successive "shells" based on distance. The Shell Modulus is then calculated for walks emanating from the ego to these shells. To facilitate computation, the paper introduces:

  • Analytical Bounds: The Ahlfors upper bound and a tree-based lower bound provide a range for local conductance without requiring complex optimization.
  • Shell Degree ($gDeg$): A practical, local centrality measure that generalizes standard degree. It uses the harmonic mean of ancestral relations in each shell to estimate a node's influence.
Comparison of Shell Modulus, bounds, and Shell Degree across different shells (k=1, 2, 3).

The methods were validated using real-world social networks (e.g., Jazz musicians, Bottlenose dolphins) and various simulated models including Erdős-Rényi and Barabási-Albert networks.

Key Results

The proposed measures demonstrate high accuracy and scalability. Shell Degree consistently provides a "fair estimate" of the true shell modulus across diverse topologies, outperforming simpler bounds.

Scalability and Network Size

A key advantage of the egocentric approach is its computational efficiency. Unlike global measures, the complexity depends on the local neighborhood size, making it feasible for massive networks with hundreds of thousands of edges.

Computed centrality of randomly chosen nodes in scale-free networks as a function of network size.

Epidemic Control

In SIR (Susceptible-Infected-Recovered) model simulations, immunizing nodes based on Shell Degree proved more effective at preventing outbreaks than traditional global measures like Betweenness or Eigenvector Centrality, particularly as vaccination coverage increased. This highlights the practical utility of local, conductance-based measures for public health and targeted immunization strategies.

Conclusion and Future Work

This work bridges the gap between local egocentric data and global network properties. While highly effective, the authors note that shell modulus estimates may degrade in certain pathological network structures as depth increases. Future research will focus on further empirical validation in massive directed graphs and exploring the sensitivity of the neighborhood radius parameter ($r$).

Summary updated

Abstract

We study the popular centrality measure known as effective conductance or in some circles as information centrality. This is an important notion of centrality for undirected networks, with many applications, e.g., for random walks, electrical resistor networks, epidemic spreading, etc. In this paper, we first reinterpret this measure in terms of modulus (energy) of families of walks on the network. This modulus centrality measure coincides with the effective conductance measure on simple undirected networks, and extends it to much more general situations, e.g., directed networks as well. Secondly, we study a variation of this modulus approach in the egocentric network paradigm. Egonetworks are networks formed around a focal node (ego) with a specific order of neighborhoods. We propose efficient analytical and approximate methods for computing these measures on both undirected and directed networks. Finally, we describe a simple method inspired by the modulus point-of-view, called shell degree, which proved to be a useful tool for network science.
BibTeX
@misc{shakeri2017egocentric,
  author = {Heman Shakeri and Behnaz Moradijamei and Pietro Poggi-Corradini and Nathan Albin and Caterina M. Scoglio},
  title = {{Egocentric Effective Conductance Centrality and General Degree}},
  year = {2017},
  eprint = {1705.02703},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.02703},
}
Figure