Conditions for Viral Influence Spreading through Multiplex Correlated Social Networks

A fundamental problem in network science is to predict how certain individuals are able to initiate new networks to spring up “new ideas.” Frequently, these changes in trends are triggered by a few innovators who rapidly impose their ideas through “viral” influence spreading, producing cascades of followers and fragmenting an old network to create a new one. Typical examples include the rise of scientific ideas or abrupt changes in social media, like the rise of Facebook to the detriment of Myspace. How this process arises in practice has not been conclusively demonstrated. Here, we show that a condition for sustaining a viral spreading process is the existence of a multiplex-correlated graph with hidden “influence links.” Analytical solutions predict percolation-phase transitions, either abrupt or continuous, where networks are disintegrated through viral cascades of followers, as in empirical data. Our modeling predicts the strict conditions to sustain a large viral spreading via a scaling form of the local correlation function between multilayers, which we also confirm empirically. Ultimately, the theory predicts the conditions for viral cascading in a large class of multiplex networks ranging from social to financial systems and markets.

Popular Summary

New ideas, products, and trends are often disseminated through social networks. In today’s online world, a key engagement strategy known as viral marketing relies on a small group of early adopters to trigger a cascading effect (“viral spreading”) on the entire population. Examples of viral spreading include the rise of Facebook to the detriment of Myspace in the 2000s and political upheavals such as the Arab Spring that were largely enabled by social interconnectedness. We predict the conditions necessary to sustain viral spreading using physical modeling and empirical validation.

We use data from the Physics and Astronomy Classification Scheme (PACS) maintained by the American Institute of Physics. Published papers are assigned one or more PACS numbers, which makes it possible to track how various subfields of astronomy and physics grow and decline in terms of published literature. We examine five PACS subfields and use analytical solutions to predict how research networks disintegrate. We trace how the departure of both random nodes and well-connected hub nodes (i.e., established, well-connected scientists with a large number of collaborators) affects the growth and shrinkage of the subfield. We find that networks are able to recover and endure when random nodes are removed, but the departure of specific hub nodes leads to the shrinkage of the subfield. Innovators and pioneers exert influence unidirectionally through “links of influence,” and we surprisingly find that these early adopters are not always the hub nodes. However, the hub nodes are instrumental in sustaining the resulting cascades initiated by the pioneers since well-connected individuals are more likely to be aware of new trends.

Our mathematical modeling tackles the long-standing problem of the origin of viral spreading, but our methodology assumes that networks are connected in a treelike structure, where local clustering does not occur. The interconnected networks of our modern social, financial, and political systems include local clustering, necessitating additional studies to understand how viral spreading occurs in real-world networks.

Figure 1

Rise and fall of communities. (a) Comparison of activity on Myspace versus Facebook from 2004 to 2012 through Google’s Search Volume Index [12], which measures the number of Google searches of each word. The fall of Myspace coincided with the rise of Facebook, suggesting that users moved from one network to the other. The tipping point can be identified on March 25, 2007. (b) The size of the largest (giant) connected components of scientists studying “Phase Transitions” (PACS 64.60) and “Complex Networks” (PACS 89.75) from 1997 to 2009. The steady increase in the study of “Phase Transitions" declined as the “Complex Networks” field started to grow in the physics community. (c) The frequency of citations per year of the top five fields of contributing scientists to the rise of “Complex Networks”.

Figure 2

Cascades of followers through the influence of pioneers in the APS. (a) Relative size of the largest component $P_{\infty }(p)$ of collaborating scientists in the indicated fields after the departure of $1-p$ pioneers to the field of “Complex Networks." ($s=2$; other values yield similar results.) The solid curves denote the different theoretical predictions. The black curve (extreme resilience) represents classical percolation theory on a scale-free network predicting $p_c=0$ [30, 31, 32, 33]. The red curve (high vulnerability) represents the prediction of influence-induced correlated percolation for $(\alpha ,\beta ,⟨k_{\text{out}}⟩)=(0.91,1.04,0.44)$ with a predicted threshold very close to the boundary between first- and second-order transitions $p_c^{\mathrm{I}}\approx p_c^{\mathrm{II}}=0.54$. The blue curve (extreme vulnerability) represents the prediction of influence-induced correlated percolation for $(\alpha ,\beta ,⟨k_{\text{out}}⟩)=(0.91,1.04,0.83)$, giving rise to a first-order transition with $p_c^{\mathrm{I}}=0.97$. This process means that the departure of 3% of pioneers will cause cascading followers and the collapse of the original network. The red and blue curves are bounds to the real data. (b) The influence network (blue links) of collaborating scientists in the field of “Phase Transitions.” Green nodes are a sample of pioneers of the field of “Complex Networks,” and the yellow nodes are their closest followers that departed afterward. The large cascading effect produced by the departing nodes is apparent. Black links are connectivity links. (c) The largest connected component of the collaboration networks of “Phase Transitions” up to 2001 and its reduced state from 2005 to 2009 with the concomitant creation of “Complex Networks.” (d) Pioneers are not the hubs. The average degree of pioneers in the largest cluster $⟨k_{\text{pio}}⟩$ versus the maximum connectivity degree $k_{\max }$ over the members of each PACS field. We find that, in general, the degree of the pioneers is much smaller than the maximum degree, indicating that the pioneers are not the hubs (see also Table 1).

Figure 3

Modeling the cascading process of followers. (a) Sketch of the model network (considered as the giant component) with undirected connectivity links (solid black links) superimposed by a network of directed influence links (green links). The nodes are characterized by $(k,k_{\text{in}},k_{\text{out}})$, as indicated in the sample node. The node indicated by the black circle is the pioneer moving to another field and is therefore removed first. (b) First connectivity-percolation process: Two additional nodes are removed (open circles) since they are not connected anymore to the giant component after the removal of the pioneer node in (a). (c) Influence-induced process: One extra node is removed due to the influence link pointing to the pioneer that induces two more influence departures, as indicated. Such removals induce a cascading effect, since now other nodes are disconnected from the giant component, a step that is considered next. (d) Percolation-connectivity process: Three extra nodes are disconnected from the giant component and are therefore removed. (e) Influence-induced percolation process: A final node is removed due to the influence link to one of the nodes removed in (d). (f) At the end of the cascade, the giant component is reduced to six nodes. (g) Empirical study of local correlations between the influence degree and the connectivity degree averaged over all APS networks. We obtain $k_{\text{out}}\propto k^{\alpha }$ and $k_{\text{in}}\propto k^{\beta }$ with $\alpha =0.91\pm 0.04$ and $\beta =1.04\pm 0.05$. (h) Comparison between simulations and theoretical results. The symbols denote the simulation results, and the curves are the prediction of theory for $P_{\infty }(p)$. We use a scale-free network with $\gamma =2.5$ and minimal degree 1. We first generate the connectivity network and then generate the correlated influence-directed links according to the connectivity degree of each node and $(\alpha ,\beta )$ and calculate $P_{\infty }(p)$ by directly performing a percolation analysis on the network. Then, we calculate $G(x_1,x_2,x_3)$ to obtain the theoretical predictions of Eqs. (b17) and (c10). We find that the theoretical results agree very well with the simulations.

Figure 4

The phase diagram predicted by the influence-percolation model with correlation. (a) Prediction of the percolation threshold versus $\alpha$ according to Eqs. (9) and (12) for $(\beta ,\gamma )=(1.04,2.90)$ and $⟨k_{\text{out}}⟩$, as indicated. Solid lines denote the region in $\alpha$ of second-order transitions, while dashed lines denote first-order transitions. The inset shows the increase of $p_c^{\mathrm{II}}$ with $⟨k_{\text{out}}⟩$ for $(\alpha ,\beta ,\gamma )=(0.91,1.04,2.90)$. (b) Phase diagram denoting the areas in the plane $(\alpha ,\beta )$ of first-order and second-order regimes for two values of $⟨k_{\text{out}}⟩$, as indicated. The first-order regime is inside the indicated curve, while the second order is outside for a given value of $⟨k_{\text{out}}⟩$. The location of the APS networks in the phase diagram is indicated as a red dot. The networks are located near the boundary of the transitions for $⟨k_{\text{out}}⟩=0.44$ and inside the region of first order for $⟨k_{\text{out}}⟩=0.83$. The LJ network is also located in the first-order-transition regime.

Figure 5

Disintegration of communities of bloggers on LiveJournal. (a) Percolation plot in the plane $(p,P_{\infty })$ of the declining communities. The communities follow a generic curve in the plane $(p,P_{\infty })$ quantifying the rapid disintegration and cascading effects. We find a very good agreement with the empirical data that suggests that LJ communities disintegrate following a first-order transition. [See also Fig. 4 for the position of LJ in the phase diagram.] (b) Similarly to the results on the APS communities, we find positive local correlations of out- and in-influence degrees and connectivity degrees with exponents $\alpha =0.79\pm 0.03$ and $\beta =0.76\pm 0.03$, respectively.

Figure 6

Comparison of the fraction of papers published by pioneers, followers, and followers of followers. Followers are the scientists who cited at least one paper of the pioneers between 1997 and 2001 and are not the cooperators of pioneers. For a given PACS number, as indicated in the figures, we record the number of papers published in the PACS number and the number of papers published only in 89.75 (“Complex Networks”) for each author. Then, we get the total number of papers published in complex networks $N_{\text{net}}$ and the number of papers with these two PACS numbers $N_{\text{all}}$ for every author. The vertical axis shows the fraction $(N_{\text{net}}/N_{\text{all}})$ as a function of time, which approximately satisfies $\text{pioneers}>\text{followers}>\text{the rest}$. This result suggests that influence links are important for cascading dynamics.

Figure 7

Condition for a first-order phase transition. This figure shows that the functions $t(y)$ and $y(t)$ are tangential at the critical point when the transition is of the first order. Here, $⟨k_{\text{out}}⟩=0.74$, $\gamma =3$, and the minimum degree $m=2$.

Figure 8

Distribution of (a) $P(k_{\text{out}}|k)$ and (b) $P(k_{\text{in}}|k)$ for the five APS communities. We calculate the probabilities of $k_{\text{in}}$ and $k_{\text{out}}$ for a given $k$ and find that they can be approximated by Poisson distributions.

Figure 9

Estimation of $f_w^{\min }$ and $f_w^{\max }$ to obtain the bounds in $⟨k_{\text{out}}⟩$ from the empirical data. In the figure, we show three pioneers (red nodes), citation links with weights $w$ given by the number of citations, and all of the followers of the pioneers (open circles). The open purple circles denote the followers who move to “Complex Networks,” while the open blue circles do not move. For the calculating of $f_w^{\max }$, we consider the links that are active as those from followers who move to “Complex Networks.” In the figure, all the green and purple directed links are active. We estimate $f_w^{\max }=(a_w^{\max }/A_w)$ and $f_w^{\min }=(a_w^{\min }/A_w)$, as indicated in the text. For the calculation of $f_w^{\min }$, if a follower who moves to “Complex Networks” depends on several pioneers, we consider the influence link with the largest weight. For instance, for all the green influence links in the figure, the links from nodes 12 to 1 with weight 3 are active and the links from 12 to 2 and 3 are not active. In this case, we obtain $f_1^{\max }=\frac{3}{7}$, $f_2^{\max }=\frac{2}{2}=1$, $f_3^{\max }=1$ and $f_1^{\min }=\frac{2}{7}$, $f_2^{\min }=\frac{1}{2}$, $f_3^{\min }=1$.

Figure 10

Correlations between connectivity and influence networks. A flat line indicates no correlations in the APS networks for $⟨k_{\mathrm{NN}}⟩$ for the in-degree and $⟨k_{\mathrm{NN}}⟩$ for the out-degree. In the degree sequence, there are no nodes with a degree around $k=130$.