Title: Finding events in temporal networks: Segmentation meets densest-subgraph discovery,
Abstract: In this paper we study the problem of discovering a timeline of events in a
temporal network. We model events as dense subgraphs that occur within
intervals of network activity. We formulate the event-discovery task as an
optimization problem, where we search for a partition of the network timeline
into k non-overlapping intervals, such that the intervals span subgraphs with
maximum total density. The output is a sequence of dense subgraphs along with
corresponding time intervals, capturing the most interesting events during the
network lifetime.
A naive solution to our optimization problem has polynomial but prohibitively
high running time complexity. We adapt existing recent work on dynamic
densest-subgraph discovery and approximate dynamic programming to design a fast
approximation algorithm. Next, to ensure richer structure, we adjust the
problem formulation to encourage coverage of a larger set of nodes. This
problem is NP-hard even for static graphs. However, on static graphs a simple
greedy algorithm leads to approximate solution due to submodularity. We
extended this greedy approach for the case of temporal networks. However, the
approximation guarantee does not hold. Nevertheless, according to the
experiments, the algorithm finds good quality solutions.