图 书 馆
网络中基于距离的影响：计算与最大化Distance-Based Influence in Networks: Computation and Maximization |
|
| 课程网址: | https://videolectures.net/videos/kdd2016_cohen_influence_in_netwo... |
| 主讲教师: | Edith Cohen |
| 开课单位: | KDD 2016研讨会 |
| 开课时间: | 2016-10-12 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | A premise at a heart of network analysis is that entities in a network derive utilities from their connections. The {\em influence} of a seed set $S$ of nodes is defined as the sum over nodes $j$ of the {\em utility} of $S$ to $j$. {\em Distance-based} utility, which is a decreasing function of the distance from $S$ to $j$, was explored in several successful research threads from social network analysis and economics: Network formation games [Bloch and Jackson 2007], Reachability-based influence [Richardson and Domingos 2002; Kempe et al. 2003]; ``threshold'' influence [Gomez-Rodriguez et al. 2011]; and {\em closeness centrality} [Bavelas 1948]. We formulate a model that unifies and extends this previous work and address the two fundamental computational problems in this domain: {\em Influence oracles} and {\em influence maximization} (IM). An oracle performs some preprocessing, after which influence queries for arbitrary seed sets can be efficiently computed. With IM, we seek a set of nodes of a given size with maximum influence. Since the IM problem is computationally hard, we instead seek a {\em greedy sequence} of nodes, with each prefix having influence that is at least $1-1/e$ of that of the optimal seed set of the same size. We present the first highly scalable algorithms for both problems, providing statistical guarantees on approximation quality and near-linear worst-case bounds on the computation. We perform an experimental evaluation which demonstrates the effectiveness of our designs on networks with hundreds of millions of edges. |
| 关 键 词: | 网络分析; 基本计算问题; 最佳种子集 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-01-07：liyq |
| 最后编审: | 2025-01-07：liyq |
| 阅读次数: | 12 |