Explosive percolation on directed networks due to monotonic flow of activity

An important class of real-world networks has directed edges, and in addition, some rank ordering on the nodes, for instance the popularity of users in online social networks. Yet, nearly all research related to explosive percolation has been restricted to undirected networks. Furthermore, information on such rank-ordered networks typically flows from higher-ranked to lower-ranked individuals, such as follower relations, replies, and retweets on Twitter. Here we introduce a simple percolation process on an ordered, directed network where edges are added monotonically with respect to the rank ordering. We show with a numerical approach that the emergence of a dominant strongly connected component appears to be discontinuous. Large-scale connectivity occurs at very high density compared with most percolation processes, and this holds not just for the strongly connected component structure but for the weakly connected component structure as well. We present analysis with branching processes, which explains this unusual behavior and gives basic intuition for the underlying mechanisms. We also show that before the emergence of a dominant strongly connected component, multiple giant strongly connected components may exist simultaneously. By adding a competitive percolation rule with a small bias to link uses of similar rank, we show this leads to formation of two distinct components, one of high-ranked users, and one of low-ranked users, with little flow between the two components.

Figure 1

Temporal evolution of the retweet network on Twitter after the discovery of the Higgs boson. Blue links indicate a lower-rank node retweeting a higher-ranked node, and red links indicate a higher-ranked node retweeting a lower-ranked node. Nodes of degree 0 and 1 are removed for the sake of readability, and any nodes that appear to be of degree 0 or 1 are actually connected to some number of degree 1 nodes that were removed. (Left) First 1000 retweets. (Middle) First 4000 retweets. (Right) First 10000 retweets. This data set is publicly available as part of the Stanford Large Network Dataset Collection [15],

Figure 2

The number of reverse edges compared to the total number of edges. That is, the number of times a higher-ranked user retweets a lower-ranked user compared to the total number of retweets after the discovery of the Higgs boson. Note that the number of reverse edges is only about 1% of the total number. The optimal linear fit is given by $y=0.008x+347$.

Figure 3

In the ODER process directed edges $(a,b)$ are selected uniformly at random. If $a<b$ in ranking, then the edge $(a,b)$ is added to the network, and otherwise the edge $(b,a)$ is added. (Left) The purple-colored edge $(8,7)$ is chosen at random. (Right) Since $8>7$ the edge $(7,8)$ is added in the right image.

Figure 4

In the C-ODER process three random nodes $a<b<c$ are selected, and either the edge $e_1:=(a,b)$ or the edge $e_2:=(b,c)$ is added to the network. If $b-a<c-b$ we add $e_1$, and otherwise we add $e_2$. In the image above the edge $e_2$ will be selected. Regardless of the particular values of $a,b,$ and $c$, since $a<b<c$ it follows that $c-a>b-a$ and $c-a>c-b$, so the edge $(a,c)$ will never be selected. In the figure $a=0$, $b=3$, and $c=5$. Since $5-3<3-0$. the edge $e_2:=(3,5)$ is added instead of the edge $e_1:=(0,3)$.

Figure 5

The ODER process over ten different runs of ${10}^6$ node networks. Behavior varies greatly in different trials, and so it is not clear whether explosive percolation occurs. In particular, the analysis in Sec. 6 suggests that the initial emergence of a giant SCC may be discontinuous.

Figure 6

Illustration of explosive percolation (discontinuous jump) with the C-ODER process over ten different runs of ${10}^6$ node networks.

Figure 7

The maximum jump in the size of the largest strongly connected component resulting from the addition of a single edge averaged over 40 runs. As system sizes increases, the size of the jump remains constant. (Top) In the C-ODER process, there is a large jump about $1/3$ of the system size in magnitude. (Bottom) In the ODER process, there is a smaller jump about $5\%$ of the system size in magnitude.

Figure 8

The three largest strongly connected components from a single run. Here we see that two giant strongly connected components can exist simultaneously until they are merged into a single larger component.

Figure 9

The fractional overlap between the intervals of the two largest strongly connected components in the C-ODER process immediately prior to the largest jump in the size of the largest strongly connected component, averaged over 20 independent trials.