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.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; Wilfried Elmenreich; Falko Dressler; Vittorio Loreto; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 7th International Workshop on Self-Organizing Systems (IWSOS), May 2013, Palma de Mallorca, Spain. Springer, Lecture Notes in Computer Science, LNCS-8221, pp.115-126, 2014, Self-Organizing Systems. 〈10.1007/978-3-642-54140-7_10〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01291505
Contributeur : Hal Ifip <>
Soumis le : lundi 21 mars 2016 - 15:43:04
Dernière modification le : vendredi 24 novembre 2017 - 11:58:10
Document(s) archivé(s) le : mercredi 22 juin 2016 - 11:13:12

Fichier

978-3-642-54140-7_10_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Panagiotis Pantazopoulos, Merkourios Karaliopoulos, Ioannis Stavrakakis. On the Local Approximations of Node Centrality in Internet Router-Level Topologies. David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; Wilfried Elmenreich; Falko Dressler; Vittorio Loreto; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 7th International Workshop on Self-Organizing Systems (IWSOS), May 2013, Palma de Mallorca, Spain. Springer, Lecture Notes in Computer Science, LNCS-8221, pp.115-126, 2014, Self-Organizing Systems. 〈10.1007/978-3-642-54140-7_10〉. 〈hal-01291505〉

Partager

Métriques

Consultations de la notice

36

Téléchargements de fichiers

44