CELF(Cost-Effective Lazy Forward selection)具有成本效益的惰性前向选择算法

本文主要是介绍CELF(Cost-Effective Lazy Forward selection)具有成本效益的惰性前向选择算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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种子集在网络中影响到的非种子结点的数量!次模性的意思就是,当种子集A比B小的时候,新的种子结点S加入到种子集A和B中, R ( A ∪ R(A\cup R(A{s} ) − R ( A ) )-R(A) )R(A)获得边际收益更大!

二.CELF 算法伪码解读

在这里插入图片描述

图2 CELF算法伪码

  CELF算法的说明:因为算法最主要的是“篮筐处”,我对“篮筐”里面的伪码,做出如下逐行解释:(如果你已经熟悉伪码可以不用看)

  第一行:输入网络结构 g ( V , E ) g(V,E) g(V,E),网络结构 V V V是点的集合, E E E是边的集合;R是收益函数;c是成本函数;B是预算;type就是网络节点成本的类型,原文中有两种类型,UC统一成本(常数),CB非统一成本(会变化的)。

  第二行:最开始种子结点集A为空集;对于每一个V中的结点s,初始化它的边际收益 δ s \delta_{s} δs为无穷大。

  第三行:循环条件为,当把种子结点S加入到种子集A中的时候,成本函数的值c小于等于预算B,然后可以继续循环。循环为后置循环,意思是先循环再判断是否满足循环条件。

  第四行:进入循环体内,对于每一个非种子结点s,我们给它打上flase标签。

  第五行:永久循环,除非第八行运行条件成立退出。

  第六、七行:根据种子结点的成本类型为UC或者CB并进行以边际收益 δ s \delta_{s} δs为选则依据的结点选择(选择边际收益最大的)。

  第八行: 如果找出来的最大边际收益 δ s \delta_{s} δs结点的标签为ture,则加入种子集A,并结束循环,进行下一轮选择。

  第九行:如果找出来的最大边际收益结点的标签为flase,则重新计算边际收益,并改标签为ture。

次模性在CELF中的体现解析
  在第二轮选择种子结点的时候,并没有全部计算所有结点的边际收益(可能计算了部分)

  因为:
在这里插入图片描述

图3 论文截图处“蓝色框部分”给出了解释

  因为第一轮边际收益计算后,排序在顶端的点依然在顶端,只有可能当他们的边际收益很接近的时候,可能在第K(k>1)轮需要多计算几次。另外,如果结点之间的边际收益相隔大,那么之后的计算完全没必要感觉,直接依靠第一轮的边际收益排序来选择就好了!

  这就是相比于贪婪算法时间节省的地方,第一轮时间复杂度是一样的,后面的选择轮数就不需要再去遍历估计那些没有被选为种子结点的结点的边际收益,此处正是次模性的体现(领会)
   该解析如果还是看得不明白,可以参考另一位作者写的,虽然简陋,希望能一起结合论文看,能让你明白!
https://blog.csdn.net/s1102379635/article/details/8524447

这篇关于CELF(Cost-Effective Lazy Forward selection)具有成本效益的惰性前向选择算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/344578

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用(一)延迟Bean的初始化(二)与@Autowired结合使用二、实例解

前端知识点之Javascript选择输入框confirm用法

《前端知识点之Javascript选择输入框confirm用法》:本文主要介绍JavaScript中的confirm方法的基本用法、功能特点、注意事项及常见用途,文中通过代码介绍的非常详细,对大家... 目录1. 基本用法2. 功能特点①阻塞行为:confirm 对话框会阻塞脚本的执行,直到用户作出选择。②

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Python 中 requests 与 aiohttp 在实际项目中的选择策略详解

《Python中requests与aiohttp在实际项目中的选择策略详解》本文主要介绍了Python爬虫开发中常用的两个库requests和aiohttp的使用方法及其区别,通过实际项目案... 目录一、requests 库二、aiohttp 库三、requests 和 aiohttp 的比较四、requ