Modeling and measuring graph similarity: the case for centrality distance

Matthieu Roy, Stefan Schmid, Gilles Trédan

TL;DR

This paper introduces centrality distance, a novel framework for measuring how similar two graphs are by looking at how the "importance" of their nodes changes. By moving beyond simple edge-counting metrics, the authors demonstrate that real-world social networks evolve along paths that preserve structural roles, allowing us to distinguish natural network growth from random noise.

What Problem Does This Paper Address?

In graph theory, the standard way to compare two networks is the Graph Edit Distance (GED)—essentially counting the minimum number of edge additions or removals needed to turn Graph A into Graph B.

However, the authors argue that GED is "blind" to the actual structure of complex networks. In a social network, adding a link between two highly connected "hubs" has a much larger impact on the network's function than adding a link between two isolated individuals. Yet, to GED, both operations cost exactly "1." Furthermore, most traditional metrics treat nodes as anonymous, but in the real world (social networks, infrastructure, etc.), nodes have identities. We care about how Alice's role changes, not just the abstract shape of the graph.

Methods

The authors propose Centrality Distance ($d_C$). The core idea is to assign every node a "centrality" value (a measure of its importance) and then calculate the distance between two graphs as the sum of the differences in these values for all nodes.

The paper explores three main types of centrality:

  1. Degree Centrality (DC): How many neighbors a node has. (The authors interestingly prove that GED is actually a special case of Degree Centrality distance).
  2. Betweenness Centrality (BC): How often a node sits on the shortest path between others.
  3. Closeness Centrality (CC): How "near" a node is to all other nodes in the network.

The researchers focus on Closeness Centrality Distance ($d_{CC}$) as their primary case study. They define a "sensitive" centrality as one where any single edge change affects at least one node's value, ensuring the metric is mathematically sound for distinguishing different topologies.

Datasets

The authors evaluated their approach using two dynamic real-world datasets:

  • SOUK: A high-resolution dataset capturing the physical proximity of 45 individuals during a cocktail party over 300 discrete time steps.
  • FBL: A dataset of a Facebook-like Online Social Network (OSN) covering roughly 20,000 users over 7 months, discretized into 187 daily snapshots of message exchanges.

Key Insights and Ideas

  • GED is a Subset: The realization that the classic Graph Edit Distance is mathematically equivalent to Degree Centrality distance is a powerful "aha moment." It frames GED not as the "default" metric, but as the simplest (and perhaps most limited) version of a broader family of centrality-based measures.
  • Evolution isn't Random: Real networks don't just add edges haphazardly. The authors found that actual evolutionary paths in social networks (like "triadic closure"—becoming friends with a friend's friend) result in much smaller changes in closeness centrality than random edge additions would.
  • Predictive Power: Because real evolution follows "low-distance" paths in the centrality space, this metric can be used to distinguish between a "fake" (randomly generated) successor network and the "actual" successor network with high probability.

Key Results

The experimental results strongly support the utility of Closeness Centrality Distance:

  • Distinguishing Reality: In the SOUK dataset, the actual observed next step of the network was closer in $d_{CC}$ than 200 randomly generated alternatives (with the same GED) in 298 out of 300 time steps.
  • Consistency in OSNs: In the larger Facebook dataset, the actual evolutionary path was the "closest" in 73% of the snapshots, despite the much higher noise and scale of the network.
  • Structural Stability: The research shows that while a network might change significantly in terms of raw edges (high GED), its "closeness structure" remains remarkably stable during natural evolution.

Limitations and Future Work

The primary limitation acknowledged is computational complexity. Calculating centralities like Betweenness or Closeness for every node in a massive, rapidly changing graph is computationally expensive compared to simply counting edges.

The authors suggest several avenues for future work:

  • Exploring other centralities like PageRank or Eigenvector Centrality within this distance framework.
  • Investigating how Betweenness Distance could be used to study graph clustering and community detection over time.
  • Developing more efficient algorithms for calculating these distances in large-scale dynamic graphs to make the tool more practical for real-time monitoring.

Summary updated

Abstract

The study of the topological structure of complex networks has fascinated researchers for several decades, and today we have a fairly good understanding of the types and reoccurring characteristics of many different complex networks. However, surprisingly little is known today about models to compare complex graphs, and quantitatively measure their similarity. This paper proposes a natural similarity measure for complex networks: centrality distance, the difference between two graphs with respect to a given node centrality. Centrality distances allow to take into account the specific roles of the different nodes in the network, and have many interesting applications. As a case study, we consider the closeness centrality in more detail, and show that closeness centrality distance can be used to effectively distinguish between randomly generated and actual evolutionary paths of two dynamic social networks.
BibTeX
@inproceedings{roy2014modeling,
  author = {Matthieu Roy and Stefan Schmid and Gilles Trédan},
  title = {{Modeling and measuring graph similarity: the case for centrality distance}},
  booktitle = {FOMC},
  year = {2014},
  url = {https://openreview.net/forum?id=aLVdN_MKjJ},
}

Loading related content...

Figure