过程:
SeedNode=[ ] current_inif=0
1.计算所有节点的边际影响力inf (节点n的Δinf=(n加入当前种子集Seeds后形成的新种子集Seeds的影响力)-(当前Seeds的影响力)】)
2.根据影响力对节点进行排序
3.S=S+最大影响力的节点
4.计算下一个节点的最新影响力值,如果该节点的影响力值大于等于该节点下面节点的原影响力值,该节点直接计入S
否则重新计算所有节点影响力并重新排序,选取最大计入S
5.重复4直到 |S|=k
伪代码:
Initialize S and inif[] and S_inif and Q[]
Inif[]=new inif(v)
For v in nodes:
Inif[v]=newinif([v])
Q=nodes sort byinif(nodes)
While S.length <=K
B=Q[0]
Inif[B]=newinif(S+B)-S_inif
If inif[B]>=inif[Q[1]:
S=S+B
S_inif=inif[B]
end if
Else:
For allnodes v not in S:
Inif(v)=new inif(v+S)-S_inif
Q=new Q
S=S+Q.pop()
end else
end while
Ref:
算法原理解释:http://www.cnblogs.com/aaronhoo/p/6548760.html