NDLI: Dynamic shortest path algorithms for hypergraphs

Content Provider	IEEE Xplore Digital Library
Author	Gao, Jianhang Zhao, Qing Ren, Wei Swami, Ananthram Ramanathan, Ram Bar-Noy, Amotz
Copyright Year	2012
Description	Author affiliation: Raytheon BBN Technologies, Cambridge, MA, USA (Ramanathan, Ram) \|\| Microsoft Corperation, Redmond, WA, USA (Ren, Wei) \|\| Department of Computer Science, City University of New York, USA (Bar-Noy, Amotz) \|\| Department of Electrical and Computer Engineering, University of California, Davis, USA (Gao, Jianhang; Zhao, Qing) \|\| Army Research Laboratory, Adelphi, MD, USA (Swami, Ananthram)
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 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.
Starting Page	238
Ending Page	245
File Size	168205
Page Count	8
File Format	PDF
ISBN	9781467322942
e-ISBN	9783901882456
e-ISBN	9783901882470
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-14
Publisher Place	Germany
Access Restriction	Subscribed
Rights Holder	IFIP
Subject Keyword	Shortest path problem Heuristic algorithms Social network services Color Partitioning algorithms Complexity theory Electronic mail
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic Shortest Path Algorithms for Hypergraphs

Incremental algorithm for updating betweenness centrality in dynamically growing networks

Dynamic Shortest Path Algorithms for Hypergraphs (2014)

Degree Anonymization for K-Shortest-Path Privacy

Incremental closeness centrality for dynamically changing social networks

Shortest paths subject to time-varying stochastic transit times

Community detection using a neighborhood strength driven Label Propagation Algorithm

SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process

Fractal Graph Optimization Algorithms

Dynamic shortest path algorithms for hypergraphs

Similar Documents

Dynamic Shortest Path Algorithms for Hypergraphs

Incremental algorithm for updating betweenness centrality in dynamically growing networks

Dynamic Shortest Path Algorithms for Hypergraphs (2014)

Degree Anonymization for K-Shortest-Path Privacy

Incremental closeness centrality for dynamically changing social networks

Shortest paths subject to time-varying stochastic transit times

Community detection using a neighborhood strength driven Label Propagation Algorithm

SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process

Fractal Graph Optimization Algorithms

Dynamic shortest path algorithms for hypergraphs