影响力最大化-独立级联 (IC)模型+贪心算法(python代码)

盼盼    2020-03-01 09:42

贪心
(1)首先|S|=1,在所有点中选一个在IC模型下跑出感染的点数量最多的点加入S
(此时跑了n趟IC)
(2)再在剩下的点中选一个加入S后结果最好的点加入S
(此时跑了n-1趟IC)
(3)重复2,直到能S扩散的结果能覆盖所有点

IC
(1)激活S中的所有节点,加入活集A(本轮被激活的所有点)
(2)找到A的非活邻居集N(可能被传染的所有点),对于N中的每一个点,被传染的概率都为1-(1-Pa1,n)*(1-Pa2,n)…。
(3)清空A
(4)标记所有被传染的点,并放入A
(4)重复2、3直到步骤2已经不能找到新点
 
Last Modified: 2020-03-01 09:42
Views: 5.5K

[[total]] comments

Post your comment
  1. [[item.time]]
    [[item.user.username]] [[item.floor]]Floor
  2. Click to load more...
  3. Post your comment