Waagen Alex, D'Souza Raissa M, Lu Tsai-Ching
HRL Laboratories, LLC., 3011 Malibu Canyon Rd., Malibu, California 90265, USA.
Department of Computer Science, University of California, Davis, California 95616, USA.
Phys Rev E. 2017 Jul;96(1-1):012317. doi: 10.1103/PhysRevE.96.012317. Epub 2017 Jul 20.
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.
现实世界中的一类重要网络具有有向边，此外，节点上还有某种排名顺序，例如在线社交网络中用户的受欢迎程度。然而，几乎所有与爆发性渗流相关的研究都局限于无向网络。此外，在这种有排名顺序的网络中，信息通常从排名较高的个体流向排名较低的个体，比如推特上的关注关系、回复和转发。在此，我们在一个有序的有向网络上引入一种简单的渗流过程，其中边是相对于排名顺序单调添加的。我们用数值方法表明，一个占主导地位的强连通分量的出现似乎是不连续的。与大多数渗流过程相比，大规模连通性在非常高的密度下出现，而且这不仅适用于强连通分量结构，也适用于弱连通分量结构。我们用分支过程进行分析，这解释了这种不寻常的行为，并为潜在机制提供了基本的直观理解。我们还表明，在占主导地位的强连通分量出现之前，可能同时存在多个巨大的强连通分量。通过添加一个带有小偏差的竞争渗流规则来连接相似排名的节点，我们表明这会导致形成两个不同的分量，一个是高排名用户的分量，一个是低排名用户的分量，两个分量之间几乎没有信息流。
