数据分析之图算法: 基于Spark和Neo4j

社团发现算法

｜

117

解释如下。

•

u

和

v

都是节点。

•

m

是整个图的关系总权重（在模块度公式中，

2

m

是归一化的常用取值）。

•

A

2

uv

uv

kk

m

−

是

u

和

v

间关系强度与将网络各节点随机分配的预期值（趋于平均值）的比

较值。

–

A

uv

是

u

和

v

间关系的权重。

–

k

u

是

u

的关系权重和。

–

k

v

是

v

的关系权重和。

•

如果

u

和

v

被分配到同一社团中，则

δ

(

c

u

,

c

v

)

的值为

1

；如果未在同一社团中，则为

0

。

对第

1

步的另一优化操作是，当把节点移动到另一个群组时，评估模块度的变化情况。

Louvain

模块度算法使用了该公式的一个更复杂的变体，然后确定最佳群组分配情况。

6.6.2

　何时使用

Louvain

模块度算法

Louvain

模块度算法可用于在大型网络中发现社团。因为计算开销大，所以

Louvain

模块

度算法并没有完全采用模块度，而是采用了一个启发式函数。因此，

Louvain

模块度算法

可用于处理标准模块度算法难以处理的大型图。

Louvain

模块度算法对于评估复杂网络的结构也很有帮助，尤其擅长发现多层级结构，比

如可能会发现一个犯罪组织的层级结构。该算法还可以在不同粒度上缩放，在子社团的子

社团内部查找子社团。

示范用例如下。

•

检测网络攻击。

Sunanda Vivek Shanbhaq

在

2016

年的一项研究中使用了

Louvain

模块度

算法，面向网络安全应用探索大规模网络的快速社团检测。一旦发现这些社团，就可以

用它们来检测网络攻击。

•

将文档中共同出现的词汇引入主题建模过程，并基于此从在线社交平台上提取主题。 ...