Achlioptas Dimitris, D'Souza Raissa M, Spencer Joel
Department of Computer Science, University of California at Santa Cruz, Santa Cruz, CA 95064, USA.
Science. 2009 Mar 13;323(5920):1453-5. doi: 10.1126/science.1167782.
Networks in which the formation of connections is governed by a random process often undergo a percolation transition, wherein around a critical point, the addition of a small number of connections causes a sizable fraction of the network to suddenly become linked together. Typically such transitions are continuous, so that the percentage of the network linked together tends to zero right above the transition point. Whether percolation transitions could be discontinuous has been an open question. Here, we show that incorporating a limited amount of choice in the classic Erdös-Rényi network formation model causes its percolation transition to become discontinuous.
连接形成由随机过程控制的网络通常会经历渗流转变，即在临界点附近，添加少量连接会导致网络中相当大一部分突然连接在一起。通常这种转变是连续的，以至于在转变点之上，连接在一起的网络百分比趋于零。渗流转变是否可能是不连续的一直是一个悬而未决的问题。在这里，我们表明在经典的厄多斯 - 雷尼网络形成模型中纳入有限量的选择会使其渗流转变变得不连续。
