Abstract
In this thesis we study networks with a temporal component. We use the interactionnetwork 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 eventdetection problems. In the first one we propose a novel model for topically and temporallycoherent 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 topk events. In the second eventdetection 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 realworld 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 realworld datasets and compared against baselines.
Translated title of the contribution  Methods for analyzing temporal networks 

Original language  English 
Qualification  Doctor's degree 
Awarding Institution 

Supervisors/Advisors 

Publisher  
Print ISBNs  9789526082165 
Electronic ISBNs  9789526082172 
Publication status  Published  2018 
MoE publication type  G5 Doctoral dissertation (article) 
Keywords
 networks
 temporal component
Cite this
Rozenshtein, P. (2018). Methods for analyzing temporal networks. Aalto University. http://urn.fi/URN:ISBN:9789526082172