TY - JOUR
T1 - Finding events in temporal networks
T2 - segmentation meets densest subgraph discovery
AU - Rozenshtein, Polina
AU - Bonchi, Francesco
AU - Gionis, Aristides
AU - Sozio, Mauro
AU - Tatti, Nikolaj
N1 - | openaire: EC/H2020/654024/EU//SoBigData
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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 naïve solution to our optimization problem has polynomial but prohibitively high running time. 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; however, we show that on static graphs a simple greedy algorithm leads to approximate solution due to submodularity. We extend this greedy approach for temporal networks, but we lose the approximation guarantee in the process. Finally, we demonstrate empirically that our algorithms recover solutions with good quality.
AB - 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 naïve solution to our optimization problem has polynomial but prohibitively high running time. 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; however, we show that on static graphs a simple greedy algorithm leads to approximate solution due to submodularity. We extend this greedy approach for temporal networks, but we lose the approximation guarantee in the process. Finally, we demonstrate empirically that our algorithms recover solutions with good quality.
KW - Approximate algorithm
KW - Densest subgraph
KW - Dynamic programming
KW - Segmentation
UR - http://www.scopus.com/inward/record.url?scp=85074365079&partnerID=8YFLogxK
U2 - 10.1007/s10115-019-01403-9
DO - 10.1007/s10115-019-01403-9
M3 - Article
AN - SCOPUS:85074365079
SN - 0219-1377
JO - Knowledge and Information Systems
JF - Knowledge and Information Systems
ER -