社区识别与传播类算法

网页排名(Page Rank)

算法 Page Rank 是在有向图中,将点的分值沿有向边的方向进行传递,直至得到收敛的分值分布的一种迭代算法。最早主要用于通过网页之间的关系,来计算网页的重要性,从而为搜索结果提供排名依据。随着技术的发展与大量关联性数据的产生,Page Rank 的使用被衍生到了众多领域。

在每次迭代中,节点的当前分值会被平均分配给与该节点的出边相连的邻居节点,同时该节点会收到与其入边相连的邻居节点传来的分值,将这些收到的分值相加即为该节点在本轮迭代中的得分:

其中,N 为当前节点 x 的入边邻居集合,d 为节点的出度。由于上式对入度为零的节点会给出 0 分的计算结果,故引入阻尼系数 q 使这种入度为零的点可以得到 1-q 分,表示在真实的互联网环境中那些没有有效外链的站点仍然有 1-q 的概率会给访问到:

由于 Page Rank 的计算涉及到全图数据,因此会以任务的方式执行。

Page Rank 的[命令]为:algo(page_rank)

Page Rank 的[配置]为:

名称 类型 规范 描述
init_value float / 初始分值,不设置则为0.2
loop_num int > 0, 必填 算法迭代的次数
damping float >0, <1,必填 阻尼系数,即用户继续停留在当前页面进行浏览的概率,一般取0.85
limit int >0或-1,必填 需要返回的结果的条数,-1表示返回所有结果
order string ASC,DESC 对返回结果进行排序,不设置则不排序

示例,执行 page rank, 设置迭代次数为 5,阻尼 0.8,默认分值为 1, 并回写到点属性

algo(page_rank)
  .params({ loop_num: 5, damping: 0.8, init_value: 1, limit: -1 })
  .write_back();

在 Ultipa-CLI 中任务信息如下图所示:

示例:查看点(age=20) 的 Page Rank 值, 并返回 3 条结果

西比尔识别(Sybil Rank)

Sybil 原指在线社交网络 OSN 中的虚假账号。由于社交网络的飞速发展,来自 Sybil 的攻击日益增多。通过 Sybil Rank 算法,可以帮助社交平台或相关企业更高效的定位虚假账号(点)。

Sybil Rank 的[命令]为:algo(sybil_rank)

Sybil Rank 的[配置]为:

名称 类型 规范 描述
loop_num int > 0, 必填 算法轮询的次数
sybil_num int > 0, 必填 返回多少个最可疑的顶点
trust_seeds id[] 必填 传入可信的点
total_trust int 必填 设置最多可信点数量

示例:计算 sybil rank ,轮询 5 次,返回 10 个最可疑的点

algo(sybil_rank).params({
loop_num: 2,
sybil_num: 10,
trust_seeds: [63342,12324,52356,18974,9634,34,8076,…],
total_trust: 100
})

标签传播算法 (Label Propagation)

标签传播是一套将图中现有标签(节点某一属性的值)进行传播并达到稳定,从而对节点按照标签进行分类的迭代过程。在每次迭代中,节点将获得其邻居中权重最大的标签值:

其中,N 是当前节点 x 的邻居集合,nw 是某邻居点的权重,ew 是该邻居与当前节点 x 之间的边的权重,(nw·ew)即为该邻居的标签的权重,将每个邻居的标签权重按照标签值进行分组求和,最大的权重和值所对应的标签值即为当前节点 x 在本轮迭代中获得的标签值。

注意:LPA 算法中的邻居是基于当前节点的每一条边找到的邻居,即通过多条边找到的同一邻居无需去重;对于含有自环(指向自己的边)的节点,该节点自身也作为邻居参与权重计算,且每一个自环对应两个该节点(自环被视为两条边,一条出边和一条入边)。

LPA 算法拥有着广泛的应用场景,如:虚拟社区挖掘,多媒体信息分类等。

标签传播算法的 [命令] 为:algo(lpa)

标签传播算法的 [配置] 为:

名称 类型 规范 描述
loop_num int > 0, 必填 传播算法迭代次数
node_property_name string / 标签所在的属性名称
node_weight_name string / 点权重所在的属性名称,属性类型为数值,不设置则权重为1
edge_weight_name string / 边权重所在的属性名称,属性类型为数值,不设置则权重为1

示例:运行全图标签传播算法,迭代次数设为 5,标签所在属性设为 type

algo(lpa).params({ loop_num: 5, node_property_name: "type" });

HANP (Hop Attenuation & Node Preference)

HANP 是 LPA 算法的扩展,在计算标签权重时考虑了标签的活性和邻居节点的度。HANP 算法在每轮迭代中给某节点计算出的标签值为:

其中,N 仍是当前节点 x 的邻居集合(多条边的共同邻居不去重,双倍自环数量的当前节点),s 是体现某邻居 y 的标签活性的分值,(s+|s|)/2 表示只有当分值大于零时该邻居才参与权重计算,d 为该邻居的度,d 的指数 m 的正负号体现选择标签时对邻居的度的偏向性,ew 为该邻居与当前节点 x 之间的边的权重。

HANP 算法在迭代开始时将所有点的标签分值设置为1,每次迭代,将邻居中所有被选中的标签的最高分值进行衰减,并传递给当前节点:

其中,N' 为当前节点 x 的邻居中,标签值被选中的邻居集合,δ 为标签活性的衰减因子。由于只有分值大于零的节点标签会参与权重计算和传递,对于初始值为1的分值,标签的最大传递步数为 1/δ。有些算法(比如定制化产品)在新标签与当前节点本来的标签相同时,不对新的标签分值进行衰减,从而延长标签的活性。

HANP 的[命令]为: algo(hanp)

HANP 的[配置]为:

名称 类型 规范 描述
loop_num int > 0, 必填 算法的迭代次数
edge_property_name string 必填 作为权重的边属性名称,属性类型为数值
node_property_name string 必填 标签所在的点属性名称
m float 必填 邻居节点度的幂的指数,表示对邻居节点的度的偏向性:
m=0:不考虑邻居的节点度
m>0:偏向节点度高的邻居
m>0:偏向节点度低的邻居
delta float >=0,必填 传播中标签活性的衰减因子
值越大衰减的越快,能传递的次数越少

鲁汶社区识别算法 (Louvain)

Louvain 算法是基于模块度(modularity)的社区识别算法,是以最大化模块度为目标的一种对点进行聚类的迭代过程。模块度反应了社区内部节点的联系相对于社区间节点的联系的紧密程度,模块度越高,社区划分越明显。在无向图中,模块度的定义可以表示为:

其中,ij 是无向图中任意两点;当 ij 不相同时,Aij 之间边的权重和,且有 Aij = Aji,当 ij 是同一点时,A 为该点自环的权重和(每个自环算两条边);k 是某点的所有自环及邻边的权重和,也称该点的权重度;m 是图中所有点的权重度的和的一半;C 是某点所属的社区,当 ij 属于同一社区时 δ 为 1,否则 δ 为 0。

如果 ij 属于同一社区,上式中 k·k 求和后则表示社区中所有点的权重度的和的平方,将社区中所有点的权重度的和称为社区的权重度,记作 Σtot,而上式中 A 求和后表示社区的权重度减去从社区内节点连接社区外节点的边的权重和,称为社区的内部权重度,记作 Σin。上式可改写为:

如果一个点 i 从其当前所属社区 a 转移到另一社区 b ,则会产生模块度增益 ΔQ

其中,社区 ab 不包含节点 ik(i) 为节点 i 的权重度,k(i,in) 为节点 i 与社区 a(或 b)之间的边的权重和的2倍。通过上式可以快速判断出一个节点的社区归属改变时对模块度的影响。

对于 i 原本不属于任何社区的情况,模块度增益的计算可简化为:

鲁汶算法是一种多轮复合式迭代算法,每轮大循环可划分为两个阶段:

第一阶段是一个迭代过程,在该阶段的一开始将每个点看作一个单独的社区;在每一轮迭代中,为每个点计算是否能够找到一个它的邻居所在的社区,如果将该点分配过去能够产生最大且为正的 ΔQ;全部计算完毕后,把能找到这样的社区的点分配到相应的社区中。第一阶段按此规则循环迭代直至没有点被可以被重新分配,或迭代次数达到限制。

第二阶段是一个图压缩过程,将第一阶段划分的每个社区压缩为一个新节点;将每个社区内部的边压缩为其新节点的一个自环,权重为该社区的内部权重度的一半,即 Σin/2;将任意两个社区之间的边压缩为其两个新节点之间的一条边,权重为这些边的权重和。如果压缩后的新图与本轮大循环开始时的图一致,即模块度无法再进一步提升,则算法结束,否则将新图作为下一轮大循环的初始图。

注意:在图压缩的过程中,模块度计算式中的 m 是保持不变的,压缩前后的模块度数值也和压缩前的一致。

Ultipa提供的鲁汶算法将图集看成无向图,并按照上述过程计算每个点的所属社区 id 以及最终模块度的值。写回到点属性当中,且将最终的模块化值存于任务信息当中,除此之外,还将生成一个结果文件,用于记录每个社区的点的个数。

鲁汶算法的 [命令] 为:algo(louvain)

鲁汶算法的 [配置] 为:

名称 类型 规范 描述
phase1_loop_num int >0, 必填 算法第一阶段中的迭代次数
min_modularity_increase float >0, 必填 触发停止的模块度变化的阈值
edge_property_name string / 作为权值的边的属性名称,属性类型为数值,不填则权值为1

注:Ultipa 的 Louvain 算法提供了高并发、超高性能实现,虽然以任务的方式异步执行,但是在千万量级的点-边的中等大小的图中可以实现实时完成。 在不同场景下,Ultipa Louvain 的性能是 Python networkX 执行效率的 1000 倍以上!!!

示例 1:运行 louvain,设置停止的模块化阈值为 0.01, 轮询次数为 5

algo(louvain).params({ phase1_loop_num: 5, min_modularity_increase: 0.01 });

在 Ultipa-CLI 中,运行示例 1 的任务结果为:

鲁汶算法可视化

鲁汶算法可视化以鲁汶算法的执行为前提,从算法结果中获取全部数据、或抽样进行数据展示。由于数据集的大小,louvain 算法可视化通常通过抽样组装的方式进行。

鲁汶算法可视化的 [命令] 为:algo_dv(louvain)

名称 类型 规范 描述
top int (0,10] 选取前 N 大社区
total int (0,10000] 设置抽样点的总数

Step 1: 运行鲁汶算法,使用visualization()预处理可视化所需的数据,并获取 task_id:

algo(louvain)
  .params({ phase1_loop_num: 5, min_modularity_increase: 0.01 })
  .visualization();

Step 2: 用上一步获得的 task_id 获取可视化数据

algo_dv(louvain).params({top: 3, total: 5000}).id(<task_id>)

注:algo_dv() 中填写的算法名一定要和 task_id 对应的任务中的算法名一致

在 Ultipa Manager 当中,高性能可视化的展示如下: