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

Didier Le Bail · 2025

Read Generalizing Egocentric Temporal Neighborhoods to probe for spatial correlations in temporal networks and infer their topology by Didier Le Bail (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16070.txt.

Introduction

Didier Le Bail, writing alone in 2025, introduces a new class of motifs for networks that change over time. Motifs are small recurring patterns thought to be basic parts of social contact networks. Past motif sets were either tiny or lacked triangles, a key social shape. His edge-centered motifs include triangles and have no size cap. Yet they can still be mined efficiently in any such network. He shows they contain the older neighborhood motifs as special cases. Tests on real data confirm they carry fresh information.

Catalog record

CREATORDidier Le Bail
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalizing Egocentric Temporal Neighborhoods to probe for spatial correlations in temporal networks and infer their topology Didier Le Bail 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 the literature. 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. I introduction We call motifs, or patterns, recurrent sub-elements that we find in data. Counting how many motifs of each type occur in a sample of data often gives us insight about it. Indeed, a system can often be described more simply as a combination of the motifs it contains. For example, in complex systems, a motif can be associated with a precise low-level function. Decomposing a system into its motifs allows us to decipher the various higher-level functions the system realizes. For example, in the brain, different recurrent neural circuits are associated with various functions such as different forms of memory [ 1 ] or semantics [ 2 , 3 ] and many others. In proteins, 3D sub-structures recurrent across all proteins are called functional motifs: they perform each a specific biological function [ 4 , 5 , 6 ] . Identifying these functional motifs inside a given protein allows us to predict its possible functions. This key role of motifs as elementary building blocks of more complex systems motivates the development of methods to mine efficiently for them. However, complex systems are so diverse that it could be thought that specific mining algorithms should be designed for each one of them. This is not the case, because many complex systems can be modelled by the same object: a graph, where nodes are parts of the system and edges are interactions between those parts. For dynamical systems, interactions change over time, which results in varying ties in this graph representation. In this case, the representation is called a temporal graph [ 7 , 8 , 9 ] , or temporal network, in opposition to a static network, whose nodes and edges are fixed in time. In this unifying representation, the problem of finding motifs in many complex systems reduces to the problem of finding motifs in a temporal graph. Many methods and algorithms were proposed to solve this problem both in the static and temporal setting [ 10 , 11 , 12 ] , but a generic motifs mining algorithm has to face a computational obstacle: motifs in a graph are sub-graphs. Hence, counting motifs implies identifying all isomorphic sub-graphs. As no algorithm is known to solve this problem in polynomial time, the motifs usually mined are restricted in their number of nodes or edges. In the temporal setting, the number of possible motifs is much larger, which makes mining even more difficult. Moreover, restricting to the sub-temporal graphs containing only a few edges does not give us access to the building blocks of complex systems, in particular of social face-to-face interaction temporal networks. Indeed, the presence of burstiness in social interactions [ 13 , 14 ] involves that an individual may interact with an arbitrarily large number of partners in a short time window. That is why the motifs to look for in these temporal networks should not be limited in their number of nodes or edges. Such tractable motifs have been found [ 15 ] : they are made of the interactions an ego has with its alters for a small number of time steps. These motifs are originally called Egocentric Temporal Neighborhood (ETN). Because they are limited in their duration and because they do not include the interactions between the alters, they can be mined for in linear time and size of the temporal network. The ETN have been shown to be relevant building blocks of social face-to-face interaction networks [ 16 ] , probably because they give the ego’s point of view, which reflects the social behaviour of the individual. However, they are still not enough to understand social systems. Indeed, they do not give any access to the groups of discussions and higher-order structures, which are omnipresent in social systems [ 17 ] . That’s why we define in this paper a new class of motifs together with an efficient mining algorithm, collecting both the ego’s point of view and the interactions between its alters. This allows us to extract motifs that contain triangles, which are the smallest possible non-trivial higher-order structures. This paper is organized as follows: In a first part, we describe in detail the ETN motifs of [ 15 ] , that we rename as node-centered motifs (NCTN, for Node-Centered Temporal Neighborhood). We then introduce a new type of motifs, called the edge-centered motifs, that include triangles. We abbreviate these motifs as ECTN, for Edge-Centered Temporal Neighborhood. In a second part, we investigate analytically how the ECTN and the NCTN motifs are related to each other. We derive a formula that expresses the NCTN motifs distribution in terms of the ECTN motifs distribution, before using a principle of maximum entropy to infer the reverse: the ECTN motifs distribution in terms of the NCTN motifs distribution. In a third part, we compute analytically the ECTN distribution under various assumptions on the dynamics generating a temporal network. We also explain how to compare our predictions with an ECTN distribution sampled from a given temporal network. The fourth part is devoted to the confrontation between theory and experiments: first we show that the principle of maximum entropy fails in empirical networks, proving that ECTN motifs bring additional information with respect to the NCTN motifs in those networks. Second, we investigate which assumption on the dynamics generating a temporal network produces an ECTN distribution similar to the distributions observed in empirical networks of social face-to-face interactions. From this investigation, we can estimate how complex must be a generative model to reproduce the empirical distributions of motifs. In a fifth and last part, we inaugurate a mathematical theory, that if developed could be used to partially infer the topology of a network from its motifs distribution. We then conclude

Read the complete text