修改密码

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

修改昵称

当前昵称:
提交

??certificate-table.title_zh_CN??

??certificate-table.name_zh_CN?? ??certificate-table.issued-at_zh_CN?? ??certificate-table.valid-until_zh_CN?? ??certificate-table.serial_zh_CN?? ??certificate-table.actions_zh_CN??
??certificate-table.serial_zh_CN?? ??certificate-table.valid-until_zh_CN?? ??certificate-table.actions_zh_CN??

??certificate-table.no-data.p1_zh_CN?? ??certificate-table.no-data.p2_zh_CN??

??invoice-table.title_zh_CN??

??invoice-table.name_zh_CN?? ??invoice-table.create-time_zh_CN?? ??invoice-table.id_zh_CN?? ??invoice-table.price_zh_CN?? ??invoice-table.actions_zh_CN??
??invoice-table.name_zh_CN?? ??invoice-table.create-time_zh_CN?? ??invoice-table.id_zh_CN?? ??invoice-table.price_zh_CN?? ??invoice-table.actions_zh_CN??
v4.3
搜索
    中文EN
    v4.3

      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
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写