Gaining intuition - a basic mean-field.

To gain insight into the statistics of the causality trees, we first propose a simple transmission theory relying on the following assumptions. a) There exists an underlying social network which is static. Though we know that at large time scales, e.g., years, the underlying social network is necessarily dynamic, we assume that at short time scales of the order of hours to few days the static approximation provides a reasonable description. b) Given a couple of nodes and , there is a directed link from to if called at least once in the database, i.e, if the directed link is present in the underlying social network. This directed link is associated to a time series: the timestamps at which has contacted . For every link we can define a communication rate that indicates the rate at which the link is active to transmit information. This is simply the number of phone calls that occurred in the database, divided by the total time . c) We define causality trees as sequences of consecutive phone calls where the time difference between consecutive phone calls is always less or equal to our observation time .

In this introductory subsection, we aim at gaining some intuition on the spreading process by reducing all the complexity of the social network topology to its average degree, and all the complexity associated to the temporal phone call dynamics to the average phone call rate per edge. We focus initially only on the average tree size. In the next subsection we will include more complex features such as in- and out-degree distributions, in-out degree correlations, etc, and focus on more interesting measurements as the size and depth distributions of the trees. For the moment, nevertheless, we study this oversimplified dynamics since it allows us to understand in very simple terms that there is a competition between the monitoring time and the phone call frequency. This competition determines the critical monitoring time above which a phase transition occurs. The mean-field associated with this simplified process reads:(1)where the dots indicate time derivatives, refers to the fraction of individuals that are uninformed at time , to those that are informed and retransmitting the information, and to those that got the information and stop retransmitting, is the average , and the average (out-)degree. Notice that for directed networks, the average in- and out-degree are the same.

The average cascade size is the average number of individuals that got the information once the process is extinguished , i.e., when there is no more users retransmitting the information and . It is easy to realize from Eq. (1) that , and . Using the fact that and , we obtain that the number of users that once got the information, i.e., the average tree size, , reads:(2)where is the number of users in the system. Eq. (2) defines a self-consistency equation for . From this expression we can derive the critical monitoring time required to observe infinite tree sizes:(3)This means that if nodes retransmit the information that they get for a period the resulting trees can be arbitrarily large. It is important to make the distinction between the duration of cascade events, i.e., the time elapsed between the first and last phone call of the tree, and the monitoring time . For instance, when only a small fraction of the cascades percolates and consequently the average tree duration is shorter than . Notice that the monitoring time refers (and controls) the individual behavior of users as callers. In fact, we are asking ourselves how the individual behavior of users should be in order to allow a rumor to take over a macroscopic fraction of the system. We will come back to this point later on and look for an interpretation of this relevant quantity.

Now let us consider the other hypothesis mentioned in the introduction, i.e., let us imagine that information travels in both directions of the directed edges. In this case, we can still use Eq. (2) to describe the spreading process, but parameters have a different meaning. The average rate activity now represents the activity of an undirected edge, i.e., it is the average of . Finally, the average out-degree has to be replaced by the average (undirected) degree , since now edges are undirected. Thus Eq. (3) becomes: .

Taking into account topological features - in-out degree distributions.

In the following, we move a step further and take into account the in- and out-degree distributions, as well as the in-out degree correlations of the underlying static social network, and the time distribution of phone calls. Our goal is to obtain an expression for the probability of finding a user with in-degree and out-degree for a given . The in-degree represents the number of different users that have called the user during . Similarly, denotes the number of different users that the user has called during the monitoring time . This means that we are considering that there is an underlying static network whose directed links are switched on and off – this dynamics defines a (directed) dynamical network.

In order to compute , we need to know the probability that an edge is activated within a period . More precisely, we need to know for a node that has in-degree and out-degree , the probability per in-edge and per out-edge of being used within a period . Then, if for instance , the probability that two of the three in-edges are used while one is not, is .

We denote the probability of finding a node with in-degree and out-degree : . The probability refers to the static underlying network that contains all connections that have occurred in the whole database. Thus, assuming that the in-degree of a node is uncorrelated with the out-degree of other nodes, we can express as:(4)where we have also assumed that the activity of an edge is independent of the activity of the other edges, and used the binomial distribution approximation explained above.

To simplify Eq. (4), we make another assumption: the edge activity is independent of the in- or out-degree of the node, i.e. . Edges exhibit a heterogeneous distribution of communication rates . Let us recall that is the rate at which an edge is used within , i.e., the number of phone calls through the edge divided the total time . We need an estimate for the probability that the edge is used during . Knowing and assuming a Poissonian process, the probability that the edge is used is [16]. Though this assumption is a strong simplification of the actual process at the level of edge usage, it does not imply that we are assuming that users exhibit a Poissonian phone call activity. Moreover, since we consider the activity of a user proportional to its out-degree, if the out-degree distribution is heavy-tail distributed, so is the user activity distribution. Under these assumptions can be estimated as:(5)

If now we consider that information travels in both direction of the edges, we need to take into account the undirected degree distribution exhibited by the nodes. Along similar lines, we can express the probability of finding a user of undirected degree for a given as:(6)where refers to the degree distribution of the undirected static social network, and is the probability that an edge connected to a node of degree is used during .

Critical monitoring time .

We now look for an expression of the critical monitoring time , which is sensitive to the topological structure of the underlying static network. As before, we start by assuming that the underlying static network is directed – below we address the alternative case where information travels in both direction on edges. To derive the percolation threshold from Eq. (4), we look for the associated generating function . After exchanging the order of the sums in order to use the binomial expansion, we obtain:(7)

The process described here corresponds to a situation where, for a given , some edges are activated while others remain silent. We want to know whether the (directed) network of activated edges contains giant trees. As explained in [18], the condition for having infinite clusters in (static) directed networks is . We can evaluate this condition for our dynamical network using Eq.(7), and recalling that , and . The evaluation of the above mentioned condition leads to:(8)where and . Notice that if the underlying network does not exhibit a giant component for , condition (8) cannot be fulfilled for any .

To gain some intuition, let us assume that , so that from Eq. (5) we can approximate as so that:(9)

Let us now consider the following two extreme cases: a) a fully in-out degree correlated underlying static network, where , for which we get(10)and b) a fully in-out degree uncorrelated underlying static network, i.e., , where we find that(11)which is exactly the mean-field prediction given by Eq. (3).

In Fig. 2 we compare the average tree size obtained from the data with the above discussed theoretical arguments. The vertical lines correspond to the predictions given by Eqs. (9), (10), and (11). In order to evaluate Eq. (9), we have measured and using the underlying static network, and estimated the average edge activity from the log data. For Eq. (10), we have computed in addition . Finally, for Eq. (11), since we assume uncorrelated in-out degree, we only need to know which has been already measured to estimate Eq. (9) (let us recall that directed networks are such that ). The in- and out-degree distributions of the underlying static network are shown in Fig. 3A, while the in-out correlation matrix, which is characterized by a Pearson's coefficient [19] of , is shown in Fig. 3B. Fig. 2 shows that there is large difference between the thresholds corresponding to the extreme cases given by Eqs. (9) and (10), more than hours, which indicates that the spreading process strongly depends on the in-out degree correlations. How can we understand that correlations have such an important effect on the spreading process? If we look at either the in- or the out-degree distribution of the underlying static network, we observe that both of these distributions exhibit fat tails, see Fig. 3A. The heterogeneity of user degree implies the presence of super-spreaders as well as super-receivers. Though the relevance of super-spreaders have been well identified and understood since many years [20], the existence and role of super-receivers have remained relatively unexplored, except for a few noticeable works where the relevance of in-out degree correlations were acknowledged [18], [21], [22]. We notice that for an undirected network, the degree of a node plays both roles, being its in- as well as its out-degree (and consequently, a high degree node is both a super-spreader and a super-receiver). On the contrary, for a directed network, the difference between the in- and out-degree of a node, as we will see, is key to understand the role of the node on the spreading process. A super-receiver is a node that is highly susceptible to get the information, since it can be contacted by a large number of different users. On the other hand, a super-spreader is a node that once informed can potentially retransmit the information to many different users. If a node is a super-receiver but not a super-spreader, it can easily get the information but it cannot contribute much in the spreading process. On the other hand, a node that is a super-spreader but not a super-receiver, while it can potentially retransmit the information to many different users, it will rarely get the information. Consequently, these nodes rarely help to the spreading process of the information. In summary, only those nodes that are both, super-spreader and super-receiver, play a significantly role on the spreading process.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. Average cascade size as function of the observation time .

The transition towards arbitrarily large cascade sizes can be estimated theoretically using Eq. (8). The vertical lines correspond to various assumptions on the underlying social network, particularly on the in-out degree correlation matrix: fully correlated, fully uncorrelated, and the actual situation, see text.

https://doi.org/10.1371/journal.pone.0028860.g002

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. Statistics on the in- and out-degree of the underlying social static network.

The in- and out-degree distribution, and , respectively, are shown in A, while in-out degree correlations, i.e., , in B, where the color scale corresponds to .

https://doi.org/10.1371/journal.pone.0028860.g003

For fully in-out correlated networks (see Eq. (10)), nodes exhibit the same in- and out-degree. This implies that all super-receivers are also super-spreaders. Thus, each super-spreader has a high probability of getting the information and subsequently retransmit it. Fig. 2 shows that for – Eq. (10) – we would observe arbitrarily large trees for values larger than hours. In general, we expect larger trees for a fully correlated network with the same number of super-spreaders (and super-receivers) as in the original network. Positive in-out degree correlations clearly facilitates information spreading. On the other hand, we expect fully in-out uncorrelated networks to exhibit smaller trees, since it is very difficult to find a node that is both, super-spreader as well as super-receiver. Fig. 2 indicates that for fully in-out uncorrelated networks – Eq. (11) – arbitrarily large trees would only emerge for values larger than hours, though again the network contains as many super-spreaders and super-receivers as in the original network. Clearly, the absence of in-out correlations makes difficult the spreading of information.

Notice that in the actual underlying static network, though there is an important fraction of nodes that are simultaneously super-spreaders and super-receivers (see diagonal in Fig. 3B), there are also many nodes that are either super-spreader or super-receivers, but not both (off-diagonal elements in Fig. 3B). This explain why we observe in Fig. 2 that the actual dynamics falls in between these two extreme cases, i.e., in between the fully correlated and fully uncorrelated underlying static network.

If information travels in both direction on edges, we have to make use of Eq. (6). Its associated generating function reads:(12)where as explained above, refers to the degree distribution of the undirected underlying network and to the probability that an undirected edge is used during . To obtain , we make use of the well-known percolation criterion for uncorrelated undirected networks, [23]. As before, if we assume that , then:(13)This result has been derived by Newman in [16] and recently used in the context of a mobile phone network by Miritello et al. in [8]. The estimated value for using Eq. (13) is hours. We recall that if the information travels along the direction given by the directed edges, the critical corresponds to Eq. (9). The prediction given by Eq. (13) is close to that obtained from Eq. (10), which corresponds the fully correlated scenario discussed above, see Fig. 2. Notice that Eq. (9) never reduces to Eq. (13). This indicates that that directed, that is to say, intentional or active information propagation is qualitatively different from unintentional information spreading, i.e., when information travels in both direction along edges. For instance, while for unintentional spreading depends always on the second moment of the degree distribution, for intentional spreading it may not depend on it, if the network is in-out degree uncorrelated.

Size of trees.

In the following we focus on the statistical features of the trees. We start out by estimating the size distribution under the assumption that information travels in the direction of the (directed) edges. In order to get an analytical estimate of , we neglect node-node correlations in the underlying static network as well as temporal correlations among nodes. It will be clear that node-node (topological) correlations can be ignored for , while temporal correlations are always too weak to impact the spreading dynamics (see below). We further assume that trees are fully determined by the out-degree , but as we will see, the assumption breaks down as we approach .

These simplifications allow us to estimate the probability of finding a tree of size one as the probability that the root node has out-degree , i.e., . The probability of finding a tree of size two has to be equal to the probability that the root node has out-degree while simultaneously its unique branch has to lead to a sub-cascade of size , i.e., . More generally, is related to with . This relation can be expressed in a compact and elegant way in term of the generating function which obeys the following self-consistency equation [24]:(14)where is the generating function of the out-degree distribution that is defined as:(15)

The cascade size distribution can be obtained from the derivatives of as(16)In summary, Eq.(14) provides us with a method to derive under the assumption that the tree statistics is given by a Galton-Watson (GW) process [24] that is fully determined by . Notice that for a given , the out-degree distribution can be approximated using Eq. (7) as indicated by Eq. (15). This approximation starts to fail for large values of due to the non-homogenous activity of node over time. Alternatively, can be directly measured from the data for each .

Depth of trees.

Now we look for an estimate of the depth distribution under the same assumptions, i.e., the tree statistics is given by a GW process fully determined by . We define , with . We look for the probability that a tree gets extinguished at depth less or equal than . The probability obeys . Using a more compact notation [24], this relation reads:(17)On the other hand, the probability that a tree gets extinguished at is directly the probability that a node does not make phone any phone call in a period , i.e., . Thus, using the above given definition of , we rephrase Eq.(17) as:(18)We can draw the probability from , as:(19)

If we assume that information can flow in both direction of the edges, the above depicted GW process for a directed underlying network can be easily adapted to an undirected network, the main difference being that the GW process is now fully determined by the (undirected) degree distribution – see Eq. (6). Except for this, the computations of and follows similar lines, taking into account that a node of degree can contribute at most with new nodes to the growing tree.