Efficient Index Maintenance and Edge Influence Computation for Dynamic Graphs

Duration: 1.5 – 2 hours

Short Description: Since today’s real-world graphs, such as web graphs, 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 new/inactive users need to handle additional/failed links or nodes, dynamic computation and maintenance for graphs is considered a challenging problem. Shortest path computation and reachability computation are two of the most fundamental operations for managing and analyzing large graphs. Firstly, we focus on the problem of computing the shortest path distance in dynamic graphs, particularly on decremental updates (i.e., edge deletions), with the use of distance labeling techniques. We propose maintenance algorithms that can handle decremental updates efficiently. Then we would like to talk about handling graph reachability queries in dynamic graphs. Specifically we investigate the influence of a given edge in the graph, aiming to study the overall reachability changes in the graph brought by the possible failure/deletion of the edge. To this end, we firstly develop an efficient update algorithm for handling edge deletions. We then define the edge influence concept and put forward a novel computation algorithm to accelerate the computation of edge influence.


Louie Qin Dr. Yongrui Qin is currently a Lecturer in School of Computing and Engineering, University of Huddersfield, United Kingdom. His main research interests include Internet of Things, Graph Data Management, Data Stream Processing, Data Mining, Information Retrieval, Semantic Web, Computer Networks, and Mobile Computing. Dr. Qin has published more than 40 refereed technical papers, including publications in prestigious journals, such as ACM Computing Surveys, IEEE Trans. on Parallel Distributed Systems, World Wide Web Journal, Journal of Network and Computer Applications, and IEEE Internet Computing, as well as top international conferences, such as SIGIR, EDBT, CIKM, CAiSE, WISE, DASFAA, and SSDBM.