Methods for analyzing temporal networks
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2018-11-09
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
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, FinlandThesis advisor
Tatti, Nikolaj, Dr., F-secure Corp., FinlandKeywords
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