Source-linked AI summary
Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
Laetitia Gauvin, André Panisson, Ciro Cattuto
TL;DR
Temporal networks intertwine changing topology with time-dependent activity, creating a challenge for methods developed for static community structure. The paper applies non-negative tensor factorization to a three-way representation of temporal adjacency data, simultaneously extracting communities and activity patterns, and recovers known school classes and schedule-determined correlated activities. Its temporal axis is treated as unordered, so the method captures global correlations but does not exploit known temporal continuity.
Problem
Temporal-network community structure and correlated activity patterns require principled methods that preserve their intertwined temporal and topological organization.
Method
Non-negative tensor factorization decomposes a three-way tensor of temporal adjacency matrices into components representing network communities and associated activity patterns.
Results
The method fully recovers known school classes and their activity patterns, while identifying mixed-class communities validated through spatio-temporal metadata and scheduled social activities.
Takeaways & Limitations
Extracted components can be validated either as known classes or as correlated spatial and temporal activity patterns determined by the school schedule.
Takeaways & Limitations
Because the temporal axis is not constrained by continuity, the method cannot exploit known temporal continuity and may require separate factorizations to expose nested community structures.
Abstract
from arXiv · showhide
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.
Introduction
Temporal networks require methods that preserve evolving structure and activity patterns rather than relying only on aggregated representations. The paper proposes an intrinsically temporal tensor-factorization approach that simultaneously detects communities and tracks their activity, validating it on school data with known structure.
- Aggregating temporal networks into static representations can overlook essential features or confound structures separable only in time.
- Discontinuous activity patterns and abrupt structure formation challenge snapshot-based methods that assume continuity between successive community structures.
- Non-negative tensor factorization represents time-varying adjacency matrices as a three-way tensor to identify communities and track their activity simultaneously.
- The method is validated on a school interaction network with independently known class structure and temporal activity patterns.
- The factorization fully recovers the school’s known class structure and activity patterns, while also detecting mixed-class communities linked to social activities in public spaces.
Materials and Methods
The study applies non-negative tensor factorization to high-resolution temporal school-interaction data, using known class labels and activity schedules for validation. The method represents temporal structure through component memberships and time-varying activity while controlling decomposition complexity and capturing overlapping or temporally discontinuous structures.
- Empirical temporal network data: Wearable proximity sensors recorded close-range face-to-face interactions among 241 children, 10 teachers, and 10 classes over two school days.Each participant carried a uniquely identified badge, and contacts were timestamped and logged.
- Empirical temporal network data: The dataset provides ground truth for community membership through participant-to-class associations and supports spatial trajectories from receiver-based location fingerprints.Fifteen receivers provide room-level spatial information aggregated over one-minute intervals.
- Temporal aggregation: The two-day interaction stream was aggregated into S = 150 consecutive network snapshots of approximately 13 minutes, with alternative interval lengths used to assess robustness.The raw temporal resolution was 20 seconds, while class activity schedules were defined more coarsely.
- Tensor factorization: The temporal network tensor T ∈ R^N×N×S encodes topology and time, and canonical factorization represents it through lower-dimensional factors and sums of rank-1 outer products.The factor matrices organize node and temporal vectors into components corresponding to latent structures.
- Model complexity and validation: The number of components R balances underfitting against overfitting, so core consistency and related quality indicators assess decomposition quality rather than impose one universally optimal R.The reported community structures and activity patterns were robust to changing R, with most components remaining stable.
- Interpretation and scope: Non-negative factorization permits nodes to belong to multiple components and can identify components with temporally disjoint activity because it imposes no temporal-continuity constraint.This enables overlapping communities and purely structural temporal patterns.
Results
Non-negative tensor factorization recovered the school’s class communities and their temporal activity patterns, while also identifying mixed-class components linked to scheduled social gatherings. At R = 13, the decomposition matched nearly all known classes and aligned non-class activity with independently known spatio-temporal events.
- Community structure: The component-node matrix revealed 10 mutually disjoint communities plus three overlapping components mixing members of 2 to 7 classes.Most nodes belonged to at least one community: 234 of 241 students and teachers.
- Activity patterns: Class-related components peaked during class periods and dipped at lunch, whereas overlapping components peaked during lunch and exhibited distinct activity patterns.Activity profiles were computed by combining factors C and A; the figure shows the first school day.
- Class recovery: As R increased, matched classes reached all 10 known school classes at R = 12, despite the strict single-nonzero Jaccard matching criterion.When matched, class attribution was reported as almost perfect, and smaller R values produced fewer or mixed-class communities rather than partial classes.
- Class recovery: At R = 13, nine components perfectly matched nine classes, while the remaining matched class missed one student out of more than 20.The class-related components were marked as “class” in Figure 6.
- Spatio-temporal validation: The three non-class components corresponded to multi-class social activities whose inferred times, participating classes, and locations matched the independent school schedule.Their activity peaks temporally matched co-location spikes in social spaces such as the cafeteria and playground.
- Comparison with static methods: On the time-aggregated network, tensor factorization performed in line with static community-detection algorithms; Infomap and Community Walktrap each yielded an exact match.Aggregation weights represented the total number of active time intervals for each link.
Discussion
The study applies non-negative tensor factorization to recover temporal communities and their activity patterns in a school network with independently known structure and schedules. It finds that the method recovers school classes and interpretable cross-class social gatherings, while also identifying important scope limitations and extensions.
- Method: The method simultaneously identifies network communities and their activity patterns over time from temporal network data.It is intrinsically temporal and is evaluated on a school network with ground truth for both community structure and activity schedules.
- Findings: The factorization fully recovers known school classes and class activity patterns, while also finding communities spanning multiple classes.The mixed-class components are validated using spatio-temporal metadata and linked to known social activities in school public spaces.
- Method: Non-negative tensor factorization naturally represents time-varying topology and can produce overlapping communities with correlated link-activity patterns.Nodes may belong to multiple components, with membership represented through component weights.
- Limitations: The approach does not exploit temporal continuity, limiting its usefulness when continuity is relevant, although it can capture global temporal correlations.Incorporating continuity could improve robustness with noisy or missing data.
- Limitations: Hierarchical or nested community structures require multiple factorizations and separate correspondence or hierarchy analysis between components.This adds an additional analysis step beyond computing a single tensor decomposition.
- Extensions: Proposed extensions include directed and weighted temporal networks, incremental factorization for changing populations, and multiplex networks.Multiplex layers can replace the temporal dimension in the three-way tensor representation.
- Future needs: Benchmark datasets with known synthetic structures and empirical temporal networks with ground truth are identified as important for advancing method evaluation.The paper emphasizes the need for systematic characterization of temporal community-detection methods.
Supplementary information
The supplementary material documents the school-contact dataset, tensor-factorization setup, component diagnostics, aggregation-interval tests, and comparisons with static-network algorithms. Across tested intervals, the detected school-class structure remains robust, while some static methods merge classes.
- Factorization setup: The factorization uses 13 components on a temporal contact tensor, with node memberships represented in A and component activity over time represented in C.Component sizes are summarized after binary classification of nodes by membership weights.
- Component number: Smaller component counts generally produce larger detected communities than R = 13, as shown by component-node matrices with a fixed node order.The supplementary analysis assesses consistency of the detected structure across different values of R.
- Membership diagnostics: For R = 13, many nodes have zero membership weight across components, producing concentrated membership-weight distributions and ranked weight profiles.The distributions are shown using natural logarithms of the weights.
- Aggregation duration: Using aggregation intervals of 5, 15, 30, and 60 minutes with R = 13, all school classes are recovered and score values remain very close across intervals.The results therefore appear robust over this tested range, although the 13-minute interval used in the main text is described as somewhat arbitrary.
- Static-algorithm comparison: Infomap and Community Walktrap produce score matrices equivalent to the reference up to column permutations, whereas OSLOM and Louvain merge several known classes.The latter methods consequently yield non-diagonal score matrices.
- Activity patterns: The supplementary activity plots show component activity over the second day, with some components matched to classes and others interpreted as mixed-class gatherings.The component-node matrices, membership histograms, and activity plots provide complementary views of the extracted structure.