0


优先附着网络中改进的度界和全谱幂律

Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks
课程网址: http://videolectures.net/kdd2017_nahum_attachment_networks/  
主讲教师: Yinon Nahum
开课单位: 魏茨曼科学研究所
开课时间: 2017-10-09
课程语种: 英语
中文简介:
考虑用于网络演化的随机优先附着模型 $G(p)$，它允许节点和边缘到达。从任意非空图 $G_0$ 开始，在每个时间步，有两个可能的事件：以概率 $p>0$ 到达新节点，并在新节点和现有节点之间添加新边，以概率$1-p$ 在两个现有节点之间添加一条新边。在这两种情况下，所涉及的现有节点都是根据优先连接随机选择的，即概率与其程度成正比。$G(p)$ 已知会生成{\em幂律网络}，即度为 $k$ 的节点比例与 $k^{-\beta}$ 成正比。这里 $\beta=(4-p)/(2-p)$ 在 $(2,3]$ 范围内。 用 $m_{k,t}$ 表示 $t$ 时刻 $k$ 度的节点数量，我们显着改进了一些长期存在的结果。特别是，我们表明 $m_{k,t}$ 集中在其均值附近，偏差为 $O(\sqrt{t})$，与 $k$ 无关。我们还将期望 $\ev{m_{k,t}}$ 与附加误差 $O(1/k)$ 紧密结合，该误差独立于 $t$。这些新界限使我们能够严格估计 $m_{k,t}$ 以获得比以前大得多的 $k$ 值。反过来，这使我们能够估计其他重要的量，例如 $k$-rich 俱乐部的大小，即度数至少为 $k$ 的所有节点的集合。 最后，我们引入了一个新的广义模型 $G(p_t, r_t, q_t)$，它通过允许节点和边到达以及形成的 \emph{时变} 概率来扩展 $G(p)$新组件。我们证明，扩展模型可以生成具有 $(1,\infty)$ 范围内任何指数 $\beta$ 的幂律网络。此外，为 $G(p)$ 中的 $m_{k,t}$ 建立的浓度界限也适用于 $G(p_t, r_t, q_t)$。
课程简介: Consider a random preferential attachment model $G(p)$ for network evolution that allows both node and edge arrivals. Starting with an arbitrary nonempty graph $G_0$, 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 {em power law networks}, i.e., the fraction of nodes with degree $k$ is proportional to $k^{-beta}$. Here $beta=(4-p)/(2-p)$ is in the range $(2,3]$. Denoting the number of nodes of degree $k$ at time $t$ by $m_{k,t}$, we significantly improve some long-standing results. In particular, we show that $m_{k,t}$ is concentrated around its mean with a deviation of $O(sqrt{t})$, which is independent of $k$. We also tightly bound the expectation $ev{m_{k,t}}$ with an additive error of $O(1/k)$, which is independent of $t$. These new bounds allow us to tightly estimate $m_{k,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(p_t, r_t, q_t)$, which extends $G(p)$ by allowing also emph{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 $beta$ in the range $(1,infty)$. Furthermore, the concentration bounds established for $m_{k,t}$ in $G(p)$ also apply in $G(p_t, r_t, q_t)$.
关 键 词: 网络演化; 广义模型; 数据科学
课程来源: 视频讲座网
数据采集: 2023-12-26：wujk
最后编审: 2023-12-26：wujk
阅读次数: 31

纠错/补充/评论/留言
评论/留言 纠错/补充
验证算术题： 8 + 6 =