Localized Centrality Estimation in Large Networks

21 concepts17 papers1 proposal

Evaluating the importance of a node within a network—its centrality—is a foundational task in network science. Traditional metrics like betweenness centrality, eigenvector centrality, and core numbers are explicitly global. To know how many shortest paths pass through a node, or how well-connected its neighbors' neighbors are, you traditionally need a complete, static map of the entire network.

On massive, real-world graphs, this global requirement creates a severe computational bottleneck. Algorithms for exact betweenness centrality require full graph traversals that scale poorly with network size. Furthermore, in decentralized or privacy-sensitive systems, a centralized repository of the entire network topology simply does not exist.

To bypass these limitations, a powerful paradigm has emerged: localized centrality estimation. Instead of traversing the entire graph, these techniques approximate global importance metrics by analyzing small, bounded neighborhoods around target nodes.

Why Local Information Predicts Global Centrality

It is not immediately obvious why a local view should accurately predict a global property. If you only look at a node and its immediate neighbors, how can you tell if it bridges two massive, distant communities?

The intuition lies in the structural properties of real-world networks. Graphs like social networks, road maps, and knowledge bases are not random tangles; they possess structural sparsity, latent geometric organization, and community clustering. Because of these properties, global paths and network flows are heavily constrained by local boundaries. A node that acts as a critical bottleneck globally will almost always manifest as a unique structural hub or high-energy bridge within its immediate ego network.

[Global Network] 
       │
       ▼ (Constrained by structural sparsity & latent geometry)
[Constant-Radius Neighborhood / Ego Network] 
       │
       ▼ (Local metrics: Graph energy, local message passing)
[Accurate Proxy for Global Centrality]

By shifting the computational focus from the entire graph to independent, local neighborhoods, we can transform global graph problems into highly parallelizable, linear-time computations.

Ego Networks and Constant-Radius Proxies

The most direct way to localize centrality is to restrict the horizon of computation to a constant radius $r$ around a vertex, often referred to as an ego network when $r=1$ or $r=2$.

Qi Zhang et al. demonstrated this effectively in Efficient Top-k Ego-Betweenness Search. Instead of calculating shortest paths across the entire graph to find key bridge nodes, the authors restricted shortest-path calculations strictly to each node's immediate ego network. This local scope isolates independent computations for each vertex, capturing a remarkably high percentage of the top global bridges at a fraction of the computational cost.

But what structural features within these local neighborhoods best mirror global importance? Mikolaj Morzy et al. explored this by analyzing the "graph energy" (a metric derived from a graph's eigenvalues) of egocentric networks in Graph Energies of Egocentric Networks and Their Correlation with Vertex Centrality Measures. The authors discovered that the internal structural density and energy of a local ego network correlate strongly with traditional, expensive global metrics like betweenness and eigencentrality.

This localization is backed by rigorous structural theory. In Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs, Felix Reidl et al. proved that for networks exhibiting "bounded expansion" (a formal measure of structural sparsity), analyzing a constant-radius neighborhood is mathematically sufficient to identify the most globally central nodes in linear time.

Similarly, dense structural properties like a node's "core number" (its placement in the hierarchical $k$-core decomposition of a graph) can be inferred locally. While traditional core decomposition requires recursively peeling nodes from the entire graph, Michael P. O'Brien et al. in Locally Estimating Core Numbers and Fragkiskos D. Malliaros et al. in Core Decomposition in Graphs: Concepts, Algorithms and Applications showed that a vertex's coreness can be accurately estimated using only local neighborhood information, bypassing full network traversals entirely.

Targeted and Query-Dependent Estimation

In many practical applications, we do not actually need to know the centrality scores of every single node in a network simultaneously. Instead, we often want to evaluate a specific subset of nodes or respond to a localized query. Traditional algorithms cause massive computational waste because they must compute global state just to resolve a local query.

To address this, researchers have designed targeted estimation algorithms. For instance, when analyzing directed graphs, Talel Abdessalem et al. introduced algorithms in Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs that isolate only the specific subset of nodes capable of reaching a target vertex. This prunes away the vast majority of the network, computing exact or approximate betweenness scores orders of magnitude faster.

When exact pruning is insufficient, targeted importance sampling can fill the gap. In Metropolis-Hastings Algorithms for Estimating Betweenness Centrality, Albert Bifet et al. utilized localized Markov chains to sample source nodes from an optimal distribution. This allows applications to focus entirely on calculating the centrality of a specific node or subset of interest without exhaustive network processing.

This query-dependent localization is highly effective in specialized domains:

  • Entity-Relationship Graphs: In Efficient Computation of Relationship-Centrality in Large Entity-Relationship Graphs, Stephan Seufert et al. focused on finding "bridge" entities that connect two specific sets of nodes. By utilizing distance-based pruning to explore only the local neighborhood around the query nodes, the authors achieved a tenfold reduction in processing time while maintaining a high rank correlation with global results.
  • Spatial Road Networks: Monitoring critical traffic intersections requires real-time updates that global algorithms cannot provide. In Efficient processing of coverage centrality queries on road networks, Yehong Xu et al. leveraged localized Shortest Path Trees (SPT) and novel pruning strategies to enable rapid single-vertex queries for coverage centrality, allowing real-time tracking as road conditions change.

Distributed and Privacy-Preserving Centrality

Localized centrality is not merely a tool for acceleration; it is an architectural necessity for distributed systems where data privacy or network fragmentation prevents global visibility.

Consider a peer-to-peer (P2P) network or a privacy-sensitive social network. In Message Passing Optimization of Harmonic Influence Centrality, Luca Vassio et al. designed a decentralized message-passing algorithm inspired by electrical circuits. Nodes execute purely local interactions with immediate neighbors to compute their own Harmonic Influence Centrality, identifying their ability to sway network-wide opinions without any central data repository.

Similarly, in P2P overlay architectures, Nicolas Kourtellis et al. demonstrated in Leveraging Peer Centrality in the Designof Socially-Informed Peer-to-Peer Systems that the global centrality of a peer in a projection graph can be accurately estimated by aggregating the local centrality of the users hosted on that peer.

[Neighbor Node A] <───(Local Message Passing)───> [Target Node] <───(Local Message Passing)───> [Neighbor Node B]
                                                        │
                                             (Aggregates Local Signals)
                                                        ▼
                                          [Estimated Centrality Score]

This decentralized paradigm is vital for real-world crisis response, such as contact tracing. In Kemeny-based testing for COVID-19, Şerife Yılmaz et al. highlighted that identifying critical "bridge" individuals who connect different communities normally requires a privacy-violating centralized database. The authors argued that distributed estimation methods using local random walks can mitigate these risks, allowing nodes to discover if they are bridges using only local interactions.

Remarkably, network topology isn't always required to estimate centrality. In Blind Estimation of Eigenvector Centrality from Graph Signals: Beyond Low-pass Filtering, T Mitchell Roddenberry et al. proved that eigenvector centrality can be recovered purely from data signals observed at the nodes, bypassing the resource-heavy step of full graph recovery entirely. When broader network properties like radius or diameter are needed in a distributed setting, Bertie Ancona et al. showed in Distributed Distance Approximation that a small "committee" of representative nodes can be selected locally to approximate the distance profile of the entire network efficiently.

The Latent Geometry of Locality

Why do these local approximations hold up so robustly against exact global calculations? The answer is increasingly found in the underlying geometry of networks.

In Latent Geometry-Driven Network Automata for Complex Network Dismantling, Thomas Adler et al. shifted the problem of network dismantling away from slow, global shortest-path calculations. Instead, they utilized fast, local geometric approximations. They demonstrated that a network's structural vulnerability and its nodes' bridging properties are deeply encoded in the hidden "latent space" of a node's immediate neighborhood.

Because global paths are fundamentally shaped by these local geometric properties, local estimators do not just guess global centrality—they measure the very structural features that create it.

Key Foundational Work

Locally Estimating Core Numbers (2014) — contributed 2 concept elements to this direction.
Leveraging Peer Centrality in the Designof Socially-Informed Peer-to-Peer Systems (2014) — contributed 2 concept elements to this direction.
Efficient Computation of Relationship-Centrality in Large Entity-Relationship Graphs (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_localized_centrality_estimation_5c2c9711,
  title = {localized centrality estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/localized-centrality-estimation/rdr_5c2c9711151a40c284e79ca509f8b5b0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_localized_centrality_estimation_5c2c9711_v1,
  title = {localized centrality estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/localized-centrality-estimation/rdr_5c2c9711151a40c284e79ca509f8b5b0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake