Methods for analyzing temporal networks
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.advisor | Tatti, Nikolaj, Dr., F-secure Corp., Finland | |
| dc.contributor.author | Rozenshtein, Polina | |
| dc.contributor.department | Tietotekniikan laitos | fi |
| dc.contributor.department | Department of Computer Science | en |
| dc.contributor.lab | Data-mining group | en |
| dc.contributor.school | Perustieteiden korkeakoulu | fi |
| dc.contributor.school | School of Science | en |
| dc.contributor.supervisor | Gionis, Aristides, Prof., Aalto University, Department of Computer Science, Finland | |
| dc.date.accessioned | 2018-09-29T09:02:59Z | |
| dc.date.available | 2018-09-29T09:02:59Z | |
| dc.date.defence | 2018-11-09 | |
| dc.date.issued | 2018 | |
| dc.description.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. | en |
| dc.format.extent | 83 + app. 113 | |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.isbn | 978-952-60-8217-2 (electronic) | |
| dc.identifier.isbn | 978-952-60-8216-5 (printed) | |
| dc.identifier.issn | 1799-4942 (electronic) | |
| dc.identifier.issn | 1799-4934 (printed) | |
| dc.identifier.issn | 1799-4934 (ISSN-L) | |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/34089 | |
| dc.identifier.urn | URN:ISBN:978-952-60-8217-2 | |
| dc.language.iso | en | en |
| dc.opn | Akoglu, Leman, Asst. Prof., H. John Heinz III College Carnegie Mellon University, USA | |
| dc.publisher | Aalto University | en |
| dc.publisher | Aalto-yliopisto | fi |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [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 | |
| dc.relation.haspart | [Errata file]: Errata in publication 1, 2 and 6 | |
| dc.relation.ispartofseries | Aalto University publication series DOCTORAL DISSERTATIONS | en |
| dc.relation.ispartofseries | 192/2018 | |
| dc.rev | Pitoura, Evaggelia, Prof., University of Ioannina, Greece | |
| dc.rev | Bogdanov, Petko, Asst. Prof., University at Albany, USA | |
| dc.subject.keyword | networks | en |
| dc.subject.keyword | temporal component | en |
| dc.subject.other | Computer science | en |
| dc.title | Methods for analyzing temporal networks | en |
| dc.type | G5 Artikkeliväitöskirja | fi |
| dc.type.dcmitype | text | en |
| dc.type.ontasot | Doctoral dissertation (article-based) | en |
| dc.type.ontasot | Väitöskirja (artikkeli) | fi |
| local.aalto.acrisexportstatus | checked | |
| local.aalto.archive | yes | |
| local.aalto.formfolder | 2018_09_28_klo_13_06 |
Files
Original bundle
1 - 2 of 2
No Thumbnail Available
- Name:
- isbn9789526082172.pdf
- Size:
- 2.37 MB
- Format:
- Adobe Portable Document Format
No Thumbnail Available
- Name:
- Errata_rozenshtein_polina_DD_192_2018_publications_P1_P2_P6.pdf
- Size:
- 109.98 KB
- Format:
- Adobe Portable Document Format
- Description:
- Errata Polina Rozenshtein DD-192/2018 Publications P1, P2 and P6
