Dynamic Shortest Path Algorithms for Hypergraphs

Abstract : A hypergraph is a set V of vertices and a set of non-empty subsets of V , called hyperedges. Unlike graphs, hypergraphs can capture higherorder interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for both random geometric hypergraphs and the Enron email data set. The latter illustrates the application of the proposed algorithms in social networks for identifying the most important actor based on the closeness centrality metric.
Type de document :
Communication dans un congrès
WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.238-245, 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00763797
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 11 décembre 2012 - 15:04:00
Dernière modification le : mercredi 14 février 2018 - 18:16:02
Document(s) archivé(s) le : mardi 12 mars 2013 - 06:25:16

Fichier

p238-gao.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00763797, version 1

Collections

Citation

Jianhang Gao, Qing Zhao, Wei Ren, Ananthram Swami, Ram Ramanathan, et al.. Dynamic Shortest Path Algorithms for Hypergraphs. WiOpt'12: Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, May 2012, Paderborn, Germany. pp.238-245, 2012. 〈hal-00763797〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

227