【自然语言处理NLP】社区发现快速入门（1）https://developer.aliyun.com/article/1541013
五、图分区的比较（指标）
5.1 无监督算法度量指标
- 图聚类算法选择
- 集群的质量
- 稳定性
- 效率（时间空间）
- 其他：不需要指定聚类的数量（k）、集群的层次结构等
- 图聚类是无监督学习，没有明确的目标函数，不同算法使用不同的目标函数。
- 图分割算法度量
- 质量的衡量标准：sim(T,A)，对给定的参考划分（ground truth partition）T计算图A的划分的相似度函数
- 稳定性的衡量标准：sim(A,A′)，同一算法的运行多次比较
- 比较算法之间的结果：sim(A,B)
5.2 图相似度度量指标
- 图无关度量——只看点的信息，不考虑边的影响
- 基于成对计数：考虑对图节点的两个划分，度量指标基于A和B里面各个集群中的成对元素
- Jaccard 指数
- 调整兰德指数（ARI），取值范围是[-1, 1]，-1表示聚类结果完全不一致，0表示聚类结果与随机结果相同，1表示聚类结果完全一致
- 基于信息论：基于 A 和 B 之间的互信息
- 归一化互信息 （NMI），取值范围是[0, 1]，0表示两个聚类结果没有任何相似性，1表示两个聚类结果完全一致。NMI并不受聚类结果的绝对数目影响，而是关注聚类结果之间的相对关系和一致性。
- 基于卡方分布
- Cramer 的 V指标 和 Tschurprow 的 T指标
- 图感知度量——只看边的信息，不考虑点的信息
- AGRI
设网络G 的真实社区情况为 A， 并设 B1 和 B2 分别是 A 的粗化和细化，在某些情况下，在图无关度量下A更接近B2（细化）；在图感知度量下A更接近B1（粗化）
- 当使用图无关的度量时，集群的数量更多
- 图感知度量生成的集群的数量更少
这两种指标都获得高值是我们做图聚类所希望的，但图感知和图无关度量在解决问题方面具有相反的行为（trade-off）。ECG算法可以使两者都达到一个较好的效果。
总结：
- 使用调整后的基于集合的相似性度量，可以减少度量对分区粒度的偏差，消除随机性
- 图无关（ARI，AMI）和图感知（AGRI）度量是互补的，在评估算法的优越性时应同时使用它们
5.3 其他指标
- 拓扑特征
- 缩放密度(scaled density)
- 内部传递性(internal transitivity)
- 社区强度指数CSI（ECG论文中提出的一个指标）：边界（0 和 1）附近的 ECG 权重的双峰分布(bi-modal distribution)表明了强大的社区结构，由此提出了一个基于点质量 Wasserstein 距离（推土机距离（Earth Mover’s distance））的简单社区强度指标 (CSI)
3.异常检测CADA（community-aware anomaly detection社团感知异常检测）对于每个节点 
，令 
：v的邻居数； 
属于出现次数最多社区的邻居数（通过图聚类）。
六、图嵌入
图嵌入Graph Embedding，也叫图表示学习(Network Representation Learning)，其目标是将网络（节点）映射到向量（特征）空间，将相似节点映射到向量空间中的附近位置。
何谓”相似“？
- 图拓扑上较近
- 图中相似的角色（例如：度相似）
- 相似的节点属性
图嵌入的大部分算法基于大部分算法基于随机游走和用于词嵌入的SkipGram方法。
NLP中的SkipGram：使用滑动窗口对每个词上下文的相关词进行组合，构建“词向量”，对应到图中：
- 单词——节点
- 词的上下文——节点与其周围的节点构成的链路
如何找出这样一条链路？——随机游走——node2vec
node2vec：定义了有偏随机游走（biased random walks）【有偏：从一个点跳到下一个不同点的概率是不一样的】混合了广度和深度优先搜索。关键参数：
- p：控制重新访问同一节点的概率（留在附近）
- q：控制探索更远的概率
以下图为例，假设当前节点v的上一时刻的节点为t（即节点v是从节点t转移过来的），定义从节点v游走到节点x1 , x2 , x3之间的概率为α。其中，节点v游走到与上一时刻节点t直接相连的节点x1 的概率为1，游走到其他节点（x2 , x3）的概率为1/q，回到上一时刻节点t的概率为1/p，p,q为可调整参数。
节点v下一时刻游走到其余节点的概率的数学表述为：
参数允许在以下之间进行权衡：
- 低 p：在本地探索；这将侧重于图形拓扑结构中的社区结构（同质性）；
- 低q：探索更远；这允许捕获节点之间的一些结构相似性（例如：集线器hubs，网桥bridges）；
node2vec的参数P和q取值不同，得到的嵌入特征向量在二维空间上的可视化效果也不同。如下图所示，p比较小、q比较大时，算法更加关注局部特征，嵌入特征在局部上是比较相近的（上图）；p比较大、q比较小时，算法倾向于捕获在结构上相似的一些点（下图）。
其他图嵌入算法：
不同算法之间的结果可能会有很大差异，并且随着参数的选择也会有很大不同，如何比较算法的嵌入效果？
- 核心：使用嵌入后的向量构建同分布随机图，比较随机图和原图的JS散度，若很小，说明相近，进而说明嵌入效果良好。
首先，将原始图中的节点通过嵌入算法转换为向量表示，这些向量表示可以捕捉到节点之间的关系和特征。然后，使用这些向量来构建同分布随机图（通常是通过随机过程生成），即生成一张与原图在节点分布上相似的新图。
接下来，通过计算随机图和原图的JS散度来衡量它们之间的差异。JS散度（Jensen-Shannon divergence）是一种度量两个概率分布之间差异的指标。当JS散度越小时，表示两个概率分布越接近，即随机图和原图在节点分布上越相似。
因此，如果通过嵌入得到的向量能够很好地保留原始图中节点之间的关系和特征，那么使用这些向量构建的同分布随机图与原图之间的JS散度会很小，说明嵌入效果良好。
给定具有度分布 w=(w1,w2,...,wn)的 n 个顶点上图G=(V,E) 及其顶点到 k 维空间的嵌入，ε:V→Rk，我们的目标是为这个嵌入分配一个**“分歧分数”(divergence score)**，该分数用于比较不同嵌入结果在多个维度上的差异，分数越低，嵌入越好。这将使我们能够在不同的维度上比较多个嵌入的结果。
流程总述：
非随机图（原图）表现出类似社区的结构，所以我们一般：
- 将节点分组为集群（使用聚类算法/框架进行分组）
- 测量簇之间和簇内的边缘密度
- 通过计算散度分数将其与嵌入（矢量）空间中空间模型的预测密度进行比较
- 选择得分最高的嵌入
聚类算法/框架主要关注两个角度：
- 图拓扑视图：一个好的、稳定的图聚类算法（ECG、Louvain或InfoMap）
- 空间视图：引入基于度分布 w 和嵌入 ε 的几何 Chung-Lu (GCL) 模型
计算嵌入分歧分数（embedding divergence score）的算法：
给定G=(V,E)，它在 V上的度分布w，以及它的顶点的嵌入ε : V → Rk，执行接下来的五个步骤。通过计算分歧分数的算法获得嵌入的分歧分数ΔE(G)，可以应用该算法来比较几个嵌入算法的分歧分数指标，选出最好的（最小的）那个。
- 第一步：在G上运行一些稳定的图聚类算法以获得顶点集V的分区C，一共产生l个社区
。 - 第二步：令ci表示两个端点都在ci中的边的比例，ci,j表示一个端点在ci中且另一个端点在Cj中的边的比例，定义
，这些向量从G的角度表征分区C，嵌入ε不影响cˉ和c^。 - 接下来需要在 α 的一系列值上重复步骤 3-4
- 第三步：给定α ∈ R+，使用
的GCL模型（也可以使用其他稳定的模型）计算①bi：Ci内边的比例期望，②bi,j：Ci中一个端点和Cj中另一个端点的边的比例期望，计算公式为 
这些向量从嵌入ε的角度表征分区C。 - 第四步：使用 Jensen-Shannon 散度 (JSD)计算
之间的距离，以及 
之间的距离，公式为 
这是给定 α 的（分歧）分数。 - 第五步：从重复的步骤 3-4，我们获得了一系列Δα，选择
，将分期函数定义为 
。
为了比较同一个图G的多个嵌入，我们重复上面的步骤3-5并比较分歧分数（分歧分数越低越好）；步骤1-2值执行一次，因此我们对每个嵌入使用相同的图划分算法到l个社区。
