Efficient Algorithms for Truss Maintenance over Large Dynamic Graphs

Graphs are widely used to model entities and their connections in various real-life domains, such as social networks, communication systems, biological databases, and transportation networks, to name a few. Among many graph analytics tasks, truss identification, which finds dense subgraphs
in which every edge has at least k-2 triangles, has wide applications such as community search, the acceleration of clique discovery, and the visualization of complex networks.

However, most of the existing works on truss identification are confined to static and deterministic graphs, which is not enough, as many real graphs undergo frequent and complex updates. For instance, in a social network, users may add/delete friends (referred to as edge insertion/deletion)
and even close the account forever (referred to as vertex deletion). Even worse, the graph connections might be uncertain, due to the noisy measurements, prediction learning models, or for privacy considerations. In a communication network, two mobile devices may have an unstable
connection when they go through tunnels (i.e., the cellphone connection may be broken with a probability; referred to as uncertainty). However, there is no previous work on truss maintenance with dynamic uncertainties. Therefore, it is important to efficiently maintain the trussness for
various updates over dynamic graphs. Moreover, when graph updates can be operated by the network owners/attackers, another maintenance task of truss manipulation by adding new edges on purpose becomes practically useful. For example, improving route connectivity by adding new
airlines in a flight network, is of interest to carrier operators, airports, and regional governments.

In this project, we intend to comprehensively investigate truss maintenance over dynamic graphs, leveraging the development of new models, efficient algorithms, and practical applications. Specifically, we plan to study the following tasks: 1) deterministic truss maintenance over evolving
graphs where the graph is updated with vertex/edge insertions/deletions; 2) probabilistic truss maintenance with dynamic uncertainties; 3) budget-constrained truss manipulation by inserting a given number of new edges; and 4) evaluation of the proposed techniques on a variety of real
data, in order to develop prototype systems. With our extensive research experience in the field of uncertain and dynamic graph analytics, the outcomes of this project are expected to lead to new models and tools for truss maintenance over dynamic and large graphs, thereby benefiting the graph
analytics industry.