用一个例子说明如下:
问题描述如下:从一组节点中,取出一组k个种子节点S,使得产生的增益最大。
对任意的a属于A,f(a):a加入之后的增益。
有如下一个表:
初始扫描情况,第0轮,各个节点产生的增益情况。(用优先队列存储)
1>.,取出第一行a1 ,10,0因为此时是第0轮,0==0
加入S,因为第0轮加入a1时候增益最大。
此时表如下:
2>此时再取出首行,为 a2 ,7,0
因为行数为0,而此时是第一轮,0!=1,所以得计算将a2加入s后的增益,
因为:f(a2)=f(a2+空)-f(空)=7>=f(a2+s)-f(s)
因为子模性质,所以将a2加入S后的增益肯定小于7,假设是6,则变为如下:
此时将第一行取出,a2 ,6,1因为1==1,而且后面的将a3加入s的增益肯定少于5,所以后面的不用计算了。
3>一次这样下去,直到选出k个种子集合来为止。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)