Skip to Main content Skip to Navigation
Conference papers

On the Local Approximations of Node Centrality in Internet Router-Level Topologies

Abstract : In many networks with distributed operation and self-organization features, acquiring their global topological information is impractical, if feasible at all. Internet protocols drawing on node centrality indices may instead approximate them with their egocentric counterparts, computed out over the nodes’ ego-networks. Surprisingly, however, in router-level topologies the approximative power of localized ego-centered measurements has not been systematically evaluated. More importantly, it is unclear how to practically interpret any positive correlation found between the two centrality metric variants.The paper addresses both issues using different datasets of ISP network topologies. We first assess how well the egocentric metrics approximate the original sociocentric ones, determined under perfect network-wide information. To this end we use two measures: their rank-correlation and the overlap in the top-k node lists the two centrality metrics induce. Overall, the rank-correlation is high, in the order of 0.8-0.9, and, intuitively, becomes higher as we relax the ego-network definition to include the ego’s r-hop neighborhood. On the other hand, the top-k node overlap is low, suggesting that the high rank-correlation is mainly due to nodes of lower rank. We then let the node centrality metrics drive elementary network operations, such as local search strategies. Our results suggest that, even under high rank-correlation, the locally-determined metrics can hardly be effective aliases for the global ones. The implication for protocol designers is that rank-correlation is a poor indicator for the approximability of centrality metrics.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, March 21, 2016 - 3:43:04 PM
Last modification on : Thursday, November 26, 2020 - 3:50:03 PM
Long-term archiving on: : Wednesday, June 22, 2016 - 11:13:12 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Panagiotis Pantazopoulos, Merkourios Karaliopoulos, Ioannis Stavrakakis. On the Local Approximations of Node Centrality in Internet Router-Level Topologies. 7th International Workshop on Self-Organizing Systems (IWSOS), May 2013, Palma de Mallorca, Spain. pp.115-126, ⟨10.1007/978-3-642-54140-7_10⟩. ⟨hal-01291505⟩



Record views


Files downloads