课程知识复习使用。

图中的社区是指一张图中的一些子图。这些子图内部顶点直接紧密相连，而子图内部节点与外部节点之间连接是稀疏的。社区发现算法是需要找到图中所有的社区，可以分为基于层级聚类的方法和基于边介数的方法。

1. 基于层级聚类的方法

  • 点关联强度：衡量两点间的关联强度。
    • 两点间独立路径数：能够连接两点的所有互不相交(没有公共节点)的简单路径总数，即为割点数目。
    • 全路径融合强度：认为节点间的关联强度与所有路径都相关，路径长度越小，强度越大。
  • 算法流程
    • 选定并计算关联强度
    • 初始化每个顶点为单个社区
    • 定义两个社区的关联强度为其间所有点对的关键强度平均值
    • 每次合并两个关联强度最大的点对，合并关系形成层级关系
    • 聚类质量达到一定程度之后不再继续
  • 衡量标准：模块度，是评估社区结果质量高低的度量方法。模块度Q 计算如下：

$$Q \propto \sum_{s\in S} [ 社区s内部的实际边数 - 社区s内部的期望边数 ] $$

模块度取值范围为[-1,1]，实践中，模块度达到0.3到0.7之间就说明划分质量很好。

不足：对度数低的点的社区分配不友好。例如一个顶点如果只有一条边，则这个顶点理应分配在其唯一邻居所在的社区，然后基于层级聚类的方法中，该点同邻居的关联强度低，很容易被排斥在邻居所属社区之外。

2. 基于边介数的方法

  • 边介数：对于图上的一条边 $e$ 而言，$e$ 的介数是指图中所有点对的最短路径中，要经$e$ 的路径比例总和。
  • 算法流程：
    • 计算所有边的介数
    • 移除介数最高边
    • 重新计算所有边的介数
    • 如果剩余所有边的介数都低于一定阈值则终止，否则回到步骤二

图1

3. 其它社区发现算法：BK,k-clique,k-core

  • 团（完全图）：任意两个节点间都连接有边。

  • 最大团：一个图中顶点数最多的团

  • 极大团：加入任何其它顶点都无法在图中构成更大的完全子图的团

  • BK算法求解极大团：
    图2

  • k-clique算法，允许社区重叠，将发现的社区定义为团联。给定一个大于1的正整数k，由一系列k-团(节点数目为k的团)互相连接形成的子图称为k-团联。
    图3

  • k-core算法：子图是连通的，且每个节点的度数均不小于k。
    图4

4. 社区搜索

社区发现是为了找到图G中所有的社区，然而社区搜索只需找到用户所关心的社区，如找到包含用户输入的查询点/查询点集合的社区。即在图G中找到一个连通子图H，且$f(H)$在所有可能子图的得分函数中值最大。得分函数$f(H)$定义为H中最小的节点度数。

  • 贪心算法
    图5

  • K-Truss算法：K-Truss要求子图H中任意一条边都被包含在至少(k-2)个不同的三角形中。

    • 支持度,$sup(e,G)$：包含e的三⻆形数目
    • 子图 Trussness：子图H中所有边的最小支持度
    • 边 Trussness：边e所在所有子图中最大的子图 Trussness
    • k 分类：图G中所有边 Trussness 为k 的边集合

图6
图7

5. 图划分

图的划分是将图切分为多个不相交的子集，每个子集称为一个分割，并希望各个子图的大小要相对均衡。

图8
图9

KL 算法最大的问题是可扩展性太差，对于大图考虑所有可能的节点置换的时间复杂性太高。一种改进的算法则是METIS 算法: 通过对基于点边的融合来不断压缩原始图，当原图小到一定程度之后，再进行KL 等图分割算法，最后基于分割结果进行原图恢复。

6.参考资料

中国科学院大学邹磊老师，图数据管理与应用课程课件