Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach

Abstract

The increasing availability of temporal network data is calling for more research on extracting and characterizing mesoscopic structures in temporal networks and on relating such structure to specific functions or properties of the system. An outstanding challenge is the extension of the results achieved for static networks to time-varying networks, where the topological structure of the system and the temporal activity patterns of its components are intertwined. Here we investigate the use of a latent factor decomposition technique, non-negative tensor factorization, to extract the community-activity structure of temporal networks. The method is intrinsically temporal and allows to simultaneously identify communities and to track their activity over time. We represent the time-varying adjacency matrix of a temporal network as a three-way tensor and approximate this tensor as a sum of terms that can be interpreted as communities of nodes with an associated activity time series. We summarize known computational techniques for tensor decomposition and discuss some quality metrics that can be used to tune the complexity of the factorized representation. We subsequently apply tensor factorization to a temporal network for which a ground truth is available for both the community structure and the temporal activity patterns. The data we use describe the social interactions of students in a school, the associations between students and school classes, and the spatio-temporal trajectories of students over time. We show that non-negative tensor factorization is capable of recovering the class structure with high accuracy. In particular, the extracted tensor components can be validated either as known school classes, or in terms of correlated activity patterns, i.e., of spatial and temporal coincidences that are determined by the known school activity schedule.

References in corpus (6)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• Finding statistically significant communities in networks
• Dynamics of person-to-person interactions from distributed RFID sensor networks
• Robust Detection of Dynamic Community Structure in Networks
• Detecting Overlapping Temporal Community Structure in Time-Evolving Networks

Cited by in corpus (58)

• Multilayer Networks
• The physics of spreading processes in multilayer networks
• Modern temporal network theory: A colloquium
• Community Discovery in Dynamic Networks: a Survey
• What are higher-order networks?
• Fundamental structures of dynamic social networks
• Mitigation of infectious disease at school: targeted class closure vs school closure
• Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers
• Stream Graphs and Link Streams for the Modeling of Interactions over Time
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Multilayer Brain Networks
• Modeling sequences and temporal networks with dynamic community structures
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Effect of risk perception on epidemic spreading in temporal networks
• Compensating for population sampling in simulations of epidemic spread on temporal contact networks
• Mining (maximal) span-cores from temporal networks
• Constrained information flows in temporal networks reveal intermittent communities
• Sampling of Temporal Networks: Methods and Biases
• Multilayer Network Science: from Cells to Societies
• Community Detection in Quantum Complex Networks
• Relevance of temporal cores for epidemic spread in temporal networks
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Discovering and Characterizing Mobility Patterns in Urban Spaces: A Study of Manhattan Taxi Data
• Reciprocity, community detection, and link prediction in dynamic networks
• Community detection in directed acyclic graphs
• Community evolution in retweet networks
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• Community detection in multiplex networks using locally adaptive random walks
• Building surrogate temporal network data from observed backbones
• Infection patterns in simple and complex contagion processes on networks
• Temporal stability of network partitions
• Estimating the outcome of spreading processes on networks with incomplete information: a mesoscale approach
• Dynamic Hidden-Variable Network Models
• Information transfer in community structured multiplex networks
• Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread
• An embedding-based distance for temporal graphs
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Detecting periodic time scales in temporal networks
• The switching mechanisms of social network densification
• Temporal Clustering in Dynamic Networks with Tensor Decomposition
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications
• Extracting the multi-timescale activity patterns of online financial markets
• Temporal Network Embedding via Tensor Factorization
• The Atlas for the Aspiring Network Scientist
• Dynamic Graph Metrics: Tutorial, Toolbox, and Tale
• Duality between Temporal Networks and Signals: Extraction of the Temporal Network Structures
• Exact rank-reduction of network models
• Span-core Decomposition for Temporal Networks: Algorithms and Applications
• Fast Approximate Spectral Clustering for Dynamic Networks
• Detecting multi-timescale consumption patterns from receipt data: A non-negative tensor factorization approach
• Constant State of Change: Engagement Inequality in Temporal Dynamic Networks
• weg2vec: Event embedding for temporal networks
• Size Agnostic Change Point Detection Framework for Evolving Networks
• Automatic Dimension Selection for a Non-negative Factorization Approach to Clustering Multiple Random Graphs
• Skeleton coupling: a novel interlayer mapping of community evolution in temporal networks
• Techniques for clustering interaction data as a collection of graphs
• Spatio-Temporal Tensor Sketching via Adaptive Sampling
• Convex Optimization For Non-Convex Problems via Column Generation