admin管理员组

文章数量:1530084

CELF(Cost-Effective Lazy Forward selection)算法解析
  

  引言：在社交网络影响力最大化问题的求解过程中，我们往往需要去选择一些目标种子结点作为信息初始传播的源头。贪婪算法在传播效果上的解决可以达到影响的最大化，但是在时间复杂度上面显得确十分糟糕。为此CELF算法应势而生，CELF算法利用了函数次模性的特点，在第一轮选择种子结点时，计算网络中所有节点的边际收益，但将在之后的过程中，不再做网络节点边际收益的重复计算，这相对于传统的贪婪算法，将在时间上得到非常明显的改善。本文是对论文《Cost-effective Outbreak Detection in Networks》的补充，如果你是看了这篇论文之后，依然不明白CELF算法，那么本文可能会给予你一点点启示。

一.函数的次模性（submodular)

  对于函数次模性的理解，举个例子，当我们在饿了的时候，吃一碗饭得到的满足感，是比饱腹的时候得到的更多，函数次模性数学解释如下：

图1 函数的次模性

  图中的 R ( ) R() R()函数，我们可以看作是一个收益函数，因为在原文中的解释相对稍微复杂，我就用另一个例子来说明。图1中的A和B看作是选好的种子集， R ( ) R() R()可以看作是A,B种子集在网络中影响到的非种子结点的数量！次模性的意思就是，当

本文标签： 惰性算法前向效益成本

版权声明：本文标题：CELF(Cost-Effective Lazy Forward selection)具有成本效益的惰性前向选择算法 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1726481335a1072604.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。