Accession Number:

ADA558936

Title:

Dynamic Shortest Path Algorithms for Hypergraphs

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV DAVIS

Report Date:

2012-01-01

Pagination or Media Count:

12.0

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 higher-order 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 addressing 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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE