Integrating Temporal Graphs via Dual Networks: Dense Graph Discovery

Interactions among objects are usually modelled using graphs. Nevertheless, these relations may change over time and there exist different kind of relations among object that need to be integrated. We introduce a new network model, called temporal dual networks, to deal with interactions that changes over time and to integrate information coming from two different networks. We consider a fundamental problem in graph mining, that is finding densest subgraphs on this new model. We propose an approach based on both network alignment and dynamic programming. Given two temporal graphs, we obtain a dual temporal graph via alignment and then we look for densest subgraphs in the obtained graph. We present a dynamic programming algorithm to solve the problem in polynomial time. Since this algorithm is not applicable even to medium size network, we present a heuristic that is based on (1) constraining the dynamic programming to consider only bounded temporal graphs and (2) a local search procedure. We show that our method is able to return optimal or near optimal solution even for temporal graphs having 10,000 vertices and 10,000 timestamps.