The idemetric property: when most distances are (almost) the same.

Area of Science:

• Graph theory
• Network science
• Algorithm analysis

Background:

• Small-world network models often exhibit similar distances between nodes.
• Previous research highlighted limitations of decentralized algorithms for shortest path finding in certain network models.

Purpose of the Study:

• Introduce and formalize the 'idemetric' property for graphs.
• Investigate the relationship between idemetricity and expander conditions.
• Analyze the implications of idemetricity for algorithm design, particularly shortest path and routing algorithms.

Main Methods:

• Formal definition of the idemetric property.
• Mathematical proofs establishing equivalence between idemetricity and expander conditions (PUMP).
• Analysis of algorithms (e.g., Breadth-First Search) on idemetric graphs.

Main Results:

• Strong idemetricity is equivalent to a weak expander condition.
• Small-world network models like Watts-Strogatz and Kleinberg's model are shown to be idemetric.
• For idemetric graphs, all-pairs shortest paths can be approximated efficiently using BFS.
• Deterministic distributed routing requires significantly less information (O(n log n)) on idemetric graphs compared to the worst case (Ω(n^2)) for achieving stretch < 3.

Conclusions:

• The idemetric property is a common and useful characteristic of many real-world networks.
• Idemetricity enables efficient shortest path and routing algorithms, overcoming previous limitations.
• This work provides a new perspective on network analysis and algorithm design for distributed systems.