Modeling and Measuring Graph Similarity: The Case for Centrality Distance

Matthieu Roy, Stefan Schmid, Gilles Trédan

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.

Introduction

In graph theory, the standard approach to comparing two networks is the Graph Edit Distance (GED), which counts the minimum number of edge additions or removals required to transform one graph into another. While mathematically simple, GED is often "blind" to the underlying structure of complex networks. In a social network, for instance, adding a link between two highly connected "hubs" has a much more profound impact on the network's function and information flow than adding a link between two isolated individuals. Yet, to GED, both operations are equivalent.

The Case for Centrality Distance

To address these limitations, we propose Centrality Distance ($d_C$). This framework assigns every node a centrality value—a measure of its importance or role within the network—and calculates similarity as the distance between the centrality vectors of two graphs. This approach preserves node identities, allowing us to track how a specific individual's role changes over time.

Comparison of edge additions with identical GED but different structural impacts.

We explore three primary centrality measures:

  1. Degree Centrality (DC): Based on the number of neighbors. We demonstrate that GED is actually a special case of Degree Centrality distance.
  2. Betweenness Centrality (BC): Based on the frequency with which a node lies on shortest paths.
  3. Closeness Centrality (CC): Based on the average distance from a node to all others.

Our primary focus is on Closeness Centrality Distance ($d_{CC}$), which we identify as a "sensitive" metric where any single edge change affects the centrality of at least one node, ensuring topological changes are captured.

Experimental Methodology

The utility of $d_{CC}$ was evaluated using two real-world dynamic datasets:

  • SOUK: High-resolution physical proximity data of 45 individuals at a cocktail party over 300 time steps.
  • Facebook-like OSN (FBL): Daily snapshots of message exchanges among approximately 20,000 users over 7 months.

The core hypothesis is that real-world networks do not evolve randomly; instead, they follow paths that preserve their structural roles (e.g., through triadic closure).

Results and Discussion

Experimental results strongly validate the centrality distance approach. In the SOUK dataset, the actual observed evolutionary step was closer in $d_{CC}$ than 200 randomly generated alternatives in 298 out of 300 time steps. In the larger, noisier Facebook dataset, the actual path was the "closest" in 73% of snapshots.

Closeness Centrality Distance ($d_{CC}$) tracked over successive rounds of network evolution.

These findings suggest that while a network may undergo significant changes in its raw edge set (high GED), its "closeness structure" remains remarkably stable during natural evolution. This stability allows $d_{CC}$ to effectively distinguish natural growth from random noise.

Conclusion and Future Work

Centrality distance provides a structurally-aware alternative to traditional graph similarity metrics. By focusing on node roles, it offers superior predictive power for network evolution. While calculating centralities like closeness or betweenness is more computationally expensive than edge counting, the resulting insights into network stability and growth are invaluable. Future research will focus on optimizing these calculations for massive graphs and exploring other centrality measures like PageRank or Eigenvector Centrality within this framework.

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},
}
Figure