3.3.2　图计算

图计算（Graph Computing）是以关联图谱为基础引申出来的一类算法的统称，主要解决了图数据模型的表示和计算问题。图计算是目前比较热门的一个研究方向，比较成熟的应用场景有社区发现、标签传播、图嵌入等。社区发现（Communication Detection）主要用于关联图中社区的划分，与聚类算法的目标类似，我们也希望社区划分后每个社区内部节点联系密切，而社区之间的连接较为稀疏，因而这里定义了模块度的概念。简单理解，模块度是社区内部节点的连接边数与随机情况下边数的差，这个差值越大说明社区内部的连接程度越紧密。以最大化全局模块度为学习目标，就有了经典的Louvain算法。Louvain算法在初始化的时候将每个节点看作一个社区，通过分配节点使得相邻社区的模块度增益最大，直至所有社区不再变化，之后将生成的社区压缩成一个新的节点，重复上述工作，直至整个图中的模块度不再变化。Louvain在Spark环境下已经实现分布式，因而可以较好地支持工业界的需求。

标签传播（Label Propagation Algorithm，LPA）是一种基于关联图的半监督学习方法，利用已标记的样本来推论未标记的样本。标签传播算法的核心在于利用节点之间边的权重构建转移矩阵，每轮传播后更新除已标记样本外其他样本的标签，直至所有样本的标签收敛。标签传播算法最大的优势是简单高效，不过也存在结果不稳定等问题。

图嵌入（Graph Embedding）借鉴了NLP中word2vec的思想，将关联图中的节点嵌入某个高维空间中，使得每个节点向量化，并且映射后的向量还能够保留图的结构和性质。图嵌入的方式有很多，例如DeepWalk、Line、node2vec、SDNE等，并没有绝对意义上最优的嵌入方式，需要建模人员根据数据的分布特性和实际业务效果，不断地尝试和迭代。图嵌入后的向量可以表示每个样本的社交属性，既可以作为入模特征放到欺诈或者风险模型中训练，又可以利用聚类算法进行客群间的划分。