网络成长中的选择力量

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
“选择的力量”已经被证明从根本上改变了许多随机化算法的行为。在这里，我们探讨选择对树和网络增长模型的影响。在我们的模型中，每个新节点有k个随机选择的联系人，其中k>1是一个常数。然后，在某种意义上，它依附于这些接触中的任何一个最理想的接触，例如它与根的距离或它的度。即使当新节点只有两个选择时，即当k=2时，所得到的网络可能与随机图或树非常不同。例如，如果新节点附着在最接近树根的接触处，则深度分布由泊松解变为行波解。如果新节点以最小的度附着在接触点上，则度分布比在随机图中更接近均匀，因此网络中极有可能不存在度大于O（log log N）的节点。最后，如果新结点以最大的度附着在接触上，我们发现度分布是指数为-1的幂律，直到大致等于k的度，超过该度时有指数截止；因此，在这种情况下，我们需要k>>1才能看到一个在很宽的度数范围内的幂律。
---
英文标题：
《The power of choice in network growth》
---
作者：
Raissa M. D'Souza, Paul L. Krapivsky, Cristopher Moore
---
最新提交年份：
2007
---
分类信息：

一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--

---
英文摘要：
  The "power of choice" has been shown to radically alter the behavior of a number of randomized algorithms. Here we explore the effects of choice on models of tree and network growth. In our models each new node has k randomly chosen contacts, where k > 1 is a constant. It then attaches to whichever one of these contacts is most desirable in some sense, such as its distance from the root or its degree. Even when the new node has just two choices, i.e., when k=2, the resulting network can be very different from a random graph or tree. For instance, if the new node attaches to the contact which is closest to the root of the tree, the distribution of depths changes from Poisson to a traveling wave solution. If the new node attaches to the contact with the smallest degree, the degree distribution is closer to uniform than in a random graph, so that with high probability there are no nodes in the network with degree greater than O(log log N). Finally, if the new node attaches to the contact with the largest degree, we find that the degree distribution is a power law with exponent -1 up to degrees roughly equal to k, with an exponential cutoff beyond that; thus, in this case, we need k >> 1 to see a power law over a wide range of degrees.
---
PDF链接：
https://arxiv.org/pdf/704.1882

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：distribution Probability Transitions Exponential equilibrium attaches 接触 growth 指数 发现