Dynamic Shortest Path Algorithms for Hypergraphs

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.


I. INTRODUCTION
A graph is a basic mathematical abstraction for modeling networks, in which nodes are represented by vertices and pairwise relationships are represented by edges between vertices. A graph is thus given by a vertex set V and an edge set E consisting of cardinality-2 subsets of V . A hypergraph is a natural extension of a graph obtained by removing the constraint on the cardinality of an edge: any non-empty subset of V can be an element (a hyperedge) of the edge set E (see Fig 1). It thus captures group behaviors and higher-dimensional relationships in complex networks that are more than a simple union of pairwise relationships. Examples include communities and collaboration teams in social networks, document clusters in information networks, and cliques, neighborhoods, and multicast groups in communication networks. While the concept of hypergraph has been around since 1920's (see, for example, [1]), many well-solved algorithmic 0 This work was supported by the Army Research Laboratory NS-CTA under Grant W911NF-09- 2-0053. problems in graph theory remain largely open under this more general model. In this paper, we address the shortest path problem in hypergraphs.

A. Shortest Path Problem in Graphs
The shortest path problem is perhaps one of the most basic problems in graph theory. It asks for the shortest path between two vertices or from a source vertex to all the other vertices (i.e., the single-source version or the shortest path tree). Depending on whether the edge weights can be negative, the problem can be solved via Dijkstra's algorithm or Bellman-Ford algorithm [2]. This basic problem finds diverse applications in communication networks, operational research, plant and facility layout, and VLSI design [3].
The dynamic version of the shortest path problem is to maintain the shortest path tree without recomputing from scratch during a sequence of changes to the graph. A typical change to a graph includes weight increase, weight decrease, edge insertion, and edge deletion. The last two types of changes model network topological changes, but they can be conceptually considered as special cases of weight changes by allowing weight to be infinity. Thus, if the sequence of changes contains only weight increase and edge deletion, we call it a decremental problem; if it contains only weight decrease and edge insertion, we call it an incremental problem. Otherwise, we have a fully dynamic problem. If multiple edges change simultaneously, then it is called a batch problem.
There have been a number of studies of the dynamic shortest path problem in graphs. Ramalingam and Reps [4], Frigioni et al. [5,6], and Narvaez et al. [7] proposed several algorithms for the single-change problem. The batch problem was considered in [7][8][9]. Comprehensive experiments on the comparison of different batch algorithms can be found in [9,10].

B. Shortest Path Problem in Hypergraphs
Both the static and dynamic shortest path problems have a corresponding version in hypergraphs. The static shortest hyperpath problem was considered by Knuth [11] and Gallo et al. [12], in which Dijkstra's algorithm was extended to obtain the shortest hyperpaths. Knuth's algorithm is for a special class of hypergraphs while Gallo's algorithm is for a general hypergraph. Ausiello et al. proposed a dynamic shortest hyperpath algorithm for directed hypergraphs, considering only the incremental problem with the weights of all hyperedges limited to a finite set of numbers [13,14]. A dynamic algorithm for the batch problem in a special class of hypergraphs was developed in [8].
With the exception of the above few studies, the shortest hyperpath problem remains largely unexplored. To the best of our knowledge, no algorithms exist for the fully dynamic problem in a general hypergraph.
In this paper, we develop two fully dynamic shortest path algorithms for general hypergraphs. These two algorithms complement each other, with each preferred in different types of hypergraphs and dynamics.
Referred to as the HyperEdge based Dynamic Shortest Path algorithm (HE-DSP), the first algorithm is an extension of the dynamic Dijkstra's algorithm for graphs to hypergraphs (parallel to Gallo's extension of the static Dijkstra's algorithm to hypergraphs in [12]). The extension of the dynamic Dijkstra's algorithm to hypergraphs is more involved than that of the static Dijkstra's algorithm. This is due to the loss of the tree structure (in the original graph sense) in the collection of the shortest hyperpaths from a source to all other vertices. Since the dynamic Dijkstra's algorithm relies on the tree structure to update the shortest paths after an incremental change (weight increase or edge deletion), special care needs to be given when extending it to hypergraphs.
The second algorithm is rooted in the idea of Dimension Reduction and is referred to as DR-DSP. The basic idea is to reduce the problem to finding the shortest path in the underlying graph of the hypergraph. The underlying graph of a hypergraph has the same vertex set and has an edge between two vertices if and only if there is at least one hyperedge containing these two vertices in the original hypergraph. The weight of an edge in the underlying graph is defined as the minimum weight among all hyperedges containing the two vertices of this edge. The shortest hyperpath in the hypergraph can thus be obtained from the shortest path in the underlying graph by substituting each edge along the shortest path with the hyperedge that lent its weight to this edge. The correctness and advantage of this algorithm are readily seen: the definition of weight in the underlying graph captures the minimum cost offered by all hyperedges in choosing a path between two vertices, thus ensuring the correctness of the algorithm; the reduction of a hypergraph to its underlying graph removes many hyperedges from consideration when finding the shortest path, leading to efficiency and agility to dynamic changes.
HE-DSP is more efficient in hypergraphs that are densely connected through high-dimensional hyperedges and for network dynamics where changes often occur to hyperedges that are not on the current shortest hyperpaths. DR-DSP has lower complexity when hyperedge changes often lead to changes in the shortest hyperpaths. This is usually the case in networks where hyperedges in the shortest hyperpaths are more prone to changes due to attacks, frequent use, or higher priority in maintenance and upgrade. Furthermore, DR-DSP leads to an alternative algorithm for solving the static shortest hyperpath problem when the dynamic problem degenerates to the static problem. It has the same complexity as Gallo's algorithm for a general hypergraph and lower complexity for simplicial complexes (a special class of hypergraphs whose hyperedge set is closed under the subset operation). We also point out that both proposed algorithms apply to directed hypergraphs with minor modifications in their implementation details.
A detailed time complexity analysis of these two algorithms is provided to demonstrate their performance in the worstcase change scenario. Using a random geometric hypergraph model and a real data set of a social network (Enron email data set), we study the average performance of these two algorithms in different scenarios and demonstrate the partition of the application space between these two algorithms. In the experiment with Enron email data set, the proposed algorithms successfully identified the most important actor in this social network using the closeness centrality metric.

C. Applications
Shortest path computations on hypergraphs can be applied to communication as well as social networks. An example application in wireless communications, in particular, for multihop wireless networks, is in opportunistic routing schemes such as ExOR [15], GeRaF [16], and MORE [17]. In such schemes, any receiver of a packet is eligible to forward the packet. Receivers typically execute a protocol amongst themselves to decide who should forward it. This naturally leads to a hypergraph model where a node and its neighbors form a hyperedge. The cost of each hyperedge can be defined based on the cardinality of the hyperedge to capture the success rate of forwarding (lower the cardinality, lesser the chance that at least one of the nodes successfully receives the packet) and the associated overhead (higher the cardinality, higher the energy consumption and the overhead in choosing the forwarding node). A shortest hyperpath from the source to the destination is thus a better route than merely the traditional shortest path. And as the network topology changes, a dynamic algorithm is required to maintain the shortest hyperpath.
In social networks, information (results, event reports, opinions, rumors, etc.) propagates through diverse communication means including direct links (e.g., gestures, optical, satcom, regular phone call), social media (e.g., Facebook, Twitter, blogs), mailing lists, and newsgroups. Such a network may be modeled as a hypergraph with the weight of a hyperedge reflecting the cost, credibility, and/or delay for disseminating information among all vertice of this hyperedge. In particular, the weight of a hyperedge can capture the unique effect on the information after it passes through a group of people. For instance, a result can be discussed by overlapping blog collaboration networks as it spreads, and often the discussion yields a better result than if it only spreads through individuals. The minimum cost information passing in social networks can thus be modelled as a shortest hyperpath problem.
Another potential application is that of finding the most important actor in a social network. Under a graph model of social networks, the relative importance of a vertex can be measured by its betweenness and closeness centrality indices. The former is defined based on the number of shortest paths that pass through this vertex, and the latter, the total weight of the shortest paths from this vertex to all the other vertices [18]. In a social network exhibiting hyper-relationships, between-ness and closeness centrality, based on the shortest hyperpaths, would be better indicators of the relative importance of each actor. In Sec. VII, we apply the proposed shortest hyperpath algorithms to the Enron email data set. We propose a weight function that leads to the successful identification of the CEO of Enron as the most important actor under the closeness centrality metric. The distance of each person in the data set to the CEO along the resulting shortest hyperpaths closely reflects the position of the person within the company.

II. BACKGROUND ON DYNAMIC SHORTEST PATH ALGORITHMS FOR GRAPHS
In this section, we present the basic ideas of the dynamic shortest path algorithms developed for graphs in [5]. Some basic techniques in updating and maintaining the shortest path tree will be borrowed in later sections when we develop dynamic shortest hyperpath algorithms.

A. Dynamic Shortest Path Problem
A change δ on a graph G = (V, E) corresponds to one edge modification. There are four types of changes: weight increase, weight decrease, edge insertion, and edge deletion. Weight increase and edge deletion can be similarly treated (with small differences in the required data structures which will be omitted for simplicity), so can weight decrease and edge insertion. The dynamic algorithms are thus presented only for weight increase and weight decrease.
Given a graph G, a source node s, and a sequence of changes C = {δ 1 , δ 2 , . . . , δ l } on G, the dynamic shortest path problem is to find the shortest paths from s to all nodes in each new graph after change δ i . In

B. Weight Decrease
Consider that the weight of edge (ǔ,v) decreases to w new . Without loss of generality, assume that . It is not difficult to see thatǔ will not be affected by this change. The dynamic algorithm starts with determining whetherv will be affected by simply checking the inequality If the inequality does not hold, then this edge with the decreased weight does not provide a shorter path forv; the algorithm ends and the shortest path tree remains unchanged. If the inequality holds, thenv is affected; its new shortest path from s must go through edge (ǔ,v) and D[v] reduces to D[ǔ] + w new . We putv in a priority queue 1 Q, and the rest of the procedure is similar to Dijkstra's algorithm: dequeue the node z with the minimum distance from Q, update the distances of its neighbors, update Q by inserting the new affected vertices among the neighbors to Q and update the ranks of others based on the updated distances. The procedure iterates until Q is empty. A pseudo code presentation of the basic steps is given below.
is not an edge in the shortest path tree, then none of the vertices will be affected, the shortest path tree remain unchanged. Otherwise, the descendants, and only the descendants of this edge in the shortest path tree may be affected. For these vertices, some of them will have increased distances, some of them will go through an alternative path with the same distance (but changed parent), while the rest will not be affected. In order to classify the vertices into these three categories, we introduce the coloring idea in Frigioni's algorithm [5]: remains the same.
It is not difficult to see that if a vertex v is white or pink, all its descendants in the shortest path tree are white; if v is red, all its descendants are either red or pink. Therefore the coloring procedure is clear: we first determine whetheř v is pink or red by checking whether there is an alternative shortest path with the same distance forv (note thatv cannot be white due to the weight change of edge (ǔ,v) that is on its current shortest path); if such a path exists, then we coloř v pink and the algorithm ends, otherwise we color it red and put all its children in a priority queue M . The procedure then iterates for each vertex in M according to an increasing order of the vertex distances.
After the coloring process, we only need to deal with the red vertices. For each red vertex z, we initialize its distance with the distance of the shortest path through one of its non-red neighbors and put z in another priority queue Q (if no nonred neighbor exists, we initialize it with ∞). After this, the procedure is similar to Step 2 in the Graph: Weight Decrease algorithm: at each iteration, we extract the vertex at the top of Q and update its neighbors and Q until Q is empty.
then z is pink 10 else z is red; Enqueue(M , all z's children) 11 end; end Step3.a (Initialize the distance vector for red vertices) 12 for each red vertex z do 13 if z has no nonred neighbor 14 let u be the best nonred neighbor of z 17 end; end; end Step3.b: Step2 of Graph: Weight Decrease The worst-case time complexity for one edge change (either weight decreasing or increasing) is O(|δ| log |δ| + δ ), where |δ| denotes the number of affected vertices and δ the total number of both affected vertices and affected edges.

III. DYNAMIC SHORTEST HYPERPATH PROBLEM
We introduce some basic concepts of hypergraph [1] and define the static and the dynamic shortest hyperpath problems. Some basic properties of the shortest hyperpaths are established and will be used in developing the dynamic algorithms in subsequent sections.

A. Hypergraph and Hyperpath
Let V be a finite set and E a family of subsets of V . If for all elements e i ∈ E, the following conditions are satisfied: In a hypergraph, a hyperpath is defined as follows. Definition 1: A hyperpath between two vertices u and v is a sequence of hyperedges {e 0 , e 1 , . . . , e m } such that u ∈ e 0 , v ∈ e m , and e i ∩ e i+1 = ∅ for i = 0, ..., m − 1. A hyperpath is simple if non-adjacent hyperedges in the path are nonoverlapping, i.e., e i ∩ e j = ∅, ∀j = i, i ± 1.
Let L e = {e 0 , . . . , e m } be a hyperpath in a weighted hypergraph H. We define the weight of L e as:

B. Shortest Hyperpath and Relationship Tree
Given two vertices u and v, a natural question is to find the shortest hyperpath (in terms of the path weight) from u to v. Since the weight function is nonnegative, it suffices to consider only simple hyperpaths. If the shortest hyperpath is not simple, we can always generate a simple hyperpath without increasing the weight by deleting all the hyperedges between two overlapping non-adjacent hyperedges.
The dynamic shortest hyperpath problem can be similarly defined for a sequence C = {δ 1 , δ 2 , . . . , δ l } of hyperedge changes. Hyperedge changes have the same four types as edge changes in a graph: weight increase, weight decrease, hyperedge insertion, and hyperedge deletion. Similarly, weight increase and hyperedge deletion will be treated together, so are weight decrease and hyperedge insertion.
In this paper, we consider the single-source shortest hyperpath problem: find the shortest hyperpaths from a given source s to all other vertices. The presentation of the paper focuses on undirected hypergraphs. However, the two proposed dynamic algorithms apply to directed hypergraphs with minor modifications in their implementation details.
Below, we establish a basic property of shortest hyperpaths. Lemma 1: Let L = {e 1 , e 2 , . . . , e l } be a shortest hyperpath from s ∈ e 1 to z ∈ e l . Then for any vertex v ∈ e i ∩ e i+1 , the hyperpath L v = {e 1 , e 2 , . . . , e i } is a shortest hyperpath from s to v. Furthermore, for any two vertices u, v ∈ e i ∩ e i+1 (if there exist at least two vertices in e i ∩ e i+1 ), Proof: We will prove by contradiction. Assume that Then consider the hyperpath L ′ = {e ′ 1 , e ′ 2 , . . . , e ′ k , e i+1 , e i+2 , . . . , e l }, we have w(L ′ ) < w(L) which contradicts the fact that L is a shortest hyperpath to z. This completes the proof for the first part of the lemma. Furthermore, for any two nodes u, v ∈ e i ∩e i+1 , since L v is the shortest hyperpath for both vertices, Next, we introduce the concept of relationship tree that is needed in the proposed dynamic shortest hyperpath algorithm HE-DSP. Since two adjacent hyperedges in a hyperpath may overlap at more than one vertex, the shortest hyperpaths from s to all other vertices do not generally form a tree in the original graph sense. For the development of the dynamic shortest hyperpath algorithms, we introduce the concept of relationship tree to indicate the parent-child relationship along shortest hyperpaths. The concept can be easily explained in the example given in Fig 2. Let {e 1 , e 2 } be a shortest hyperpath from s to v 4 . By Lemma 1, {e 1 } is a shortest hyperpath for both v 1 and v 2 . As illustrated in Fig 2, there are 4 possible relationship trees to indicate the parent-child relationship in these shortest hyperpaths. We will show in Sec. IV that the choice of the relationship tree does not affect the correctness or performance of the proposed algorithm HE-DSP.

IV. HYPEREDGE BASED DYNAMIC SHORTEST PATH ALGORITHM
In this section, we propose HE-DSP. It is an extension of the dynamic Dijkstra's algorithm to hypergraphs. The extension is more complex than Gallo's extension of the static Dijkstra's algorithm, since the dynamic Dijkstra's algorithm relies on the tree structure of the shortest paths, a structure no longer there for the shortest hyperpaths.

A. Hyperedge Weight Decrease
Consider that the weight of a hyperedgeě decreases to w new . Similar to the case for graphs, we know that the vertex x ∈ě with D[x] = min v∈ě {D[v]} will not be affected. We then check weather the other vertices ině are affected by checking the inequality given in (1), and put all the affected vertices into a priority queue Q. The rest of the procedure is similar to that for graphs, only when we update the distance of a vertex, we check all the hyperedges that contain this vertex.

HE-DSP: Weight Decrease
end Step2 (Iteratively enqueue and update affected vertices) 7 while

B. Hyperedge Weight Increase
The coloring process in the graph case relies on the tree structure of the shortest paths, which is no longer present in the shortest hyperpaths. Our solution is to use a relationship tree for the coloring process, and we prove the correctness of this approach regardless of the choice of the relationship tree.
Consider that the weight of a hyperedgeě increases to w new . First, we redefine the color of a vertex v based on the chosen relationship tree.
With the above modified definitions of colors, the same coloring process as in the graph case can be carried out using a relationship tree. The algorithm is given below. In this section, we propose DR-DSP. When the dynamic problem degenerates to the static problem, DR-DSP leads to an alternative algorithm for solving the static shortest hyperpath problem.

A. The Static Case: DR-SP
We first consider the static version of the algorithm (referred to as DR-SP), which captures the basic idea of dimension reduction.
The proposed DR-SP algorithm is based on the following theorem in which we show that for a general hypergraph H, the weight ω(L * ) of the shortest path L * of H is equal to the shortest path L * G of a weighted graph G derived from H. Specifically, corresponding to every hyperedge e in H, G contains a clique defined on the vertices of e.
Let L * and L * G be the shortest paths from u ∈ V to v ∈ V in H and G, respectively. Then we have that w(L * ) = w G (L * G ).
Proof: First, for each shortest path L * G in G, we can obtain a corresponding hyperpath L in H with the same weight based on (2), therefore we have that Then it suffices to show that there exists a path Assume that L * = {e 0 , e 1 , . . . , e k−1 } is a shortest hyperedge path from v 0 to v k in H where v 0 ∈ e 0 and v k ∈ e k−1 .
Let v i ∈ e i−1 ∩ e i (i = 1, 2, ..., k − 1) be one of the vertices in the intersection of hyperedges e i−1 and e i . Construct a path L G = {v 0 , v 1 , ..., v k } in the graph G. For each edgẽ Thus, i.e., w G (L G ) ≤ w(L * ). It follows from Theorem 3 that the shortest path in a general hypergraph can be obtained by applying Dijkstra's algorithm to the underlying graph G with weights modified as stated in the theorem.

B. The Dynamic Case: DR-DSP
In the dynamic case, a sequence C = {δ 1 , δ 2 , . . . , δ l } of hyperedge changes in the hypergraph H results in a sequence of edge changes in the underlying graph G. For each hyperedge change δ i , DR-DSP first updates the underlying graph G to locate all the changed edges caused by δ i . In the next step, DR-DSP updates the shortest path tree in the underlying graph G.
Consider first the graph update. A change to a hyperedge e only affects those edges in G that are subsets of e, i.e., a hyperedge change is localized in the underlying graph G. Furthermore, since the weight of an edge in G is the minimum weight of all hyperedges containing it, not all edges in G that are subsets of e will change weight. Based on these observations, we propose a special data structure and procedure for updating the underlying graph G without regenerating the graph from scratch using Step 1 of DR-SP.
At the initialization stage of the algorithm, a priority queue M uv for each pair of vertices (u, v) in the hypergraph is established to store the weights of all hyperedges that contain both u and v. When a change occurs to hyperedge e, all the priority queues M uv associated with the pair of vertices (u, v) that are contained in e are updated with the new weight of e. Thus, the top of these priority queues always maintain the weight for edge (u, v) in the underlying graph G for each (u, v). Below is a pseudo code implementation of the proposed procedure.
Graph Update(ě, w new ). After the underlying graph G is updated, we are now facing a dynamic shortest path problem in a graph. However, since a single hyperedge change can result in multiple edge changes in G, we need to handle a batch problem. While existing batch algorithms and iterative single-change algorithms for graphs can be directly applied here, we show that the batch problem we have at hand has two unique properties that can be exploited to improve the efficiency of the algorithm.
Property 1: The edge changes in G caused by a hyperedge change are either all weight decreases or all weight increases.
Property 2: All changed edges in G caused by a hyperedge change belong to a clique in G.

C. Hyperedge Weight Decrease
If the weight of hyperedgeě decreases to w new , by Theorem 3 and Property 1, there are (possibly) several edgeweight decreases in the underlying graph G. Therefore similar to HE-DSP, there is at least one unaffected node x = argmin v∈ě {D[v]}. By Property 2, these affected edges are contained in a clique derived from the changed hyperedge; therefore it is sufficient to determine the distance of every node v (other than x) in the original changed hyperedge e by checking D[x] + w new < D [v]. And we can initialize the priority queue with those nodes whose weight decreases. After that, the procedure is similar to that in the graph case.

VI. TIME COMPLEXITY ANALYSIS
We analyze the time complexity of the two proposed dynamic algorithms. We show that for different scenarios, each algorithm has its own advantage. We also consider the static case and show that the static version of DR-DSP has the same complexity as Gallo's algorithm for a general hypergraph and lower complexity for a simplicial complex.

A. The Static Shortest Hyperpath Problem
Therefore the time complexity for Step 1 is O(d2 d m). The total time complexity thus follows.

B. The Dynamic Shortest Hyperpath Problem
Given a hypergraph H = (V, E, w) and a change to hyperedge e, let |δ| denote the number of affected vertices, δ the number of affected hyperedges plus |δ|, |δ Φ | = e∈E,e is affected |e| 2 , and δ the number of affected edges in the underlying graph plus |δ|. For DR-DSP: Weight Decrease, the total time spent on Graph Update procedure is O(|e| 2 log m). In Step 2, there are |δ| iterations; in each iteration O(log |δ|) time is spent to dequeue z from M . Time spent on updating neighbors over all iterations is O( δ ). Therefore the total time complexity is O(|δ| log |δ|+ δ +|e| 2 log m). For DR-DSP: Weight Increase, Step 2, Step 3.a and Step 3.b take O(|δ| log |δ| + δ ) (similar to the analysis for graphs). The total time complexity thus follows.
From Theorem 5 we see that if δ is small and |e| is large, HE-DSP performs better, since in DR-DSP, the update of the underlying graph has to be done regardless whether there are affected vertices. Thus in a sequence of hyperedge changes, if only a small fraction of them actually have affected nodes, then HE-DSP will outperform DR-DSP. On the other hind, if δ is large, because usually |δ Φ | ≫ δ , then DR-DSP will outperform HE-DSP. Consider the extreme example where every valid hyperedge exists, all nodes are affected and the changed hyperedge contains n vertices. Then |δ| = n, |δ Φ | = O(n 2 2 n ), δ = O(n 2 ), |e| = n, m = O(2 n ). The time complexity of HE-DSP is O(n log n + n 2 2 n ) = O(n 2 2 n ) while the time complexity of DR-DSP is O(n 3 ). We see that the time complexity of DR-DSP can be much lower than that of HE-DSP.

VII. SIMULATION RESULTS
We present simulation results on the running time of the proposed dynamic shortest hyperpath algorithms. We test the proposed algorithms on hypergraphs generated from a random geometric model as well as those generated by the Enron email data set. All simulation code is compiled and run on the same laptop equipped with a 3.0GHz i7-920XM Mobile Processor.

A. Random Geometric Hypergraph
We first consider a random geometric hypergraph model in which n nodes are uniformly distributed in an a×a square. All nodes within a circle with radius r form a hyperedge (circles are centered on a h × h grid). The weight of each hyperedge is given by the average distance between all pairs of vertices of this hyperedge.
A sequence of changes are then generated and the proposed dynamic algorithms are employed to maintain all the shortest hyperpaths from the source s located at a corner of the a × a square. Each change can be a hyperedge insertion (with probability p I ), a hyperedge deletion (with probability p D ), or a weight change (with probability 1−p I −p D ) with new weight chosen uniformly in [w min , w max ]. In the case of a hyperedge deletion or a weight change, the hyperedge to be deleted or to be assigned with a new weight is chosen according to the two models detailed below. Hyperedge insertions are only realized when there are hyperedges that have been deleted, and a randomly chosen one is inserted back. This ensures that all hyperedges satisfy the geometric property determined by r at all time. It also models the practical scenario where a broken link is repaired.
In selecting a hyperedge for deletion or weight change, we consider two different models: the random change model and the targeted change model. In the former, the hyperedge is randomly and uniformly chosen among all hyperedges. In the latter, it is randomly and uniformly chosen from the current shortest hyperpaths. This models the scenarios where hyperedges in the shortest hyperpaths are more prone to changes due to attacks, frequent use, or higher priority in maintenance and upgrade.
In Fig. 3, we show the simulation results on the running time of the two proposed algorithms under a sequence of 10 4 changes. We see that HE-DSP has lower complexity in networks with random topological and weight changes (Fig. 3-Left), whereas DR-DSP should be preferred in networks with targeted changes (Fig. 3-Right). This partition of the application space can be explained from the structures of these two algorithms. Under the random change model, a large fraction of changes do not result in changes in the current shortest hyperpaths. Such changes lead to little computation in maintaining the shortest hyperpaths for both algorithms, but requires about the same amount of computation in the Graph-Update step of DR-DSP for maintaining the underlying graph. On the other hand, under the targeted change model, all hyperedge deletions and weight changes affect the shortest hyperpaths. Updating the shortest hyperpaths can be done more efficiently in DR-DSP since it works on the underlying graph with a much smaller number of edges.

B. Enron Email Data Set
In this example, we consider the application of the shortest hyperpath algorithms in finding the most important actor in a social network. We consider the Enron email data set and use the same hypergraph generation model as in [20]. Specifically, each person is a vertex of the hypergraph, and the sender and recipients of every email form a hyperedge. Our objective is to identify the most important person measured by the closeness centrality index (i.e., the total weight of the shortest hyperpaths from this person to all the other persons). The first step is to assign weight to each hyperedge that reflects "distance". While there is no universally accepted way of measuring distance in a social network observed through email exchanges, certain general rules apply. First, a direct email exchange between two persons indicates a stronger tie than an email sent to a large group. Thus, the weight of an hyperedge should be an increasing function of the cardinality of this hyperedge. Second, more frequent email exchange among a given group of people shows stronger ties. Thus, the weight of an hyperedge should be decreasing with the number of times that this hyperedge appears in the email data set. Considering these two general rules, we adopt the following weight function: where |e| is the cardinality of the hyperedge e, α is the parameter measuring how fast the weight decreases with the number l of times that this hyperedge appears in the data set. We can then apply DR-SP on the resulting (static) hypergraph to find the shortest hyperpaths rooted at each vertex and compute this vertex's closeness centrality index. With the weight function given in (3) using α = 0.6, the identified most important actor is the CEO of Enron. The average distance (along the shortest hyperpath) from the CEO to the other persons at various positions is shown in Fig. 4. We observe that in general, the higher the position, the shorter the distance. These results demonstrate that the adopted hypergraph model and weight function capture the essence of the problem.
Next, we construct a dynamic hypergraph sequence based on the Enron data set. At the beginning, the hypergraph contains only individual vertices. We then consider each email chronologically. Each email either adds a new hyperedge or decrease the weight of an existing hyperedge (due to the increased number of appearances of this hyperedge). The two proposed algorithms are employed to maintain the shortest hyperpaths rooted at the CEO after each change. The running time is given in Fig. 5, which shows the lower complexity of DR-DSP. The reason is that a large fraction of hyperedge changes result in changes in the shortest hyperpaths.

VIII. CONCLUSION
We have presented, to our best knowledge, the first study of the fully dynamic shortest path problem in a general hypergraph. We have developed two dynamic algorithms for finding and maintaining the shortest hyperpaths. These two algorithms complement each other with each one preferred in different types of hypergraphs and network dynamics, as illustrated in the time complexity analysis and simulation experiments. We have discussed and studied via experiments over a real data set the potential applications of the dynamic shortest hyperpath problem in social and communication networks.
The proof is based on the following three lemmas.
, which can be easily seen from the procedure of the algorithm).
We now prove the converse. Assume that Then u i+2 will be enqueued in Step 2 of the algorithm when u i+1 is dequeued if it has not been enqueued before that. Repeating this line of argument, we conclude that there exits u l ∈ e l−1 ∩ e l with d ′ [u l ] < d[u l ] and u l is enqueued into Q. Then v will be enqueued when u l is dequeued if it is not enqueued already. Then based on the fact that distances of the dequeued vertices are monotonically increasing with the order of the dequeueing as shown at the beginning of the proof, u cannot be any vertex dequeued after z l+1 . Since z l+1 ∈ě, it is also clear that u cannot be an unaffected vertex(otherwise, z l+1 will be unaffected, which contradicts Lemma 3). We thus have u ∈ {z 1 , . . . , z l }. Let u = z i . Then when z i is dequeued , D[z l+1 ] will be updated to the shortest distance d ′ [z l+1 ] due to the induction hypothesis of D[z i ] = d ′ [z i ]. This completes the proof. Based on Lemma 3 and 4, the shortest distances of all affected vertices will be updated correctly. Based on Lemma 3, all unaffected vertices will not be enqueued, and their distances remain the same. It is not difficulty to see from the algorithm that P [v] and E[v] are also correctly maintained for all v.

APPENDIX B: PROOF OF THEOREM 2
We first show the correctness of the coloring process as given in the following lemma.
Lemma 5: The coloring process correctly colors all the affected vertices.
Proof: We first state the following simple facts without proof: given a relationship tree, after the hyperedge weight increase, (1) if v is pink or white, then all its descendent in this relationship tree are white; (2) if a v is red, then all its children in the relationship tree are either pink or red; (3) if a v is affected, either v ∈ě or P [v] is red. These facts can be directly obtained from the definition of the color. It is also easy to see that vertices are dequeued from M in a nondecreasing order of their current distance D[·]. This is because each time a vertex z is dequeued from M , the possible new vertices to be enqueued into M are z's children with distances no smaller than D[z].
Then, the proof of the lemma has two parts: first we prove that all affected vertices are enqueued into M ; then we prove by induction that only affected vertices are enqueued into M and their colors are correctly identified.
We prove the first part by contradiction. Assume that there exists an affected vertex v that is not enqueued into M . It is easy to see that v ∈ě because all the affected vertices ině are enqueued in Step 1. Based on the third fact stated above, P [v] is red. Based on the hypothesis, P [v] is not enqueued (otherwise, v will be enqueued in Step 2). Continue this line of arguments, we eventually reach the root of the relationship tree and arrive at the contradiction that the source s is red.
We prove the second part by induction. It is easy to see that all the vertices initially enqueued into M are affected vertices. It remains to show that the first vertex z 1 dequeued from M is colored (pink or red) correctly. To show that, we need to establish that the algorithm correctly determines whether there is an alternative shortest hyperpath to z 1 with the same distance, i.e., d[z 1 ] = d ′ [z 1 ]. The key here is to show that checking the currently non-red neighbors (which may become red in the future) of z 1 will not lead to a false alternative path. This follows from the fact that z 1 has the smallest distance D[·] among all affected vertices (which belong to the set of vertices consisting of the affected vertices ině and their descendents).
Next, assume that vertices z 1 , z 2 , . . . , z l dequeued from M are all affected vertices and are correctly colored. Consider the next dequeued vertex z l+1 . It is an affected vertex because it is either enqueued in Step 1 with E[v] =ě or enqueued in Step 2 with a red parent. To show that z l+1 will be colored correctly, we use a similar argument by showing that the currently nonred neighbors of z l+1 will not give a false alternative path. The latter follows from the fact that all affected vertices will be enqueued and those dequeued after z l+1 have distances no smaller than D[z l+1 ]. This completes the induction.
We now show that D[v], P [v] and E[v] are correctly maintained for all v. For each red vertex v, its distance is set based on the current shortest distance from a non-red neighbor in Step 3.a. The rest of the algorithm is essentially Gallo's extension of Dijkastra's algorithm with the current initial distance. The correctness of the algorithm thus follows. It is not difficult to see that P [·] and E[·] are correctly updated for both red and pink vertices.