The switching mechanisms of social network densification

Empirical evidence on mixed densification scaling

We focus our analysis on temporal contact networks taken from the following four datasets:

• WS-16: Contacts between participants of the Computational Social Science Winter Symposium 2016 at GESIS in Cologne on November 30, 2016¹⁹.

• IC2S2-17: Contacts between participants of the International Conference on Computational Social Science 2017 at GESIS in Cologne on July 12, 2017¹⁹.

• Hospital: Contacts among patients, nurses, doctors and staffs in a Hospital in Lyon on December 8, 2010²⁰.

• Workplace: Contacts between workers in a office building in France on June 27, 2015²¹.

These data consist of contacts between individuals collected every 20 seconds using RFID sensors^18,22. A “contact” is here defined as a physical, face-to-face proximity event. The datasets thus give us temporal networks in which nodes are individuals and edges encode the contacts occurring between them. All datasets exhibit large and abrupt fluctuations of the number of edges that are typical in these non-stationary systems (see Fig. 1, lower panels). In these particular contexts of social interactions, these transitions between high an low activity periods are often related to specified schedules: from talk sessions to coffee breaks in the conferences, changes in shifts in the hospital, from desk work to meetings in the workplace.

In many social and economic dynamical networks, the numbers of aggregate edges and nodes have a superlinear scaling relationship called the “densification power law”^14,23,24, in which the average degree is increasing with the number of nodes, i.e., “densification”. For temporal networks, where there is a sequence of network snapshots, a similar type of scaling emerges from the dynamics of the population, in which nodes enter and leave the system, keeping the chance of two nodes being connected constant^15,25. However, another type of scaling emerges in real-world systems for which the population is fixed. In such systems densification is “explosive”, with the scaling exponent increasing with N¹⁵. While these two classes of scaling could be differentiated and identified from data if we observe a specific type of scaling¹⁵, in general there may exist a mixture of them that cannot be easily classified as one of the two classes. Indeed, in the four datasets we study, no clear scaling relationship appears (Fig. 1, upper panels). In the following we show that the mixed shape of empirical densification behavior reflects a mixing of both classes of scaling.

Two dynamical regimes in the dynamic hidden-variable model

To explore the temporal dynamics of densification and sparsification, we consider a dynamic version of the hidden variable model. The probability that two nodes i and j are in contact within a given time window t is:

where (a_i) is the “fitness” that represents the intrinsic activity level of node i^26,27,28, and T denotes the last time window in the data. There are two time-varying parameters in the model. The first one is (kappa _t>0), which modulates the overall activity rhythm of nodes. A variation in (kappa) would reflect the time-schedule of a conference or a school, working hours in an office or a hospital, or the circadian rhythm of individuals^9,22,29,30. The second time-varying parameter (N_mathrmp,t) denotes the potential number of active nodes at time t, i.e., the total of active and inactive nodes that are in the room or the building. It should be noted that although the number of active nodes (i.e., nodes having at least one edge) (N_t) is always observable from the data, the potential number of nodes (N_mathrmp,t) is not. We do not usually know how many people were actually in the room at a given time because people could enter and exit the room at any time without being interacting with any other individual. We can observe the number of active nodes that appear in the record of contacts, but in many cases there is no record of nodes without any interaction. We assume that activity (a_i) is uniformly distributed on [0, 1], because (i) we do not have any prior information about the full distribution of the activity levels of all nodes including isolated ones, and (ii) introducing a more general distribution prohibits us from obtaining an analytical solution, which makes it difficult to implement parameter estimation.

The average numbers of active nodes N and edges M are analytically given as (see “Analytical expression for N and M” section in Methods for derivation):

where we drop time subscript t for brevity. From these expressions, it is clear that the two parameters (kappa) and (N_mathrmp) play different roles in the determination of N and M, but it is not clear how N and M correlate. To see the direct relationship between N and M, we eliminate one of the two parameters in Eq. (2), using Eq. (3). By doing this, we can effectively endogenise either (kappa) or (N_mathrmp). Depending on whether we endogenise (kappa) or (N_mathrmp), we obtain different functional forms that connect N and M.

Regime 1: (N_mathrmp)-driven dynamics

First, let us consider the case of time-varying (N_mathrmp). This is a situation in which the dynamics of N and M are fully driven by changes in the population. We call this system as being in “Regime 1” or “state 1”:

Definition 1.

A system is in Regime 1 if (N_mathrmp) is time-varying and (kappa) is constant, in which case the dynamical relationship between N and M is given by:

where the time-varying (N_mathrmp) value is expressed as a function of (M_t) and (kappa): (N_mathrmp(M_t,kappa ) equiv frac1+ sqrt1+32M_t/kappa 2) (see, Eq. 3).

For the purpose of parameter estimation, we introduce an error term as (N_t=h^1(M_t;widehatkappa ) + varepsilon _1,t,) where (widehatkappa ) denotes the estimated value of (kappa), and (varepsilon _t^1) is a residual term following a normal distribution with mean zero and standard deviation (sigma _1). Estimated value of (N_mathrmp,t) when the system is in Regime 1 leads to:

where (S_t=1) denotes the fact that the system is in Regime 1 at time t. In Regime 1, network dynamics is totally driven by the time-varying nature of the population, what we call “(N_mathrmp)-driven” dynamics. For a given (kappa), the slope of densification scaling is close to constant, while different (kappa) yield different slopes (Fig. 2, lower left).

Regime 2: (kappa)-driven dynamics

Next, let us consider the case of time-varying (kappa). This corresponds to a situation in which the dynamics of the system is fully driven by changes in the overall activity of individuals. We call this system as being in “Regime 2” or “state 2”:

Definition 2.

A system is in Regime 2 if (kappa) is time-varying and (N_mathrmp) is constant, in which case the dynamical relationship between N and M is given by

where the time-varying value of (kappa) is expressed as a function of (M_t) and (N_mathrmp): (kappa (M_t,N_mathrmp) equiv frac8M_tN_mathrmp(N_mathrmp-1)) (see, Eq. 3).

For estimating, we add an error term as (N_t=h^2(M_t;widehatN_mathrmp) + varepsilon _2,t,) where (widehatN_mathrmp) denotes the estimated value of (N_mathrmp), and (varepsilon _2,t) is a residual term following a normal distribution with mean zero and standard deviation (sigma _2). Estimated value of (kappa) at time t when the system is in Regime 2 leads to:

In Regime 2, network dynamics is fully driven by the individuals’ time-varying activity levels, what we call “(kappa)-driven” dynamics, and the slope of densification scaling in fact increases with N (Fig. 2, lower middle). This kind of accelerating growth of M naturally happens when edges are created in a fixed-population system, in which case the network tends to be denser as the number of inactive nodes vanishes.

Analysis of switching dynamics behind temporal densification and sparsification

A Markov regime switching model

In real-world networks, the mechanism of densification and sparsification may occasionally change depending on the context, such as working schedule, coffee breaks, lunch time, etc. To incorporate such a possibility, we propose a unified framework based on the Markov regime switching model in which the hidden state of a system can switch from Regime 1 to Regime 2 (respectively from Regime 2 to Regime 1) with probability (p_12) (resp. (p_21))^16,17. An important advantage of the regime switching model is that it allows us to calculate the probability of a system being in Regime (sin 1,2\) at time t for a given parameter set (varvectheta =N_mathrmp,kappa ,sigma _1,sigma _2,p_11,p_22\). This probability of the system being in Regime s can then be interpreted as the relevancy of each mechanism in explaining the densification dynamics at a given time (Fig. 2). We employ a Bayesian approach for the estimation of the parameters, using the Markov chain Monte Carlo (MCMC) to obtain posterior distributions (see, Methods “Bayesian estimation” for the estimation method). It should be noted that (varvectheta ) does not contain (N_mathrmp,t|_S_t=1) and (kappa _t|_S_t=2) since (varvectheta ) only contains constant parameters to be directly estimated by the Bayesian method.

In the following, we use the smoothed probability (mathrmPr(S_t=s|psi _T;varvectheta )) which is calculated conditional on all the information available at time T, denoted by (psi _T) (see, Methods “Smoothed probability” for full derivation) ³¹. Validation analyses using synthetic networks show that the proposed method correctly detects the switching of regimes and estimates the model parameters quite accurately (Table S1, Figs. S1 and S2 in Supporting Information (SI)). Given the probability of being in Regime (sin 1,2\), we can estimate the dynamical parameters (N_mathrmp,t) and (kappa _t) as:

where (widehatvarvectheta ) denotes the set of estimated parameters, which is summarised in Table 1 in Methods.

Classification of network dynamics

The Bayesian estimation of the parameters suggests that the empirical systems’ dynamics are indeed occasionally switching between (N_mathrmp)-driven and (kappa)-driven (Fig. 3, upper panels). For the conference data, a common feature is that the probability of being in Regime 1 is almost 1 prior to the first session and after the last keynote session of the day, and mostly zero in between (see Fig. 4 for the correspondence between the dynamics and the schedule of the conferences). For WS-16, we see further fluctuations between the two regimes, one linked to the lunch break, the other to the poster session which closed the day. This suggests that the dynamics during the oral sessions, keynote talks and breaks are mainly driven by changes in the activity level of participants, while in the “opened” time slots, such as registration, closing and poster session, their dynamics are explained by time-varying population. The same patterns linked to the schedule are found on the other days of the conferences (see S3a–c).

For the Workplace data we see a roughly similar pattern (Fig. 3, top right). The dynamics in the early morning and evening are driven by a variation in (N_mathrmp), as well as around lunch time and coffee break, and changes in activity level are the main source of dynamics in between. This is, of course, not necessarily a general property of contact networks in physical space. We also see that the regime remains almost constant in most of the day (Fig. S3e), or there might be days in which the regime constantly changes throughout the day (Fig. S3f). In the case of the Hospital data, there is no clear tendency for the regime-switching pattern (Fig. 3, third column and S3d), which seems natural for such an open environment with visitors and medical workers coming and going, and no general, fixed schedule for working hours.

We next attempt to classify the snapshot networks into two groups based on their probability of being in a particular regime. We identify a snapshot network at t as being in Regime 1 (resp. Regime 2) if more than 95 % of samples for the value of (mathrmPr(S_t=1|psi _T;varvectheta )) generated by MCMC are greater than 0.5 (resp. lower than 0.5), i.e., in more than 95 % of parameter sampling the dynamics at t is considered to be attributed to Regime 1 (resp. Regime 2). Otherwise, the system is considered as being in an undetermined “gray area”. As seen in the lower panels of Fig. 3, the location of snapshot networks in the N–M space is strongly related to which regimes they belong to. As expected, the snapshots in Regime 1 exhibit a scaling whose slope is almost constant (i.e., (N_mathrmp)-driven scaling), while the snapshots in Regime 2 exhibit accelerating growth patterns (i.e., (kappa)-driven scaling). Classifying each time window according to the underlying dynamical mechanism is essentially equivalent to identifying patterns in the N–M space.

Temporal dynamics of population and activity level

We also examine the evolution of the dynamical parameters for both regimes (Fig. 4). For the two conferences (WS-16 and IC2S2-17), the estimated population size (widehatN_mathrmp,t) increases at the beginning of the day and decreases at the end, consistent with the dynamics of participants entering and exiting the venue. The estimated activity parameter (widehatkappa _t) is high during these periods, and the level is consistent with those seen in highly active windows during social breaks. During the main program, the population is virtually constant and the size is consistent with the number of attendants ((sim) 120 for WS-16, (sim) 200 for IC2S2-17). The variation of network size is thus mainly driven by the schedule, which constrains the participants’ networking activity. In the case of WS-16, the fluctuation of (widehatN_mathrmp,t) during the lunch break and the poster session are worth noting since the variation of observed network size N seems to be driven by both mechanisms; we see slight reductions in the estimated population while the overall activity is still high in these time windows. This demonstrates the ability of the proposed method to extract mixed-regime periods in which both of the two mechanisms are at work (see Fig. 2, right, for schematic). Similar patterns are also found in the other days (see S4).

In the Hospital data, the regime-switching dynamics is much less periodic, with lots of transitions and mixed periods (Fig. 5a). This is however not surprising, because there is no fixed schedule regulating either the activity or the number of people present. For the Workplace data, we also do not expect a priori to see a clear segmentation of regimes because of the absence of a rigid schedule as in a hospital. However, the dynamics uncovered by our method indicates that the situation is much simpler than that for Hospital, as there seem to be less variation in population size, aside from the “opening” and “closing” effects and a reduction in population around the lunch time (Fig. 5b). The day that exhibited many regime switches presents however many episodes of small variations in population size (see S4), similar to the dynamics observed in a Hospital.

Non-monotonic behaviour of network density

Since both types of scaling emerging from two different dynamics exhibit superlinearity, the average degree is always increasing in N. However, the density of networks, defined by (2M/(N(N-1))), is not always increasing with N (Fig. 6). In fact, when the dynamics is (N_mathrmp)-driven, the network density mostly decreases as the network size N increases (Fig. 6, blue circle). So, a rise in N causes the density to be smaller when the engine of dynamics is changes in population. In contrast, when changes in (kappa) play a dominant role, the network density may increase when the network size is sufficiently large (Fig. 6, pale-red cross). This is because when the number of active nodes N is close to its upper bound (N_mathrmp), at which the activity levels of remaining inactive nodes are fairly low, the overall activity (kappa) needs to be large enough for those low-activity nodes to get at least one edge. This would necessarily increase the total number of edges in the network to a large extent, which leads to a “true” densification of networks.

These properties are also confirmed by the analytical equation for the average network density¹⁵

where (q_0) denotes the fraction of isolated nodes in the system (see Eq. 16 in Methods “Analytical expression for N and M”). If the system is in Regime 1, in which (kappa) is constant, the density monotonically approaches (kappa /4) as (N_mathrmprightarrow infty) (i.e., (q_0rightarrow 0) and (Nrightarrow infty)). On the other hand, if the system is in Regime 2, in which (N_mathrmp) is constant, there is no a priori upper bound, and the density exhibits a non-monotonic behaviour. In Regime 2, a change in (kappa) has two opposing effects on the network density. First, an increase in (kappa) directly increases density through a rise in the probability of edges being created. Second, a shift in (kappa) would also increase N, which reduces the density through the third term in Eq. 10. Since (q_0rightarrow 0) as N becomes sufficiently large, the latter effect is vanishing, and therefore the density begins to rise with N for a sufficiently large N.