修改密码

请输入密码
请输入密码 请输入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

搜索
    中文

      Louvain

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

      概述

      Louvain(鲁汶)是一个广受认可和应用的社区识别算法,由比利时鲁汶大学的 Vincent D. Blondel 等人于 2008 年提出。它以最大化图的模块度(Modularity)为目标进行计算,因其较高的效率和优质的结果而受到欢迎。

      基本概念

      模块度

      模块度(Modularity)是用来评估图的社区划分结果质量的指标,它量化了社区内部边的密度与社区之间边的密度之间的差异。模块度(Q)的定义如下:

      其中,

      • m 是图中所有边的权重之和;
      • Aij 是节点 i 和节点 j 之间边的权重和,且 2m = ∑ijAij
      • ki 是与节点 i 相连的所有边的权重之和;
      • Ci 表示节点 i 所属的社区,当 Ci = Cj 时,δ(Ci, Cj) 为 1,否则为 0。

      上式与下式是等价的:

      其中,

      • in 是社区 C 内部边的权重之和,即社区内部权重度(Intra-community Weight);
      • tot 是与社区 C 中节点相连的边的权重之和,即社区总权重度(Total-community Weight);
      • m 的含义与上面相同,且 2m = ∑c(∑tot)。

      上图中的节点被划分至 3 个社区,以社区 C1 为例:

      • in = Aaa + Aab + Aac + Aad + Aba + Aca + Ada = 1.5 + 1 + 0.5 + 3 + 1 + 0.5 + 3 = 10.5
      • (∑tot)2 = kaka + kakb + kakc + kakd + kbka + kbkb + kbkc + kbkd + kcka + kckb + kckc + kckd + kdka + kdkb + kdkc + kdkd + = (ka + kb + kc + kd)2 = (6 + 2.7 + 2.8 + 3)2 = 14.52

      模块度的取值范围为 -1 到 1。接近 1 的值表示更明显的社区结构,而负值则意味着划分不具有意义。对于连通图,模块度的取值范围为 -0.5 到 1。

      许多流行的社区检测算法,包括 Louvain 算法,都是旨在找到使得模块度最大的社区划分结果。

      Louvain

      初始时,图中的每个节点都被赋予一个不同的社区。Louvain 算法通过多次迭代运行,每次迭代由两个阶段组成:

      第一阶段:模块度优化

      对于每个节点 i,考虑其邻居节点 j,计算将节点 i 从当前社区重新分配到节点 j 所在的社区而产生的模块度增益(ΔQ)。

      然后,当 ΔQ 大于预设的正阈值时,将节点 i 放入使 ΔQ 最大的社区中。如果无法达到预设的增益,节点 i 则留在原来的社区中。

      按顺序将这个过程应用于所有节点,并重复执行,直到没有任何节点的移动可以改善模块度,或者达到最大循环次数,第一阶段完成。

      第二阶段:社区聚合

      在第二阶段进行社区聚合,即用单个聚合节点来代表在第一阶段形成的每个社区。每个聚合节点具有一个自环边,其权重等于社区内部权重。新节点之间边的权重是两个对应社区中节点之间边的权重之和。

      下面是上述示例进行社区聚合后的结果:

      社区聚合减少了图中的节点和边的数量,同时保持局部及全图的权重度不变。聚合后,社区内的节点被视为一个整体,但它们不再是孤立地进行模块度优化,从而实现了分层(迭代)的社区划分效果。

      完成第二阶段后,对聚合后的图进行另一次迭代。迭代会一直进行,直至没有任何变化,达到最大的模块度。

      特殊说明

      • 如果节点 i 存在自环边,在计算 ki 时,自环边的权重只计算一次。
      • Louvain 算法忽略边的方向,按照无向边进行计算。
      • Louvain 算法的输出结果可能会因为节点的考虑顺序不同而有所差异,但这不会对获得的模块度产生很大的影响。

      语法

      • 命令:algo(louvain)
      • 参数:
      名称 类型
      规范
      默认
      可选
      描述
      phase1_loop_num int ≥1 5 每轮迭代的第一阶段的最大循环次数
      min_modularity_increase float [0,1] 0.01 将节点重新分配到另一社区时,需产生的最小模块度增益阈值(ΔQ)
      edge_schema_property []@<schema>?.<property> 数值类型,需 LTE / 用作边权重的边属性;具有多个指定属性的边,其权重为各属性值的和;忽略则所有边的权重为 1
      limit int ≥-1 -1 返回的结果条数,-1 返回所有结果
      order string asc, desc / 按社区中的节点数对结果进行排序(仅在 stream() 执行方式 mode 2 时有效)

      示例

      示例图如下:

      文件回写

      配置项 回写内容 描述
      filename_community_id _id,community_id 节点及其社区号
      filename_ids community_id,_id,_id,... 社区号及其中所有节点的 ID
      filename_num community_id,count 社区号及其节点数
      algo(louvain).params({ 
        phase1_loop_num: 5, 
        min_modularity_increase: 0.1,
        edge_schema_property: 'weight'
      }).write({
        file:{
          filename_community_id: "communityID",
          filename_ids: "ids",
          filename_num: "num"
        }
      })
      

      统计值:community_count = 4, modularity = 0.464280
      结果:文件 communityID、ids、num

      M,2
      N,2
      K,2
      L,2
      J,8
      I,8
      G,13
      H,8
      F,8
      C,12
      E,12
      D,12
      A,12
      B,13
      

      8,J,I,H,F,
      12,C,E,D,A,
      2,M,N,K,L,
      13,G,B,
      

      8,4
      12,4
      2,4
      13,2
      

      属性回写

      配置项 回写内容 类型 数据类型
      property community_id 点属性 uint32
      algo(louvain).params({ 
        phase1_loop_num: 5, 
        min_modularity_increase: 0.1,
        edge_schema_property: 'weight'
      }).write({
        db:{
          property: "communityID"
        }
      })
      

      统计值:community_count = 4, modularity = 0.464280
      结果:每个节点的社区号回写至名为 communityID 的点属性下

      统计回写

      algo(louvain).params({ 
        phase1_loop_num: 5, 
        min_modularity_increase: 0.1,
        edge_schema_property: 'weight'
      }).write()
      

      统计值:community_count = 4, modularity = 0.464280

      直接返回

      别名序号
      类型
      描述 列名
      0 []perNode 点及其社区号 _uuid, community_id
      1 KV 社区数量,模块度 community_count, modularity
      algo(louvain).params({ 
        phase1_loop_num: 6, 
        min_modularity_increase: 0.5,
        edge_schema_property: 'weight'
      }) as results, stats
      return results, stats
      

      结果:results 和 stats

      _uuid community_id
      13 2
      14 2
      11 2
      12 2
      10 8
      9 8
      7 13
      8 8
      6 8
      3 12
      5 12
      4 12
      1 12
      2 13
      community_count modularity
      4 0.46428

      流式返回

      配置项 参数 别名序号 类型 描述 列名
      mode 1 或忽略 0 []perNode 点及其社区号 _uuid, community_id
      2 []perCommunity 社区及其节点数 community_id, count
      algo(louvain).params({ 
        phase1_loop_num: 6, 
        min_modularity_increase: 0.5,
        edge_schema_property: 'weight'
      }).stream() as results
      group by results.community_id
      return table(results.community_id, max(results._uuid))
      

      结果:table(results.community_id, max(results._uuid))

      results.community_id max(results._uuid)
      12 5
      13 7
      2 14
      8 10
      algo(louvain).params({ 
        phase1_loop_num: 5, 
        min_modularity_increase: 0.1,
        order: "desc"
      }).stream({
        mode: 2
      }) as results
      return results
      

      结果:results

      community_id count
      8 4
      12 4
      2 4
      13 2

      统计返回

      别名序号
      类型
      描述 列名
      0 KV 社区数量,模块度 community_count, modularity
      algo(louvain).params({ 
        phase1_loop_num: 5, 
        min_modularity_increase: 0.1
      }).stats() as stats
      return stats
      

      结果:stats

      community_count modularity
      4 0.397778

      算法效率

      Louvain 算法通过优化的贪心算法实现了比之前的社区检测算法更低的时间复杂度,通常认为是 O(N*logN),其中 N 是图中节点的数量,其结果也更直观。例如,在一个包含 10,000 个节点的图中,Louvain 算法的复杂度大约是 O(40000);在一个包含 1 亿节点的连通图中,算法的复杂度大约是 O(800000000)。

      然而,仔细观察算法的过程,我们会发现,Louvain 算法的复杂度不仅取决于节点的数量,还取决于边的数量。粗略地说,可以近似为 O(N * E/N) = O(E),其中 E 是图中边的数量。这是因为 Louvain 算法的主要逻辑是计算连接到每个节点的边的权重。

      下表显示了 Clauset, Newman and Moore、Pons and Latapy、Wakita and Tsurumi 以及 Louvain 这几个社区检测算法在不同大小的图上的性能差异。对于每个算法/网络,它给出了获得的模块度和计算时间,空记录表示计算时间超过了 24 小时。可以清楚地看到,Louvain 算法在模块度和效率方面取得了显著的(指数级)提升。

      系统架构和编程语言的选择对 Louvain 算法的效率和最终结果都会产生影响。例如,用 Python 串行实现的 Louvain 算法可能需要数小时来处理约 1 万个节点的小图。此外,所使用的数据结构也会影响性能,因为该算法会频繁计算节点度和边的权重。

      原生 Louvain 算法采用 C++,但是它是串行实现的。通过尽可能多地使用并行计算,可以减少时间消耗,从而提高算法的效率。

      对于中等规模包含数千万个节点和边的图集,Ultipa 的 Louvain 算法可以实时完成。对于包含超过 1 亿个节点和边的大图,可以在几秒钟到几分钟内完成。此外,Louvain 算法的效率还受到其他因素的影响,例如数据是否写回到数据库属性或磁盘文件。这些操作会影响算法的整体计算时间。

      这是 Louvain 算法在包含 500 万个节点和 1 亿条边的图上运行的模块性和执行时间记录。计算过程大约需要 1 分钟,而其他额外的操作,比如写回到数据库或生成磁盘文件,会增加约 1 分钟的执行时间。

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