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 on possible future research about motifs. Before we go on to the next section, let us explain briefly the conventions of language we will be using in this paper: • A static network, or static graph, can be viewed as a cloud of points, with some pairs of points being linked together. The points are called vertices and the links are called edges. • A temporal network, or temporal graph, can be viewed as a succession in time of static graphs. Said otherwise, it is the data of a set of vertices with a set of edges that are either active or inactive across time. • In this paper, time is discrete and takes the form of an integer. • If not specified, a graph is actually a temporal graph. II definition of node and edge-centered motifs Before introducing edge-centered motifs, we begin by describing the motifs known under the acronym ETN, which stands for Egocentric Temporal Neighborhood. II.1 Egocentric Temporal Neighborhood ETN instances are sub-temporal graphs resulting from getting a node’s point of view for a fixed number of consecutive time steps. By “node’s point of view”, we mean the partners with whom the node interacts. More precisely, an ETN instance is extracted as follows: (1) we choose a node i that we will focus on; this node is called the central node (2) we choose a duration d of observation called the depth ; this is the number of consecutive time steps we will looking at the central node (3) we choose a starting time t for our observation (4) we collect every interaction between the central node and any other node that occurs between the times t and t+d-1 Thus, an ETN instance is labelled by three variables: the central node i , the starting time of observation t and the depth d . In practice, d is usually taken to be 2 or 3 (see Figure 1 for an example of ETN instance). (a) temporal network (b) ETN instances Figure 1: Examples of ETN instances. (a) temporal network from which the ETN instances are extracted (b) two ETN instances. Each instance is a sub-temporal graph of the network in (a), labelled by the triple (central node, starting time, depth). Here the depth is two, meaning the duration of the sub-temporal graphs is equal to two. To facilitate reading, the central node has been represented as a red square instead of a gray disk. Note that the triangle at t=1 cannot be part of any ETN instance, as only the interactions between an ego (the central node) and its alters (the satellites) are collected. Now we know what an ETN instance is, we will introduce the corresponding motif, so that we would be able to count how many instances there are of the same ETN motif in a graph. Said otherwise, given a graph G=(V,E,T) and the set of all ETN motifs \mathcal{M} , we want to compute the motif map: \begin{array}[]{cccc}m_{G}:&V\times T\times\mathbf{N}&\xrightarrow{}&\mathcal{M}\\ &(i,t,d)&\mapsto&m_{G}(i,t,d)\end{array} where i,t,d are respectively the central node, starting time and depth of the instance of the ETN motif m_{G}(i,t,d) . There are multiple ways of representing an ETN motif; we will describe three of them to help the reader getting familiar with this notion. II.1.1 Diagram representation The most intuitive way of representing an ETN is to draw them as diagrams. Such a diagram is a static graph with additional structure. It has two types of nodes and two types of edges. The nodes can either correspond to the central node or not, in which case they are called satellites . In an instance, satellites will correspond to the partners of the central node. The edges can be either horizontal or vertical. In an instance, horizontal edges are those drawn between two identical nodes at different time steps and vertical edges are those drawn between a satellite and the central node. See Figure 2 for a diagrammatic representation of the motifs associated to the instances drawn in Figure 1 . Figure 2: Diagrammatic representation of ETN motifs. When we go from the instance to the motif, the identity of the nodes is lost, as well as the starting time. The diagram representation is time-ordered: from left to right, the central node is drawn together with its satellites according to time ordering. An horizontal edge is drawn between two identical nodes at different time steps. A vertical edge is drawn between a satellite and the central node if they interact. The diagrammatic representation is not the most compact representation of an ETN. For example, the horizontal edges between the copies of the central node are redundant as they depend just on the depth. Moreover vertical edges are only possible between a satellite and the central node. From this, we see that the central node is not needed to represent an ETN. This is illustrated in the next representation. II.1.2 String representation The reason why it is possible to mine for ETN efficiently is that they can be represented as binary strings. Given an ETN, this string is built as follows: (1) we build the activity profile of each satellite. In an ETN, the activity profile of a satellite is a string of length equal to the depth of the ETN made up with ‘0’ and ‘1’. In an instance (i,t,d) , a ‘1’ at position k means that the satellite is interacting at time t+k with the central node i . (2) we sort these activity profiles by lexicographic order (or any total order on the space of binary strings of length d ) (3) we concatenate these ordered profiles in a single string. Note that any activity profile in an ETN contains at least one ‘1’. Examples of this procedure are given in Figure 3 . Figure 3: Representation of an ETN motif into a binary string. First the activity profile of each satellite is determined: a ‘1’ means the satellite interacts with the central node. Then the profiles are sorted by increasing lexicographic order and concatenated into a single string of length n_{s}d , where n_{s} is the number of satellites and d is the ETN depth. Note that the length of strings is variable and is a priori unbounded for any depth greater than zero. A representation of finite dimension is yet possible, as we will see just now. II.1.3 Map representation Note that contrary to the number of satellites, the number of possible activity profiles depends only on the depth. Then, a representation of an ETN as a tuple with a finite number of components is possible as follows: we count how many satellites realize each possible activity profile. Then, denoting the set of possible activity profiles at depth d as A(d) , an ETN of depth d is equivalent to the map (n_{a})_{a\in A(d)} where n_{a} is the number of satellites with a as activity profile. This map can equivalently be represented as a tuple as long as a total ordering convention is chosen on A(d) . Note that the number of elements in A(d) is: |A(d)|=2^{d}-1 since the empty profile is not authorized. II.2 Edge-Centered Temporal Neighborhood We have defined what an Egocentric Temporal Neighborhood (ETN) is. In the following, we will call equivalently these motifs as Node-Centered Temporal Neighborhood (NCTN), as opposed to the Edge-Centered Temporal Neighborhood (ECTN), that we are introducing now. Extracting an instance of an ECTN motif amounts to focus on a pair of nodes, called the central edge , and to collect every interaction between each node of the pair and any other node. Like in the NCTN case, we want to know whether a node is the same from one time step to the other. To be able to extract triangles, we also want to know, at each time step, whether the two nodes of the central edge are interacting with the same partner. Like NCTN instances, an ECTN instance is labelled by a triple of the form (central object, starting time, depth). For an ECTN instance, this triple is denoted by (e,t,d) , where e\in E is the central edge, t\in T is the starting time and d\geq 1 the depth. On Figure 4 , we show an example of ECTN instance. Figure 4: Example of ECTN instance. The ECTN instance is extracted from the same network as Figure 1 . Here the instance considered has (0,1) as central edge, starts at time 0 and its depth equals to 3. Note then that the whole temporal network is contained in the instance. II.2.1 Diagram representation Like in the NCTN case, we are interested in counting the number of instances of each ECTN motif in a given temporal network. This motif can be represented as a diagram, by following the same rules of the drawing of a NCTN motif diagram (see Figure 5 for the drawing of an ECTN motif diagram). Figure 5: Diagram representation of an ECTN motif. We consider the same instance as in Figure 4 . From this instance, we build the diagram representing the underlying motif. Like in NCTN, horizontal edges are drawn between identical nodes at different time steps, and vertical edges indicate interactions between nodes. Note that, contrary to the NCTN case, the central edge is no more redundant in the diagram representation, because even in the absence of satellites, it can be either active or inactive. Said otherwise, the activity profile of the central edge cannot be deduced from the profiles of its satellites. Despite this higher complexity, it is still possible to write such diagrams as strings in a fast way. II.2.2 string representation In the NCTN case, the central object needed not to be encoded. Moreover, at each time step, a satellite could be either active, meaning the satellite is interacting with the central node at that time, or inactive. In the ECTN case, the central object is encoded by an activity profile as defined previously: a binary string of length d with the ‘1’ corresponding to the times of activity of the central edge. At each time step, satellites can now be in either of four states. The letter used to code each state is indicated in parentheses: • inactive (‘0’): the satellite is not interacting with any node of the central edge • active1 (‘1’): the satellite is interacting with the first node of the central edge and not with the second • active2 (‘2’): the satellite is interacting with the second node of the central edge and not with the first • active3 (‘3’): the satellite is interacting with both nodes of the central edge To distinguish between the second and third states, we need to distinguish between the two nodes of the central edge. If we do not, we cannot recover the correct ECTN diagram from the string representation, and we would have multiple possible strings for a single ECTN motif. We will see later how to solve this problem. Once the profiles of the central edge and each satellite have been computed, we sort the satellite profiles by lexicographic order just like in the NCTN case, then we concatenate them into a single string. Then we add the profile of the central edge at the left of this string. For example, let us denote by s the number of satellites, a_{c} the profile of the central edge and a_{1},\ldots,a_{s} the profiles of the satellites. To obtain the ECTN string, we sort the a_{i} by increasing order, i.e. we find a permutation \pi such that \forall 1\leq i\leq s-1,a_{\pi(i)}\leq a_{\pi(i+1)} The final string reads a_{c}a_{\pi(1)}\cdots a_{\pi(s)} We are now ready to solve the attribution problem evoked earlier: how to decide which node of the central should be associated the letter ‘1’ or ‘2’? All we need is to test both hypotheses and retain the one yielding the smallest final string. Said otherwise, before sorting the activity profiles, we build another set of profiles where the letters ‘1’ and ‘2’ have been exchanged. Then we compare the strings obtained after sorting and concatenation of these two sets of profiles, and return the smallest string with respect to the lexicographic order. We illustrate the conversion of an ECTN instance into its string on Figure 6 . Figure 6: String representation of an extracted ECTN. The ECTN instance we take as an example is the same as in Figure 4 . At first, we do not know which naming convention to use. The first possibility is to encode by the letter ‘1’ an exclusive interaction with the node 0, and by the letter ‘2’ an exclusive interaction with the node 1. The second possibility is the reverse, obtained from the first by exchanging the letters ‘1’ and ‘2’ in the profiles of each satellite. We take as final string the smallest between the two possible ones. III relation between node and edge centered motifs What information do our motifs convey about a temporal network? In particular, we will focus on the motifs distribution, i.e. the knowledge for every motif, of its number of instances in a temporal network. What does this knowledge teach us about a temporal network? III.1 From ECTN to NCTN Before answering that question, we will show that the distribution of NCTN can be deduced from the distribution of ECTN, proving that the latter contain a priori more information than the former. Given a temporal network, let us denote by N_{n}(m) the number of instances of the NCTN m of depth d , and by N_{e}(M) the number of instances of the ECTN M of depth d . We denote also by m(i,t) the NCTN motif of instance (i,t,d) , and by M(ij,t) the ECTN motif of instance ((i,j),t,d) . We have N_{n}(m)=\sum_{i\in V,t\in T}\delta_{m,m(i,t)} Introducing Sat( i,t ) the set of the satellites of the NCTN instance (i,t,d) , we have: N_{n}(m)=\sum_{i\in V,t\in T}\delta_{m,m(i,t)}\frac{d}{|m|}\sum_{j\in\text{Sat($i,t$)}}\sum_{M}\delta_{M,M(ij,t)} Indeed, the sum \sum_{M} denotes the sum over all ECTN motifs and |m| is the length of the NCTN m viewed as a string. Then the ratio \frac{|m|}{d} is nothing but the number of satellites of m . Reorganizing the terms, we get: N_{n}(m)=\frac{d}{|m|}\sum_{i\in V,t\in T}\sum_{j\in\text{Sat($i,t$)}}\sum_{M}\delta_{M,M(ij,t)}\delta_{m,m(i,t)} Now, iterating over the indices i,t,j of the first two sums amounts to this: 1. pick a node i and a time t 2. pick a node j such that the edge (i,j) is active at least once between the times t and t+d-1 included. This iteration is equivalent to an iteration over instances (i,j,t) of non-empty ECTN motifs of depth d , on condition that we count twice each instance. Denoting by I_{d}^{M} the set of such instances, we get: N_{n}(m)=2\frac{d}{|m|}\sum_{(ij,t)\in I_{d}^{M}}\sum_{M}\delta_{M,M(ij,t)}\delta_{m,m(i,t)} where ij denotes the undirected edge (i,j) . This can be symmetrized as: N_{n}(m)=\frac{d}{|m|}\sum_{(ij,t)\in I_{d}^{M}}\sum_{M}\delta_{M,M(ij,t)}\left(\delta_{m,m(i,t)}+\delta_{m,m(j,t)}\right) The term \delta_{m,m(i,t)} can be rewritten as a condition on M : if i and j are the nodes of the central edge of M , either the NCTN centered on i or the NCTN centered on j should be equal to m . We can extract a NCTN motif from a ECTN motif by introducing maps \psi_{1} and \psi_{2} defined as follows: \psi_{1} (resp. \psi_{2} ) takes an ECTN motif and returns the NCTN motif centered on node of the central edge associated to the letter ‘1’ (resp. ‘2’). In practice, this can be done by using the maps \phi_{1} and \phi_{2} defined later. Back to our formula, we obtain: N_{n}(m)=\frac{d}{|m|}\sum_{k=1}^{2}\sum_{M\in\psi_{k}^{-1}(m)}\sum_{(ij,t)\in I_{d}^{M}}\delta_{M,M(ij,t)} This is nothing less than: N_{n}(m)=\frac{d}{|m|}\sum_{k=1}^{2}\sum_{M\in\psi_{k}^{-1}(m)}N_{e}(M) This can be written in a more compact way if we use the notion of disjoint union \coprod . A disjoint union of sets is their union taking into account the multiplicity of elements. For example, \{x\}\coprod\{x\} contains two elements. Thus we have: N_{n}(m)=\frac{d}{|m|}\sum_{M\in E_{m}}N_{e}(M) (1) where E_{m}=\psi_{1}^{-1}(m)\coprod\psi_{2}^{-1}(m) . Now, what if we are interested in the motifs frequencies and not in their number of instances? The relation between the two is the partition function: \begin{cases}Z_{n}=\sum_{m\in\{\text{NCTN}\}}N_{n}(m)\\ Z_{e}=\sum_{M\in\{\text{ECTN}\}}N_{e}(M)\end{cases} From that we deduce P_{n}(m)=\frac{dZ_{e}}{|m|Z_{n}}P_{e}(M\in E_{m}) Is there a formula relating the two partition functions that does not require the knowledge of N_{e} ? We will show that Z_{n} and Z_{e} are related to the node and edge interduration distributions, respectively. As these distributions are decoupled from each other in the general case, this might indicate that there is no simple expression of Z_{n} in terms of Z_{e} . Let us first consider the NCTN partition function: Z_{n} is the number of couples (i,t) such that the node i is active at least once within the window of size d starting from time t . Then, if we add to Z_{n} the number of couples (i,t) that are never active within the same window, we get all possible couples. The difference |V||T|-Z_{n} can be expressed in terms of the average number of consecutive times a node is inactive: Consider a node i and let us plot its activity Is( i,t ) over time on Figure 7 ), where Is( i,t ) returns True if the node i is active at time t , and False else. Figure 7: Computation of the NCTN partition function. We plot an example of activation function of a node i versus time. The function returns 1 at t if i is active at t and 0 else. The average size of the gap between two consecutive periods of activity, denoted by \Delta t on the plot, is related to the NCTN partition function Z_{n} (see text). On this plot, we introduce the gap between two consecutive periods of activity of i , that we write \Delta t . The length of such periods of inactivity is called node interduration. Since \Delta t is the number of times of inactivity, for each interduration period of size \Delta t\geq d , there are \Delta t-d+1 times t within this period, such that (i,t) is inactive for at least d consecutive time steps. Formally, let us denote by N_{ni}(\tau) the number of periods of node inactivity of size \tau . We have: |V||T|-Z_{n}=\sum_{\tau\geq 1}(\tau-d+1)\theta(\tau-d+1)N_{ni}(\tau) Thus, introducing the partition function of the node interduration distribution, we deduce that |V||T|-Z_{n}=Z_{ni}\left<(\tau-d+1)\theta(\tau-d+1)\right>_{P_{ni}(\tau)} where \left_{P(x)} denotes the average of g with respect to the distribution P for the random variable x . By a similar computation, we can show that the ECTN partition function satisfies: \left|\bigcup_{t\in T}E_{t}\right||T|-Z_{e}=Z_{ei}\left<(\tau-d+1)\theta(\tau-d+1)\right>_{P_{ei}(\tau)} where P_{ei} denotes the edge interduration distribution and Z_{ei} its partition function. E_{t} denotes the set of active edges at time t , so the union of those sets for every t is the set of edges of the fully aggregated network. From these two formula, we can conclude that the NCTN and ECTN partition functions cannot be deduced from one another. Computing the NCTN partition function from the ECTN motifs would require the knowledge of N_{e}(M) for each ECTN M . III.2 From NCTN to ECTN In the previous subsection, we have shown that the NCTN distribution could be deduced from the ECTN distribution. However, this does not mean that the ECTN contain systematically more information than the NCTN. It depends on the dynamics generating the network from which ECTN and NCTN are sampled: in some temporal networks, all the relevant information are already grasped by NCTN and the ECTN appear to be random gluing of NCTN. In such cases, we could hope to recover the ECTN distribution from the NCTN distribution. In the general case, let us make it clear that this is not possible. For example, it is possible to build an ECTN distribution compatible with a NCTN distribution via the following procedure: 1. take a NCTN 2. take one satellite 3. consider the ECTN centered on the central edge given by the pair of this satellite and the central node of your NCTN, and that contains all the interactions visible in this NCTN For example, the NCTN of depth 2 and string ‘1011’ will yield the two ECTN ‘1011’ and ‘1110’. While this construction is always possible, note that the resulting ECTN will never contain any triangle. Indeed, their string representation will contain only ‘0’ and ‘1’, the letters ‘2’ and ‘3’ will be missing. As a consequence, this ECTN distribution has little chance to match the actual ECTN distribution of the data set considered. This being said, how to test whether ECTN bring new information with respect to NCTN for a particular data set? If the distribution of ECTN does not bring any information, it should be as random as possible. That is why we propose to compare the ECTN distribution sampled from a temporal network with the ECTN distribution of maximum entropy, constrained to be compatible with the NCTN distribution of that network. If the two are similar, we will say that the ECTN distribution of that network satisfies the principle of maximum entropy (MEP). It not, then information other than the NCTN distribution are needed to recover the ECTN distribution of that network. Let us now compute the ECTN distribution with maximum entropy (the MEP distribution). III.2.1 Computation of the MEP distribution To do this, we use Lagrange multipliers to enforce the constraints under which the entropy should be maximized: \displaystyle L(N_{e},\alpha,\beta) \displaystyle=-\sum_{M}\frac{N_{e}(M)}{Z_{e}}\log\left(\frac{N_{e}(M)}{Z_{e}}\right) \displaystyle+\alpha\left(\sum_{M}N_{e}(M)-Z_{e}\right) \displaystyle+\sum_{m}\beta_{m}\left(N_{n}(m)-\frac{d}{|m|}\sum_{M\in E_{m}}N_{e}(M)\right) Deriving with respect to N_{e}(M) for each ECTN M yields \displaystyle\frac{\delta L}{\delta N_{e}(M)} \displaystyle=-\frac{1}{Z_{e}}\left(1+\log\left(\frac{N_{e}(M)}{Z_{e}}\right)\right) \displaystyle+\alpha \displaystyle-\sum_{m}\beta_{m}\frac{d}{|m|}\sum_{M^{\prime}\in E_{m}}\delta_{M,M^{\prime}} Equating to zero gives the expression for N_{e} in terms of the Lagrange multipliers: \log\left(\frac{N_{e}(M)}{Z_{e}}\right)=Z_{e}\alpha-1-dZ_{e}\sum_{k=1}^{2}\frac{\beta_{\psi_{k}(M)}}{|\psi_{k}(M)|} (2) What remains to do is obtaining the expression for \beta_{m} . It can be found by injecting the expression for N_{e} into the constraint on N_{n} . Let us introduce \begin{cases}\gamma_{m}=\exp\left(-\beta_{m}\frac{dZ_{e}}{|m|}\right)\\ \lambda=dZ_{e}\exp\left(Z_{e}\alpha-1\right)\end{cases} Then eq 2 rewrites as N_{e}(M)=\frac{\lambda}{d}\gamma_{\psi_{1}(M)}\gamma_{\psi_{2}(M)} The unknowns are the \lambda and the \gamma_{m} , but we can reduce their number by introducing \tilde{\gamma}_{m}=\gamma_{m}\sqrt{\lambda} This leads to the more convenient form for eq 2 : N_{e}(M)=\frac{1}{d}\tilde{\gamma}_{\psi_{1}(M)}\tilde{\gamma}_{\psi_{2}(M)} (3) By injecting this expression into eq 1 , we get: \sum_{M\in E_{m}}\tilde{\gamma}_{\psi_{1}(M)}\tilde{\gamma}_{\psi_{2}(M)}=|m|N_{n}(m) Let us introduce E_{m,m^{\prime}}=\psi_{1}^{-1}(m)\cap\psi_{2}^{-1}(m^{\prime}) Then we can show that \tilde{\gamma}_{m}\sum_{m^{\prime}}\left(|E_{m,m^{\prime}}|+|E_{m^{\prime},m}|\right)\tilde{\gamma}_{m^{\prime}}=|m|N_{n}(m) This system of equations can be written more conveniently if we introduce \begin{cases}\left(E_{S}\right)_{m,m^{\prime}}=|E_{m,m^{\prime}}|+|E_{m^{\prime},m}|\\ V_{m}=N_{n}(m)|m|\end{cases} Then we get: \tilde{\gamma}\cdot\left(E_{S}\tilde{\gamma}\right)=V (4) where the dot \cdot denotes the element-wise product between two matrices of same size. Once the \tilde{\gamma}_{m} have been computed, the ECTN distribution is deduced from eq 3 . To solve the system of equations 4 , we first computed the matrix E_{S} and then used the numerical solver “scipy.optimize.least_squares” [ 18 , 19 , 20 ] in an algorithm written in Python. III.2.2 The gluing matrices Let us explain how we computed the matrix E_{S} . We first notice the following relations, that hold because E_{m,m^{\prime}} and E_{m^{\prime},m} are disjoint sets whenever m\neq m^{\prime} : \left|E_{m,m^{\prime}}\cup E_{m^{\prime},m}\right|=\begin{cases}\left(E_{S}\right)_{m,m^{\prime}}\text{ if }m\neq m^{\prime}\\ \frac{1}{2}\left(E_{S}\right)_{m,m}\text{ if }m=m^{\prime}\end{cases} Second, the coefficients \left|E_{m,m^{\prime}}\cup E_{m^{\prime},m}\right| can be interpreted as follows. To build an ECTN M\in E_{m,m^{\prime}} , we need to choose the profile c of the central edge of M . Let us denote by i the central node of m and by j the central node of m^{\prime} . As the profile of j in m is the same as the profile of i in m^{\prime} , we should choose c among the profiles common to m and m^{\prime} : \displaystyle\left|E_{m,m^{\prime}}\cup E_{m^{\prime},m}\right| \displaystyle=\sum_{c\in\{a\in A|s(m,a)s(m^{\prime},a)>0\}} \displaystyle~B\left[\left(s(m,a)-\delta_{a,c}\right)_{a},\right. \displaystyle~\left.\left(s(m^{\prime},a)-\delta_{a,c}\right)_{a}\right] where A denotes the set of possible NCTN profiles and s(m,a) denotes the number of satellites with profile a belonging to the NCTN m . Before we explain what B[.,.] stands for, let us precise that we will use in this sub-subsection and the next one, the map representation II.1.3 for NCTN. In this representation, a motif m is actually a tuple of integers: m\xleftrightarrow{}(s(m,a))_{a\in A} Given two such tuples n=(n_{a})_{a\in A} and n^{\prime}=(n^{\prime}_{a})_{a\in A} , B[n,n^{\prime}] denotes the number of gluing matrices specifying which satellites of the NCTN whose map representation is n match with which satellites of the NCTN whose map representation is n^{\prime} . More precisely, a gluing matrix between two tuples n and n^{\prime} seen as representing NCTN, consists in a matrix (b_{a,a^{\prime}})_{a,a^{\prime}\in A} where b_{a,a^{\prime}} denotes the number of satellites of n with profile a that match satellites of n^{\prime} with profile a^{\prime} . Formally, a gluing matrix between n and n^{\prime} is defined by: \begin{cases}b_{a,a^{\prime}}\in\mathbb{N}\\ \sum_{a^{\prime}}b_{a,a^{\prime}}\leq n_{a}\\ \sum_{a}b_{a,a^{\prime}}\leq n^{\prime}_{a^{\prime}}\end{cases} While the number of gluing matrices is difficult to compute in the general case, we can compute it for small numbers of possible profiles. For example, if |A|=1 , the above definition reduces to: \begin{cases}b_{1,1}\in\mathbb{N}\\ b_{1,1}\leq n_{1}\\ b_{1,1}\leq n^{\prime}_{1}\end{cases} This yields B_{1}(n,n^{\prime})=1+\min(n,n^{\prime}),\forall n,n^{\prime}\in\mathbb{N} where we introduced a subscript on B to explicit the number of components of n and n^{\prime} . Here, we have a single component so we identified the tuple n to its unique integer component. For a generic |A| , the inequality b_{a,a^{\prime}}\leq\min(n_{a},n^{\prime}_{a^{\prime}}) always holds. This yields a polynomial upper bound on B : B_{|A|}(n,n^{\prime})\leq\prod_{a,a^{\prime}\in A}\left(1+\min(n_{a},n^{\prime}_{a^{\prime}})\right) However, taking this bound as approximation for B results in an ECTN distribution that does not match at all the empirical case. To determine whether this gap is due to the bad approximation or the hypothesis of maximum entropy, we need to compute B_{|A|}(n,n^{\prime}) exactly. To compute B_{k} for a generic integer k , we will establish a recursion formula. However, to speed up computations, it turns out that it is easier to compute the number of gluing matrices for n and n^{\prime} having different sizes. Indeed, it happens frequently that a motif n has many components equal to zero. If n_{a}=0 , the condition involving n_{a} for b contributing to B(n,m) yields b_{a,a^{\prime}}=0,\forall a^{\prime} . Said otherwise, the component n_{a} can be removed from n as long as the line of index a is removed from b too, turning b into a non-square matrix. Removing this way the zero components of n and m prior computing B(n,m) speeds up the computations, but requires dealing with non-square matrices. To do this, we define the set \mathcal{B}_{k,l}(n,m) of gluing matrices between the integer tuples n and m , where n has k components and m has l components: \displaystyle\hskip-10.00002pt\mathcal{B}_{k,l}(n,m) \displaystyle=\left\{b\in\mathcal{M}_{k,l}(\mathbb{N})\left|\sum_{a^{\prime}}b_{a,a^{\prime}}\leq n_{a},\sum_{a}b_{a,a^{\prime}}\leq m_{a^{\prime}}\right.\right\} where \mathcal{M}_{k,l}(\mathbb{N}) denotes the set of matrices with k rows, l columns and integer coefficients. Then we can define the number of gluing matrices between n and m : \displaystyle B_{k,l}(n,m) \displaystyle=\left|\mathcal{B}_{k,l}(n,m)\right| We can derive a recursion formula for B_{k,l}(n,m) , but before giving its expression, it is useful to introduce the following notation: \begin{cases}b_{.,+}=\left(\sum_{a^{\prime}}b_{a,a^{\prime}}\right)_{a}\\ b_{+,.}=\left(\sum_{a}b_{a,a^{\prime}}\right)_{a^{\prime}}\end{cases} Said otherwise, b_{.,+} (resp. b_{+,.} ) denotes the vector obtained by summing the matrix b over its columns (resp. rows). If n is a vector of size k , it is useful to introduce n[:i] , which denotes the vector of size k-i obtained by keeping the first components of n . Similarly, n[i:] denotes the vector of size k-i obtained by removing the first components of n . This makes the recursion formula for B_{k,l}(n,m) more human readable: \displaystyle B_{k,l}(n,m) \displaystyle=\sum_{b\in\mathcal{B}_{i,l-j}(n,m)}\sum_{b^{\prime}\in\mathcal{B}_{k-i,j}(n,m)} \displaystyle B_{i,j}\left[n[:i]-b_{.,+},m[:j]-b^{\prime}_{+,.}\right] \displaystyle B_{k-i,l-j}\left[n[i:]-b^{\prime}_{.,+},m[j:]-b_{+,.}\right] (5) We prove in Appendix S1 that this formula holds for any integers i,j,k,l as long as i0\}} \displaystyle~B_{|A|}\left[\left(m_{a}-\delta_{a,c}\right)_{a},\left(m^{\prime}_{a}-\delta_{a,c}\right)_{a}\right] where m_{a}=s(m,a) and m^{\prime}_{a}=s(m^{\prime},a) . For any couple (n,m) of integer-valued vectors, the number of gluing matrices B_{|A|}(n,m) is computed as follows: 1. the zero components of n and m are removed. For example, if n (resp. m ) has |A|-k (resp. |A|-l ) components equal to zero, and if we denote by n^{\prime} (resp. m^{\prime} ) the vector with the zero components removed, we have: B_{|A|}(n,m)=B_{k,l}(n^{\prime},m^{\prime}) 2. if k,l\leq 2 , return the value of B_{k,l}(n^{\prime},m^{\prime}) from a recursion-free formula. Else, check whether B_{k,l}(n^{\prime},m^{\prime}) has already been computed. If yes, return its value stored in the cache. If no, compute it by using the recursion formula 5 with i=\lfloor{\frac{k}{2}}\rfloor and j=\lfloor{\frac{l}{2}}\rfloor . 3. store the computed value in the cache and return to step 1. to compute the terms produced by the recursion. At this point, we have computed both the coefficients E_{S} and V of eq 4 , so we can invert it to deduce the \tilde{\gamma} . This is done by using the numerical solver scipy.optimize.least_squares with the following input: f(\tilde{\gamma})=\tilde{\gamma}\cdot(E_{S}\tilde{\gamma})-V The numerical solver will minimize the cost function: L(\tilde{\gamma})=\sum_{m}f(\tilde{\gamma}_{m})^{2}=||\tilde{\gamma}\cdot(E_{S}\tilde{\gamma})-V||_{2}^{2} Once the \tilde{\gamma} have been computed, the MEP distribution is deduced from eq 3 , that we recall here for completeness: N_{e}(M)=\frac{1}{d}\tilde{\gamma}_{\psi_{1}(M)}\tilde{\gamma}_{\psi_{2}(M)} IV probing spatial correlations with motifs We have introduced temporal motifs that include triangles. We call them edge-center temporal neighborhoods motifs (ECTN) and we showed how they were related to the node-centered motifs (NCTN) of the literature. Now, in a modeling perspective, we would like to estimate how complex a generative model should be in order to reproduce a given ECTN distribution. More precisely, we would like to identify what minimal mechanisms can account for the ECTN distribution sampled from a given data set. To achieve this, the idea is to assume some hypothesis on the dynamics generating the temporal network. Then we derive analytically the ECTN distribution we should observe according to this hypothesis. In this section, we will consider three distinct hypotheses, of increasing complexity, under which we derive an analytical expression for the ECTN distribution. IV.1 Hypothesis 1: independent edges The simplest process that generates a temporal network has no spatial correlations, meaning that each edge of the network has its own independent dynamic. We refer to this hypothesis as the hypothesis of independent edges. Before we derive the ECTN distribution under this hypothesis, let us tackle the NCTN distribution. IV.1.1 The NCTN distribution in the case of independent edges Using the map representation, a NCTN motif can be written as \vec{n}=\left(n_{a}\right)_{a\in A} where n_{a} = number of satellites with activity profile a , and A = set of possible profiles. As we exclude the empty motif in the mining phase, we are actually interested in the probability P(\vec{n}|\vec{n}\neq\vec{0})=\frac{P(\vec{n})}{1-P(\vec{0})} that we will denote as P^{*}(\vec{n}) . In the setting of independent edges, choosing a NCTN motif amounts to choosing the number of satellites, then assigning those satellites activity profiles. This writes as: P^{*}(\vec{n})=\Omega(n)n!\prod_{a\in A}\frac{p_{a}^{n_{a}}}{n_{a}!} where n=\sum_{a\in A}n_{a} = number of satellites, \Omega(n) = probability of having n\geq 1 satellites and p_{a} = probability for an edge to have a as activity profile. Thus \sum_{a\in A}p_{a}=1 . Note that \Omega is nothing but the distribution of the node degree, if we exclude the degree zero and aggregate the network on a sliding window of size equal to the depth of the considered motifs. IV.1.2 The ECTN distribution in the case of independent edges Let us compute the ECTN distribution in the same setting as above. Consider two nodes i and j , a time t and a depth d . We are interested in the probability that the ECTN instance ((i,j),t,d) is an instance of M , where M is a fixed ECTN motif. Like in the NCTN case, we restrict our distributions to non-empty motifs. Let us refer to our motif M as (c,\vec{n}) , where c is the profile of the central edge and n_{a} is the number of satellites with profile a . Because of the distinction between the two central nodes, components of n are not independent from each other. To leverage this issue, we will compute first the probability P of (c,\vec{n}) for any \vec{n} , defined by arbitrarily associating the letter ‘1’ to the node i and the letter ‘2’ to the node j . Then we deduce the probability P^{*} of observing the motif M : P^{*}(M)=\begin{cases}P(M)\text{ if the central nodes are equivalent}\\ 2P(M)\text{ else}\end{cases} (6) The case of equivalence between the central nodes corresponds to the case where the two strings from Figure 6 produced by either naming choice are equal. This being said, we can write down the probability of the couple (c,\vec{n}) : P(c,\vec{n})=P^{*}(c)\Omega(n)n!\prod_{a\in A}\frac{p_{a}^{n_{a}}}{n_{a}!} Note that the distribution \Omega and the set A are not the same as in the NCTN case. In particular, \Omega(n) denotes the probability that a pair of nodes interacts with n other nodes in a time window of size d , the motif depth. The value n=0 is now allowed, as we collect any ECTN that have a non-empty central profile c\neq\emptyset . However, we still have n=\sum_{a}n_{a} and \sum_{a}p_{a}=1 . As edges are mutually independent, our formula can be expanded further. Indeed, a profile of a satellite in an ECTN is actually a pair of edge profiles. For example, the profile ‘123’ of the satellite k comprise the edge profile ‘101’ for the edge (i,k) and ‘011’ for the edge (j,k) . Also, the profile ‘111’ comprise the edge profiles ‘111’ and ‘000’. More generally, if a is the profile of an ECTN satellite, the two edge profiles it involves are \phi_{1}(a) and \phi_{2}(a) . The \phi_{i} are maps defined as follows: \phi_{1} replaces every ‘2’ in a string by a ‘0’ and any ‘3’ by a ‘1’, every other letter being unchanged. \phi_{2} replaces every ‘1’ in a string by a ‘0’, any ‘2’ by a ‘1’ and any ‘3’ by a ‘1’, any other letter being unchanged. Then, considering Q_{a} the probability for an edge to have a as activity profile, empty profile included , we can safely write that p_{a}=P(a|a\neq\emptyset)=\frac{Q_{\phi_{1}(a)}Q_{\phi_{2}(a)}}{1-P(a=\emptyset)}=\frac{Q_{\phi_{1}(a)}Q_{\phi_{2}(a)}}{1-Q_{\emptyset}^{2}} We deduce the expression for P(M) : \hskip-28.45274ptP(c,\vec{n})=\frac{Q_{c}}{1-Q_{\emptyset}}\Omega(n)\left(1-Q_{\emptyset}^{2}\right)^{-n}n!\prod_{a\in A}\frac{\left(Q_{\phi_{1}(a)}Q_{\phi_{2}(a)}\right)^{n_{a}}}{n_{a}!} (7) Together with equation 6 , it allows to compute P^{*}(M) for any ECTN M . IV.2 Hypothesis 2: conditional independence of edges Assuming independent edges makes triangles unlikely to occur. To have a glimpse of this, let us consider an ECTN profile a such that \phi_{1}(a)\neq\emptyset and \phi_{2}(a)=\emptyset . Then we have p_{a}\propto Q_{\phi_{1}(a)}Q_{\emptyset} . If now we replace every ‘1’ in a by a ‘3’, we get the profile a^{\prime} such that p_{a^{\prime}}\propto Q_{\phi_{1}(a)}^{2} We deduce \frac{p_{a^{\prime}}}{p_{a}}=\frac{Q_{\phi_{1}(a)}}{Q_{\emptyset}}\ll 1 The last inequality holds in the empirical data sets we consider, because of the sparsity of social interactions. Despite this sparsity, ECTN with triangles are much more likely than predicted when assuming independent edges. This motivates for another hypothesis, under which triangles are more likely to occur. For a triangle to occur, there must exist a correlation between adjacent edges. The simplest way to introduce such a correlation while keeping the computation of the ECTN distribution tractable, is to assume that nodes are independent from each other. To give a meaning to this idea, we associate a hidden state h_{i} to each node i of the network. The independence condition means that the variables h_{i}(t) and h_{j}(t^{\prime}) are statistically independent whenever i\neq j . Besides these hidden states, we assume the existence of a measurement process, that takes the hidden state as input and returns the interaction graph between nodes at the current time. This modeling is akin to a hidden Markov model that would generate the temporal network we observe. Examples of such models in the literature are [ 21 ] for growing a static network and [ 22 ] for generating a temporal network. As we aim at starting simple, let us assume that at each time t , the interaction graph G(t) is generated as follows: \forall i