图 书 馆
优先附着网络中改进的度界和全谱幂律Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks |
|
| 课程网址: | http://videolectures.net/kdd2017_nahum_attachment_networks/ |
| 主讲教师: | Yinon Nahum |
| 开课单位: | 魏茨曼科学研究所 |
| 开课时间: | 2017-10-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | 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 |
| 阅读次数: | 20 |