Title: Explosive Percolation on Directed Networks Due to Monotonic Flow of Activity,
Abstract: An important class of real-world networks have 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.