Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks
Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks
复制标题
优先附着网络中改进的度界和全谱幂律
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
C. Avin;Zvi Lotker;Yinon Nahum;D. Peleg
考虑一个随机偏好连接模型G（p），它允许节点和边同时到达。从一个任意的非空图G 0开始，在每个时间步，有两个可能的事件：概率p > 0，一个新节点到达，并且在新节点和现有节点之间添加一条新边;概率1 - p，在两个现有节点之间添加一条新边。在这两种情况下，所涉及的现有节点是根据优先连接随机选择的，即，概率与其程度成正比。已知G（p）生成幂律网络，即，度为k的节点的比例与k-β成比例。这里β=（4-p）/（2-p）在范围（2，3]内。通过将时间t时度为k的节点数表示为k，t，我们显著改进了一些长期存在的结果。特别地，我们证明了k，t集中在其平均值附近，偏差为O（k，t），这与k无关。我们还严格约束期望Emk，t，其加性误差为O（1/k），这与t无关。这些新的界限使我们能够在比以前大得多的k值下紧密地估计k，t。这反过来又使我们能够估计其他重要的数量，例如，k-丰富俱乐部的大小，即度至少为k的所有节点的集合。最后，我们引入了一个新的广义模型，G（pt，rt，qt），它通过允许节点和边缘到达的时变概率以及新组件的形成来扩展G（p）。我们证明了扩展模型可以产生指数β在（1，∞）范围内的幂律网络.此外，在G（p）中建立的浓度界限也适用于G（pt，rt，qt）。
Consider a random preferential attachment model G(p) for network evolution that allows both node and edge arrivals. Starting with an arbitrary nonempty graph G0, at each time step, there are two possible events: with probability p > 0 a new node arrives and a new edge is added between the new node and an existing node, and with probability 1 - p a new edge is added between two existing nodes. In both cases, the involved existing nodes are chosen at random according to preferential attachment, i.e., with probability proportional to their degree. G(p) is known to generate power law networks, i.e., the fraction of nodes with degree k is proportional to k-β. Here β=(4-p)/(2-p) is in the range (2,3]. Denoting the number of nodes of degree k at time t by mk,t, we significantly improve some long-standing results. In particular, we show that mk,t is concentrated around its mean with a deviation of O(√t), which is independent of k. We also tightly bound the expectation Emk,t with an additive error of O(1/k), which is independent of t. These new bounds allow us to tightly estimate mk,t for a considerably larger k values than before. This, in turn, enables us to estimate other important quantities, e.g., the size of the k-rich club, namely, the set of all nodes with a degree at least k. Finally, we introduce a new generalized model, G(pt, rt, qt), which extends G(p) by allowing also time-varying probabilities for node and edge arrivals, as well as the formation of new components. We show that the extended model can produce power law networks with any exponent β in the range (1,∞). Furthermore, the concentration bounds established for mk,t in G(p) also apply in G(pt, rt, qt).