Gauvin Laetitia, Panisson André, Cattuto Ciro
Data Science Laboratory, ISI Foundation, Torino, Italy.
PLoS One. 2014 Jan 31;9(1):e86028. doi: 10.1371/journal.pone.0086028. eCollection 2014.
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.
随着时间网络数据的日益丰富，需要对时间网络中微观结构的提取和特征描述以及将此类结构与系统的特定功能或属性相关联进行更多研究。一个突出的挑战是将静态网络所取得的成果扩展到随时间变化的网络，在这种网络中，系统的拓扑结构及其组件的时间活动模式相互交织。在此，我们研究使用一种潜在因子分解技术——非负张量分解，来提取时间网络的社区活动结构。该方法本质上是与时间相关的，并且能够同时识别社区并跟踪它们随时间的活动。我们将时间网络的时变邻接矩阵表示为一个三阶张量，并将这个张量近似为一些项的和，这些项可以被解释为具有相关活动时间序列的节点社区。我们总结了张量分解的已知计算技术，并讨论了一些可用于调整分解表示复杂度的质量指标。随后，我们将张量分解应用于一个时间网络，对于该网络，社区结构和时间活动模式都有真实的基准数据。我们使用的数据描述了一所学校中学生的社交互动、学生与学校班级之间的关联以及学生随时间的时空轨迹。我们表明非负张量分解能够高精度地恢复班级结构。特别是，提取的张量分量既可以根据已知的学校班级进行验证，也可以根据相关的活动模式进行验证，即根据由已知学校活动时间表确定的空间和时间上的重合情况进行验证。
