Introduction
In network science, centrality measures traditionally focus on identifying the most important nodes in a graph. However, many real-world applications—ranging from epidemiology to search engine optimization—require understanding the importance of the edges or connections themselves. While measures like PageRank have been adapted for edges, these adaptations often lack a rigorous theoretical foundation. This paper addresses this gap by providing the first-ever axiomatic characterization of Edge PageRank.
The Problem: Why Edge Centrality?
Standard node centrality measures, such as PageRank, determine the popularity of a node based on its incoming links. Yet, in scenarios like virus outbreaks, the specific flight paths (edges) between cities are often more critical than the cities (nodes) themselves.
Historically, researchers chose edge centrality measures based on intuition or popularity. The authors advocate for an axiomatic approach, where a measure is justified by its adherence to a set of simple, desirable mathematical properties. This allows for a more principled selection of ranking methods based on the specific requirements of a network analysis task.
The Axiomatic Framework
The authors define a framework for directed multigraphs and propose six fundamental axioms that an ideal edge centrality measure should satisfy:
- Node Deletion: Removing an isolated node does not change the importance of any edge.
- Edge Deletion: Removing an edge does not affect the importance of edges that are unreachable from it.
- Edge Multiplication: If a node has a single outgoing edge, splitting it into $k$ parallel copies divides the importance of each copy by $k$ while keeping the rest of the network's importance distribution unchanged.
- Edge Swap: If two edges have equal importance, swapping their target nodes does not change the importance of any edge in the network.
- Node Redirect: If two nodes have identical outgoing edges, they can be merged, and the importance of their corresponding outgoing edges will sum up.
- Baseline: The importance of a single isolated edge is equal to the weight of its source node.
Through rigorous mathematical proof, the authors demonstrate that Edge PageRank is the unique measure that satisfies all six axioms simultaneously.
Key Insights and Results
One significant finding is the limitation of the "Line Graph" approach. A common technique is to transform edges into nodes to create a line graph and then apply standard node PageRank. The authors show that this is insufficient for a formal characterization because the space of line graphs is not closed under certain graph operations, meaning standard node axioms do not always hold.
Comparative Analysis
The paper also evaluates other popular edge centrality measures against the proposed axioms:
- Eigenedge and Edge Katz Centrality fail the Edge Multiplication axiom.
- Edge Betweenness and GTOM fail nearly all axioms except Node Deletion.
- The Seeley Index satisfies the axioms but only within the restricted class of strongly connected graphs.
Conclusion
By establishing a unique axiomatic foundation for Edge PageRank, this work provides a "manual" for practitioners. It clarifies when Edge PageRank is appropriate and highlights its structural properties. Future work may extend this axiomatic approach to undirected graphs or other pair-based measures like node similarity (e.g., SimRank).
Summary updated