Methods for analyzing temporal networks

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2018-11-09

Date

2018

Major/Subject

Mcode

Degree programme

Language

en

Pages

83 + app. 113

Series

Aalto University publication series DOCTORAL DISSERTATIONS, 192/2018

Abstract

In this thesis we study networks with a temporal component. We use the interaction-network model to preserve the exact timestamp, and possibly other information, regarding each interaction between the nodes. In this model we study summarization, event detection, centrality measures, and infection spreading in temporal networks. First, we propose a novel generalization of PageRank centrality measure, which produces realistic centrality estimates with respect to a history of interactions. It captures the temporal changes in the distribution of interactions. We show that if the distribution remains stable, temporal PageRank converges to static PageRank. Second, we consider the problem of reconstructing an activity propagation in an interaction network. We show that with access to a small noisy set of reported infections we can reconstruct the epidemic spread over time without any assumptions on the propagation model.Next, we consider two event-detection problems. In the first one we propose a novel model for topically- and temporally-coherent events in social networks. We use textual information and define events to be sets of interactions that are topically close and form a directed tree of information flow. In addition, we address and solve the problem of discovering top-k events. In the second event-detection problem we aggregate node activity over fixed time intervals. Given a graph snapshot we then define an event to be a set of nodes, which is compact in the graph and has high total activity. We represent compactness in two ways: by total distance between nodes and by minimum spanning tree. To discover snapshots with prominent events in real-world interaction networks we apply greedy heuristic to sweep through the sequence of snapshots. Summarization covers a wide range of problems. Here we study summarization from two different points of view. First, we formulate a novel problem to explain and summarize all interactions in the interaction network by identifying activity intervals of the nodes. We consider two variants of the summarization problem: minimization of the total length of activity intervals and minimization of the maximum interval length. Second, we consider a novel problem of discovering a set of nodes, which forms a dense subgraph and whose interactions occur in short time intervals. This formulation provides an accurate representation of dense overlapping communities and their dynamics over the network history. For all proposed novel problems we present complexity analysis, develop novel or adapt existing algorithms, and prove quality guarantees. The algorithms are thoroughly evaluated on synthetic and real-world datasets and compared against baselines.

Description

Supervising professor

Gionis, Aristides, Prof., Aalto University, Department of Computer Science, Finland

Thesis advisor

Tatti, Nikolaj, Dr., F-secure Corp., Finland

Keywords

networks, temporal component

Other note

Parts

  • [Publication 1]: P. Rozenshtein, A. Anagnostopoulos, A. Gionis, N. Tatti. Event detection in activity networks. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, USA, pp. 1176-1185, August 2014.
    DOI: 10.1145/2623330.2623674 View at publisher
  • [Publication 2]: P. Rozenshtein, A.Gionis, B.A. Prakash, J. Vreeken. Reconstructing an epidemic over time. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, pp. 1835-1844, August 2016.
    DOI: 10.1145/2939672.2939865 View at publisher
  • [Publication 3]: P. Rozenshtein, A. Gionis. Temporal pagerank. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Riva del Garda, Italy, pp. 674-689, September 2016.
    DOI: 10.1007/978-3-319-46227-1_42 View at publisher
  • [Publication 4]: H. Xiao, P. Rozenshtein, A. Gionis. Discovering Topically- and Temporally-Coherent Events in Interaction Networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Riva del Garda, Italy, pp. 690-705, September 2016.
    DOI: 10.1007/978-3-319-46227-1_43 View at publisher
  • [Publication 5]: P. Rozenshtein, N. Tatti, A. Gionis. Finding dynamic dense subgraphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 11.3, p. 27, March 2017.
    DOI: 10.1145/3046791 View at publisher
  • [Publication 6]: P. Rozenshtein, N. Tatti, A. Gionis. The network-untangling problem: From interactions to activity timelines. In Joint European Conference on Machine Learning and Knowledge Discovery in Database, Skopje, Macedonia, pp. 701-716, September 2017.
    DOI: 10.1007/978-3-319-71249-9_42 View at publisher
  • [Errata file]: Errata in publication 1, 2 and 6

Citation