An Axiom System for Feedback Centralities

Tomasz Was, Oskar SkibskiIJCAI 2021 · DOI

TL;DR

This paper introduces the first unified axiomatic system for four classic "feedback" centrality measures (Eigenvector, Katz, Seeley, and PageRank). By defining a set of seven axioms, the authors demonstrate that each of these measures can be uniquely characterized by a specific subset of these axioms, providing a clear framework for understanding their similarities and differences.

What Problem Does This Paper Address?

In network analysis, understanding the importance of nodes is crucial. Centrality measures aim to quantify this importance, but the sheer number of proposed measures makes choosing the right one challenging. "Feedback centralities" are a particularly interesting class, as they assess a node's importance by considering the importance of its neighbors. While individual measures like Eigenvector centrality or PageRank have been axiomatized, there's been a lack of a unified framework that simultaneously considers and differentiates multiple feedback centralities. This makes it difficult to grasp their fundamental relationships and distinctions, hindering informed selection for specific applications.

Methods

The core of this paper is the development of a novel axiomatic system. The authors propose seven axioms:

  • General Axioms (LOC, ED, NC): These are fundamental properties satisfied by all four centrality measures, dealing with graph composition, edge deletion, and node combination.
  • Node-Modification Axioms (EM, EC): These axioms address how centralities behave when node weights or edge weights are modified. Edge Multiplication (EM) scales outgoing edge weights, while Edge Compensation (EC) involves a more complex adjustment of both incoming and outgoing edge weights, as well as node weights.
  • Borderline Axioms (BL, CY): These axioms define centralities on very simple graph structures (a single isolated node for Baseline (BL) and a cycle graph for Cycle (CY)) to anchor the definitions.

The authors then prove that each of the four feedback centralities (Eigenvector, Katz, Seeley, and PageRank) can be uniquely characterized by a specific combination of five of these axioms (three general, one node-modification, and one borderline).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework: The paper's most significant contribution is the creation of a single axiomatic system that encompasses four major feedback centrality measures. This moves beyond individual axiomatizations to a comparative and relational understanding.
  • Distinguishing Measures: The specific combinations of axioms that uniquely characterize each centrality highlight their subtle but important differences. For example, Eigenvector centrality is distinguished by Edge Compensation (EC), while PageRank relies on Edge Multiplication (EM).
  • Walk Interpretations: The paper connects these axiomatic characterizations to walk-based interpretations of these centralities, providing an intuitive understanding of how they operate.
  • Axioms as Building Blocks: The general axioms (LOC, ED, NC) serve as foundational principles, while the node-modification and borderline axioms act as discriminators, allowing for precise characterization.

Key Results

The paper presents four main theorems, each stating that a specific set of five axioms uniquely characterizes one of the four feedback centrality measures:

  • Theorem 1: LOC, ED, NC, EM, and CY uniquely characterize Seeley index.
  • Theorem 2: LOC, ED, NC, EC, and CY uniquely characterize Eigenvector centrality.
  • Theorem 3: LOC, ED, NC, EM, and BL uniquely characterize PageRank.
  • Theorem 4: LOC, ED, NC, EC, and BL uniquely characterize Katz centrality.

The proofs involve constructing specific graph operations and demonstrating how the axioms constrain the behavior of centrality measures, ultimately leading to unique definitions.

Limitations and Future Work

The authors acknowledge that their work focuses on a specific set of four classic feedback centralities. They suggest several directions for future research:

  • Extending to Other Centralities: Applying this axiomatic approach to other centrality measures, such as Degree centrality and Beta measure, which are considered borderline cases of feedback centralities.
  • Random Walk-Based Measures: Investigating centrality measures derived from random walks, like Random Walk Closeness or Decay.
  • Distance-Based Centralities: Developing axiomatizations for distance-based centrality measures in directed graphs.

Summary updated

BibTeX
@inproceedings{was2021axiom,
  author = {Tomasz Was and Oskar Skibski},
  title = {{An Axiom System for Feedback Centralities}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/62},
}
Figure