Generalizing Egocentric Temporal Neighborhoods to probe for spatial correlations in temporal networks and infer their topology

Abstract

Motifs are thought to be some fundamental components of social face-to-face interaction temporal networks. However, the motifs previously considered are either limited to a handful of nodes and edges, or do not include triangles, which are thought to be of critical relevance to understand the dynamics of social systems. Thus, we introduce a new class of motifs, that include these triangles, are not limited in their number of nodes or edges, and yet can be mined efficiently in any temporal network. Referring to these motifs as the edge-centered motifs, we show analytically how they subsume the Egocentric Temporal Neighborhoods motifs of [A. Longa, G. Cencetti, B. Lepri, and A. Passerini, An efficient procedure for mining egocentric temporal motifs, Data Mining and Knowledge Discovery 36, 355 (2022)]. We also confirm in empirical data that the edge-centered motifs bring relevant information with respect to the Egocentric motifs by using a principle of maximum entropy. Then, we show how mining for the edge-centered motifs in a network can be used to probe for spatial correlations in the underlying dynamics that have produced that network. We deduce an approximate formula for the distribution of the edge-centered motifs in empirical networks of social face-to-face interactions. In the last section of this paper, we explore how the statistics of the edge-centered motifs can be used to infer the complete topology of the network they were sampled from. This leads to the needs of mathematical development, that we inaugurate here under the name of graph tiling theory.