Dynamic Shortest Path Algorithms for Hypergraphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Dynamic Shortest Path Algorithms for Hypergraphs

Résumé

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.
Fichier principal
Vignette du fichier
p238-gao.pdf (522.82 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

hal-00763797 , version 1 (11-12-2012)

Identifiants

  • HAL Id : hal-00763797 , version 1

Citer

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. ⟨hal-00763797⟩

Collections

WIOPT2012
109 Consultations
408 Téléchargements

Partager

Gmail Facebook X LinkedIn More