首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

CELF优化的贪口算法

2013-01-26 
CELF优化的贪心算法用一个例子说明如下:问题描述如下:从一组节点中,取出一组k个种子节点S,使得产生的增益

CELF优化的贪心算法

用一个例子说明如下:

问题描述如下:从一组节点中,取出一组k个种子节点S,使得产生的增益最大。

对任意的a属于A,f(a):a加入之后的增益。

有如下一个表:

CELF优化的贪口算法

初始扫描情况,第0轮,各个节点产生的增益情况。(用优先队列存储)

1>.,取出第一行a1 ,10,0因为此时是第0轮,0==0

加入S,因为第0轮加入a1时候增益最大。

此时表如下:

CELF优化的贪口算法

2>此时再取出首行,为 a2 ,7,0

因为行数为0,而此时是第一轮,0!=1,所以得计算将a2加入s后的增益,

因为:f(a2)=f(a2+空)-f(空)=7>=f(a2+s)-f(s)

因为子模性质,所以将a2加入S后的增益肯定小于7,假设是6,则变为如下:

CELF优化的贪口算法

此时将第一行取出,a2 ,6,1因为1==1,而且后面的将a3加入s的增益肯定少于5,所以后面的不用计算了。

3>一次这样下去,直到选出k个种子集合来为止。

热点排行