Anytime search in dynamic graphs

Agents operating in the real world often have limited time available for planning their next actions. Producing optimal plans is infeasible in these scenarios. Instead, agents must be satisfied with the best plans they can generate within the time available. One class of planners well-suited to this task are anytime planners, which quickly find an initial, highly suboptimal plan, and then improve this plan until time runs out.A second challenge associated with planning in the real world is that models are usually imperfect and environments are often dynamic. Thus, agents need to update their models and consequently plans over time. Incremental planners, which make use of the results of previous planning efforts to generate a new plan, can substantially speed up each planning episode in such cases.In this paper, we present an A^∗-based anytime search algorithm that produces significantly better solutions than current approaches, while also providing suboptimality bounds on the quality of the solution at any point in time. We also present an extension of this algorithm that is both anytime and incremental. This extension improves its current solution while deliberation time allows and is able to incrementally repair its solution when changes to the world model occur. We provide a number of theoretical and experimental results and demonstrate the effectiveness of the approaches in a robot navigation domain involving two physical systems. We believe that the simplicity, theoretical properties, and generality of the presented methods make them well suited to a range of search problems involving dynamic graphs.     

Behavioral clusters in dynamic graphs

This paper contributes a method for combining sparse parallel graph algorithms with dense parallel linear algebra algorithms in order to understand dynamic graphs including the temporal behavior of vertices. Our method is the first to cluster vertices in a dynamic graph based on arbitrary temporal behaviors. In order to successfully implement this method, we develop a feature based pipeline for dynamic graphs and apply Nonnegative Matrix Factorization (NMF) to these features. We demonstrate these steps with a sample of the Twitter mentions graph as well as a CAIDA network traffic graph. We contribute and analyze a parallel NMF algorithm presenting both theoretical and empirical studies of performance. This work can be leveraged by graph/network analysts to understand the temporal behavior cluster structure and segmentation structure of dynamic graphs.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Parsimonious flooding in dynamic graphs

An edge-Markovian process with birth-rate p and death-rate q generates infinite sequences of graphs (G ₀, G ₁, G ₂,…) with the same node set [n] such that G _t is obtained from G _t-1 as follows: if e ? E(G_t-1){e\notin E(G_{t-1})} then e ? E(G_t){e\in E(G_{t})} with probability p, and if e ? E(G_t-1){e\in E(G_{t-1})} then e ? E(G_t){e\notin E(G_{t})} with probability q. In this paper, we establish tight bounds on the complexity of flooding in edge-Markovian graphs, where flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t′ > t. These bounds complete previous results obtained by Clementi et al. Moreover, we also show that flooding in dynamic graphs can be implemented in a parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time. For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ? [n]{s\in [n]} , the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that it is even constant whenever the ratio p/(p + q) exceeds log n/n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs.     

Detecting dynamic patterns in dynamic graphs using subgraph isomorphism

Pattern Analysis and Applications - Graphs have been used in different fields of research for performing structural analysis of various systems. In order to compare the structure of two systems,...     

Adjacency queries in dynamic sparse graphs

We deal with the problem of maintaining a dynamic graph so that queries of the form “is there an edge between u and v?” are processed fast. We consider graphs of bounded arboricity, i.e., graphs with no dense subgraphs, like, for example, planar graphs. Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representations of sparse graphs, in: Proc. 6th Internat. Workshop on Algorithms and Data Structures (WADS'99), in: Lecture Notes in Comput. Sci., vol. 1663, Springer, Berlin, 1999, pp. 342-351] described a very simple linear-size data structure which processes queries in constant worst-case time and performs insertions and deletions in O(1) and O(logn) amortized time, respectively. We show a complementary result that their data structure can be used to get O(logn) worst-case time for query, O(1) amortized time for insertions and O(1) worst-case time for deletions. Moreover, our analysis shows that by combining the data structure of Brodal and Fagerberg with efficient dictionaries one gets O(logloglogn) worst-case time bound for queries and deletions and O(logloglogn) amortized time for insertions, with size of the data structure still linear. This last result holds even for graphs of arboricity bounded by O(logkn), for some constant k.     

Shortest paths on dynamic graphs

Among the variants of the well-known shortest path problem, those that refer to dynamically changing graphs are theoretically interesting, as well as computationally challenging. Application-wise, there is an industrial need for computing point-to-point shortest paths on large-scale road networks whose arcs are weighted with a travelling time that depends on traffic conditions. We survey recent techniques for dynamic graph weights as well as dynamic graph topology.     

Improving query performance on dynamic graphs

Software and Systems Modeling - Querying large models efficiently often imposes high demands on system resources such as memory, processing time, disk access or network latency. The situation...     

Ranking weighted clustering coefficient in large dynamic graphs

Efficiently searching top-k representative vertices is crucial for understanding the structure of large dynamic graphs. Recent studies show that communities formed by a vertex with high local clustering coefficient and its neighbours can achieve enhanced information propagation speed as well as disease transmission speed. However, local clustering coefficient, which measures the cliquishness of a vertex in its local neighbourhood, prefers vertices with small degrees. To remedy this issue, in this paper we propose a new ranking measure, weighted clustering coefficient (WCC) of vertices, by integrating both local clustering coefficient and degree. WCC not only inherits the properties of local clustering coefficient but also approximately measures the density (i.e., average degree) of its neighbourhood subgraph. Thus, vertices with higher WCC are more likely to be representative. We study efficiently computing and monitoring top-k representative vertices based on WCC over large dynamic graphs. To reduce the search space, we propose a series of heuristic upper bounds for WCC to prune a large portion of disqualifying vertices from the search space. We also develop an approximation algorithm by utilizing Flajolet-Martin sketch to trade acceptable accuracy for enhanced efficiency. An efficient incremental algorithm dealing with frequent updates in dynamic graphs is explored as well. Extensive experimental results on a variety of real-life graph datasets demonstrate the efficiency and effectiveness of our approaches.     

Flooding in dynamic graphs with arbitrary degree sequence

This paper addresses the flooding problem in dynamic graphs, where flooding is the basic mechanism in which every node becoming aware of a piece of information at step t$t$ forwards this information to all its neighbors at all forthcoming steps t^′>t$t^{\prime }>t$. We show that a technique developed in a previous paper, for analyzing flooding in a Markovian sequence of Erdös–Rényi graphs, is robust enough to be used also in different contexts. We establish this fact by analyzing flooding in a sequence of graphs drawn independently at random according to a model of random graphs with given expected degree sequence. In the prominent case of power-law degree distributions, we prove that flooding takes almost surely O(logn)$O(logn)$ steps even if, almost surely, none of the graphs in the sequence is connected. In the general case of graphs with an arbitrary degree sequence, we prove several upper bounds on the flooding time, which depend on specific properties of the degree sequence.     

Debugging hardware designs using dynamic dependency graphs

Debugging is a time consuming task in hardware design. In this paper a new debugging approach based on the analysis of dynamic dependency graphs is presented. Powerful techniques for software debugging, including reverse debugging, dynamic forward and backward slicing, and spectrum-based fault localization are combined and adapted for hardware designs. A case study on designs with multiple faults approved the power of the proposed debugging methodology reducing the debugging time to 50% in comparison to conventional techniques.     

Generalized core maintenance of dynamic bipartite graphs

Data Mining and Knowledge Discovery - k-core is important in many graph mining applications, such as community detection and clique finding. As one generalized concept of k-core,...     

Enhancing the spreading of quantum walks on star graphs by additional bonds

We study the dynamics of continuous-time quantum walks (CTQW) on networks with highly degenerate eigenvalue spectra of the corresponding connectivity matrices. In particular, we consider the two cases of a star graph and of a complete graph, both having one highly degenerate eigenvalue, while displaying different topologies. While the CTQW spreading over the network??in terms of the average probability to return or to stay at an initially excited node??is in both cases very slow, also when compared to the corresponding classical continuous-time random walk (CTRW), we show how the spreading is enhanced by randomly adding bonds to the star graph or removing bonds from the complete graph. Then, the spreading of the excitations may become very fast, even outperforming the corresponding CTRW. Our numerical results suggest that the maximal spreading is reached halfway between the star graph and the complete graph. We further show how this disorder-enhanced spreading is related to the networks?? eigenvalues.     

On State-dependent dynamic graphs and their controllability properties

We consider distributed dynamic systems operating over a graph or a network. The geometry of the network is assumed to be a function of the underling system's states-giving it a unique dynamic character. Certain aspects of the resulting abstract structure, having a mixture of combinatorial and system theoretic features, are then studied. In this venue, we will explore an interplay between notions from extremal graph theory and system theory by considering a controllability framework for such state-dependent dynamic graphs.     

Speeding up dynamic transitive closure for bounded degree graphs

In this paper we present an algorithm for solving two problems in dynamically maintaining the transitive closure of a digraph: In the first problem a sequence of edge insertions is performed on an initially empty graph, interspersed withp transitive closure queries of the form: is there a path froma tob in the graph. Our algorithm solves this problem in timeO (dm ^*+p), whered is the maximum outdegree of the resulting graphG andm ^* is the number of edges in the transitive closure ofG. In the second problem, a sequence of edge deletions is performed on anacyclic graph, interspersed withp transitive closure queries. Once again we solve this problem in timeO (dm ^*+p), whered is the maximum outdegree of the initial graphG andm ^* is the number of edges in the transitive closure ofG. For bounded degree graphs, this improves upon previous results. Our algorithms also work when insertions and deletions to the graph are intermixed. Finally, we show how to implement the operation findpath (x, y) which retrieves some path fromx toy in time proportional to the length of the path.     

改进的动态图社区演化关系分析方法

传统基于相邻时间片分析所获得的社区演化关系无法完备地刻画动态图社区演化的整个过程。为此提出了一种改进的社区演化关系分析方法。首先,定义社区事件,并根据发生的社区事件来描述社区的演化状态;然后,对两个不相同时间片内的社区进行事件匹配,从而获得社区演化关系;最后,通过实验将所提方法与传统方法进行比较。实验结果表明,所提方法发现的社区事件总数是传统方法的2倍以上,可为动态图社区演化过程的描述提供更丰富的信息。     

Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

Efficient computation of distance labeling for decremental updates in large dynamic graphs

Since today’s real-world graphs, such as social network graphs, are evolving all the time, it is of great importance to perform graph computations and analysis in these dynamic graphs. Due to the fact that many applications such as social network link analysis with the existence of inactive users need to handle failed links or nodes, decremental computation and maintenance for graphs is considered a challenging problem. Shortest path computation is one of the most fundamental operations for managing and analyzing large graphs. A number of indexing methods have been proposed to answer distance queries in static graphs. Unfortunately, there is little work on answering such queries for dynamic graphs. In this paper, we focus on the problem of computing the shortest path distance in dynamic graphs, particularly on decremental updates (i.e., edge deletions). We propose maintenance algorithms based on distance labeling, which can handle decremental updates efficiently. By exploiting properties of distance labeling in original graphs, we are able to efficiently maintain distance labeling for new graphs. We experimentally evaluate our algorithms using eleven real-world large graphs and confirm the effectiveness and efficiency of our approach. More specifically, our method can speed up index re-computation by up to an order of magnitude compared with the state-of-the-art method, Pruned Landmark Labeling (PLL).     

数据驱动的突发疫情传染扩散参数动态更新策略

在对各类重大突发疫情进行建模拟合时,参数取值一直是困扰众多学者的重要现实难题,现有研究大多参考相关文献或结合医学实验选取某一固定参数.为克服这种固定参数取值的局限性,基于数据驱动的逆向思维,借助欧拉差分变换和线性方程组解的特性,构建一种疫情传染扩散参数动态更新策略,可以帮助决策者结合疫情实时更新的状态数据,反推计算最佳的疫情传播扩散参数.以武汉新冠肺炎疫情相关数据进行算例测试,结果表明,结合所设计的参数动态更新策略,能够有效地提升重大突发疫情演化预测的准确性,这对于政府应急资源的精准配置具有重要的决策支持作用.