基于Java设计的影响力最大化模型_java最大影响力问题

影响力最大化问题可以定义为：给定一个社会网络、一个扩散模型和一个数值 k，任务就是如何在社会网络上获取一个规模为 k 的节点集合，使得这个节点集合可以达到影响力最大化的效果。

独立级联模型的算法描述如下：

初始的激活状态节点集合 A。

在 t 时刻，新近被激活的节点 u 对它的邻接节点 v 产生影响，成功的概率为

。若 v 有多个邻居节点都是新近被激活的节点，那么这些节点将以任意顺序尝试激活节点 v。

如果节点 v 被激活成功，那么在 t+1 时刻，节点 v 转为激活状态，将尝试激活其非激活状态的邻居节点；否则，节点 v 在 t+1 时刻状态不发生变化。

该过程不断进行重复，直到网络中不存在有影响力的活跃节点时，传播过程结束。

时刻 1：初始时，3,4,8 为激活状态，其他为未激活状态。每个激活状态节点都会以一定概率去激活自己周围的非激活状态。

时刻 2：节点 5 和 7 在时刻 1 被激活，在时刻 2 变成了激活状态。节点 5 和 7 在时刻 2 以一定概率去激活各自未激活状态的邻居。在时刻 2，节点 3,4,8 已不是新近被激活状态，它们不能再去激活其他节点。

注：每个节点在某个时刻 t 被激活之后，会在 t+1 时刻成为激活状态，它只能在 t+1 这一个时刻有机会去激活其周围邻居节点，之后的时刻将不再激活其他节点。

时刻 3：节点 2 在时刻 2 被激活，在时刻 3 变成了激活状态，它将会在该时刻去激活其周围的邻居节点。

贪心选择策略：

输入：社会网络结构、信息扩散模型和k
输出：拥有最大影响力的节点集合
初始化：；
For  do
    选择出

    End For
    输出S
    End
1
2
3
4
5
6
7
8
9

do
选择出

End For
输出S
End
1
2
3