修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

v5.0
搜索
    v5.0

      CELF

      ✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

      概述

      CELF(Cost Effective Lazy Forward,具有成本效益的惰性前向选择)算法可以在一个有传播(污染物、信息、病毒等)行为的网络中选取一些种子节点作为传播源头,以达到影响力最大化(Influence Maximization, IM)的效果。

      CELF算法由Jure Leskovec等人于2007年提出,它改进了传统基于IC模型的贪心(Greedy)算法,利用函数次模性,只在初始时计算所有节点的影响力,之后不再重复计算所有节点的影响力,因此具有更高的成本效益。

      算法的相关资料如下:

      CELF算法的一个典型应用场景是预防流行病爆发,通过选择一小组人进行监测,从而达到在疾病爆发的早期就能发现的效果。

      基本概念

      传播函数—IC模型

      本算法采用独立级联(Independent Cascade, IC)模型来模拟网络中的影响传播过程。IC模型是一种概率型传播模型,它从一批初始被激活的种子节点集合开始,在第k轮:

      • 只有在第k-1轮被激活的节点在第k轮具备激活能力,它们以一定的概率各自尝试激活每个尚未被激活的出边邻居节点。
      • 当图中剩余具备激活能力的节点数为0时,传播过程结束。

      传播结束时,图中被激活的节点总数就可以衡量种子集合的影响力。为了排除模拟结果的随机性,我们模拟大量次数,然后对所有结果取平均值,这种方法称为蒙特卡罗模拟(Monte-Carlo Simulation)。

      次模性

      传播函数IC()具有次模性(Submodular,又称子模性),这是指对于一个节点v,它的边际效益(Marginal Gain)随着种子集合S的增大而递减:

      其中种子集合|Sk+1|>|Sk|,S∪{v}表示将节点v加入种子集合。

      CELF算法正是利用了传播函数的次模性对传统的贪心算法进行了改进,省去了大量的重复计算从而算地更快,但结果仍接近最优。

      惰性前向选择

      CELF算法在初始时与贪心算法一样,要计算每个节点的影响力,然后根据影响力大小进行降序排列。由于此时种子集合为空,每个节点的影响力可以被视为各自的初始边际效益。

      在第一轮迭代中,将列表最顶部的节点移至种子集合。

      下一轮迭代中,只重新计算最顶部节点的边际效益。排序后,如果该节点仍位于最顶部,就可将其移至种子集合;如果不是,重新计算最顶部节点的边际效益并进行排序。

      与贪心算法不同,在每轮迭代中,CELF不计算所有剩余节点的边际效益,这就是在利用传播函数的次模性——所有节点在本轮的边际效益只会比上一轮小。因此,如果计算的节点仍处于最顶部,就可以直接将其放入种子集合,无需计算其他节点。

      当种子集合达到规定大小时,算法停止。

      语法

      • 命令:algo(celf)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      seedSetSize int >0 1 种子节点的个数
      monteCarloSimulations int >0 1000 蒙特卡罗模拟次数
      propagationProbability float (0,1) 0.1 本轮有激活能力的节点成功激活每个出边邻居的概率

      示例

      示例图如下:

      文件回写

      配置项 回写内容
      描述
      filename _id,spread 点及其加入种子集合时的边际效益
      algo(celf).params({
        seedSetSize: 3,
        monteCarloSimulations: 1000,
        propagationProbability: 0.5 
      }).write({
        file:{
          filename: 'seeds'
        }
      })
      

      结果:文件seeds

      I,4.687
      D,1.261
      X,1
      

      直接返回

      别名序号 类型
      描述
      列名
      0 []perNode 点及其加入种子集合时的边际效益 _uuid, spread
      algo(celf).params({
        seedSetSize: 2,
        monteCarloSimulations: 1000,
        propagationProbability: 0.6 
      }) as seeds
      return seeds
      

      结果:seeds

      _uuid spread
      9 5.345
      4 1.262

      流式返回

      别名序号 类型
      描述
      列名
      0 []perNode 点及其加入种子集合时的边际效益 _uuid, spread
      algo(celf).params({
        seedSetSize: 3,
        monteCarloSimulations: 1000,
        propagationProbability: 0.6 
      }).stream() as seeds
      find().nodes({_uuid == seeds._uuid}) as nodes
      return table(nodes._id, nodes.createdOn, seeds.spread)
      

      结果:table(nodes._id, nodes.createdOn, seeds.spread)

      nodes._id nodes.createdOn seeds.spread
      I 2018-12-13 00:00:00 5.345
      D 2019-01-16 00:00:00 1.262
      X 2022-06-13 00:00:00 1
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写