2022-WWW-GraphReformCD Graph Reformulation for Effective Community Detection in Real-World Graphs

ABSTRACT

社区检测受图中误导性信息影响，例如

• 图中存在许多连接不同社区的边。
• 图中存在许多连接不同社区的边。

开发一种名为\text{GraphReform}^\text{CD}的新方法。该系统通过重构输入图生成新的图结构，并有效消除影响社区划分的相关误导性信息内容。从而实现对社区结构的精确识别。

• 在重构阶段中，在为每个节点创建k-最近邻图后，在每次迭代中允许其与可能在同一社区的其他节点建立联系。
• 通过分析结构相似性指标来识别出属于同一社区的节点，并使用Jaccard系数和SimRank值作为主要评估标准。

1 INTRODUCTION

几种社区检测算法类型

• vertex-based clustering - 节点聚类技术（如SHRINK、BlackHole）
• subgraph identification - 子图识别
• splitting algorithms - 分裂算法
• network quality enhancement - 网络质量提升
• model-driven methods - 基于模型的方法（如Infomap）

广泛使用的社区检测算法：

• SHRINK is based on hierarchical clustering algorithm.
• BlackHole embeds a graph into a set of points in low-dimensional space and employs spectral clustering algorithm for community detection.
• SCAN is a variation of DBSCAN, which is a well-known density-based clustering method designed specifically for community detection.
• Louvain is a prominent modularity optimization algorithm that relies on hierarchical clustering techniques.
• Infomap leverages information theory to identify community structures within networks.

一般情况下，在图上任意两个节点之间的一条边都被用来表示这两个节点之间存在某种特定的关系。从社区发现算法的角度来看，在社区发现算法中如果一个图上任意两个节点之间存在一条边，则表明这两个节点很可能属于同一个社区

在真实世界的网络架构中（图），节点在决定是否与其他节点产生连接时（边），主要依据它们自身的特性（属性），而忽略了整体社区布局（结构）。例如，在社交网络领域中（研究领域），一个计算机科学家社群的成员可能会与旅途中结识的人发展出新的联系（关系），即便这些认识对象不属于同一个领域的学术群体（社群）。

由于真实世界的图中包含了一些可能导致社区检测算法误判的信息（例如一个节点可能与本不该连接的同属社区中的其他节点不相连），这会导致两种情况：一方面该节点可能与本不该连接的不同社区中的节点相连；另一方面则可能导致与应隔离开的本属社区中的节点相连）。随着这些误导性信息数量的增加，在实际应用中使用优秀社区检测算法依然会面临更高的准确率挑战。

该方法基于以下假设：每个图节点在决定是否与另一个节点创建边时会评估这两个节点属于同一社区的概率（即考虑它们的共同属性而不只是个体特征）。通过特定方式重新构建给定图的新图形式后，在此新图中每个节点将被连接至其可能属于同一社区的其他节点。

2 \text{GRAPHREFORM}^\text{CD}

该算法首先通过去除原始图中的所有边来构建一个基础网络。在这一过程中，在为每个节点分配社区标签时，系统会自动建立连接到其他可能归于同一社区的节点。

在本节里，我们探讨评估一对节点间属于同一社区的可能性有多大，并同时利用新构建的一条边来形成重构图

2.1 Structural Similarity Measures

基于图的拓扑结构测定两个节点之间的接近程度

• 1-hop-neighbor based ones:仅考虑给定节点对的直接邻居。两个节点之间的相似度随着直接连接到这两个节点的共同节点数量的增加而提高。典型的例子包括Jaccard指数、Adamic/Adar指数和余弦相似度。
• Multi-hop-neighbor based ones:考虑给定节点对的直接邻居和间接邻居。一对节点之间的相似度随着直接和间接连接到这两个节点的共同节点数量的增加而提高。在这里，间接邻居对相似度的影响较直接邻居小。典型的例子包括SimRank和带有重新启动的随机游走（RWR）。
• Graph-embedding based ones: 图嵌入旨在将图的每个节点表示为低维空间中的向量，其中一对节点的距离随着直接/间接连接到这两个节点的节点数量的增加而更加接近。基于图嵌入的节点对相似性可以通过使用嵌入空间中它们相应向量之间的距离来计算。典型的图嵌入技术包括Deepwalk、LINE 和Node2Vec。

基于其定义特点，在一个网络系统中同一个社群内部成员之间的联系较为紧密而不同社群之间成员间的联系则相对较少由此可知同一个社群内的成员间不仅能够通过多个直接路径而且还可以借助间接路径进一步增强这种联系。
基于这些特征 假设一对节点之间的结构相似性越高 则它们被归为同一社群的可能性越大。

2.2 k-Nearest Neighbor Graph

基于计算得到的相似度值基础上构建了一个k-最邻近（KNN）图作为重构图。在该KNN图中, 每个节点均有机会以相同概率生成k条出边, 从而连接至与其高度相关的其他节点。

首先，在原始图中存在高度节点的情况下，这些节点很可能具有跨社区的边。
在k-近邻图中（k-NN graph），其连接数受限于参数k的选择。因此，在这种情况下，
通过这种方式实现了模块化结构的有效构建。

此外，在原始图中度较低的节点很可能只与少数社区内的节点相连。
此外，在k-近邻图中，这类节点具有正好k个连接数，并倾向于与同一社区内的其他节点建立联系

因此

需要注意的是，在经过重构后的kNN图中

注意

该算法基于节点间结构的相似性度量，在原始图中识别每个节点的k近邻节点，并生成连接节点与其所有k近邻节点的k近邻图。这种方法所得出的k近邻图相较于原始图在实现社区探测时具有更高的准确性。

3 EXPERIMENTAL SETUP FOR EVALUATION

\text{GRAPHREFORM}^\text{CD}具有不同的变体，取决于以下参数：

结构相似性度量： 通过Jaccard相似性指标、Adamic/Adar指标以及SimRank算法来评估两节点间的结构相似程度。

为生成有效的kNN图结构需合理设置参数k值。在本研究中采用每个原始图平均度（\text{D}_{avg}）的不同倍数设置（如k=\{\text{D}_{avg}, 2\text{D}_{avg}, \dots, 5\text{D}_{avg}\}）来进行参数优化计算。

在本研究中探讨的两种近邻图类型包括标准的k-近邻图（K-\text{NEIGHBOR}）及其变形体——互惠k-\text{NEIGHBOR}方法（\text{MK}-\text{NEIGHBOR}）。其中，在k-\text{NEIGHBOR}框架下，默认情况下任意两节点间仅需满足单向关系即可建立连接；而\text{MK}-\text{NEIGHBOR}方法则要求两节点间必须同时满足彼此为对方k-\text{NEIGHBOR}的关系才能建立连接。在本文后续章节将通过\text{GRAPHREFORM}^\text{CD}算法对这两种框架进行系统性比较分析

本文主要运用了一系列最先进的社区检测算法（SHRINK、SCAN、Louvain 、Infomap和BlackHole），对\text{GRAPHREFORM}^\text{CD}的所有参数组合进行系统性地测试。

针对各个社区检测算法中的参数配置问题，在本文中我们采用了网格搜索策略，并最终确定能够获得最佳NMI值的最优参数配置。

部分CD算法在其运行特性上具有随机性特征，在采用相同参数设置进行多次实验时也可能导致结果差异。为了应对这一问题，在本文中我们对这些算法进行了五次独立运行，并计算并呈现了平均NMI得分。

在社区检测领域来看

我们在评估中采用了六个真实世界数据库与四个人工合成基准数据库作为实验依据。其中真实世界数据库均具备真实的社群结构特征，并包含Football、Polbooks、Karate、Email、Cora与PubMed等代表性领域数据集合。而人工合成基准数据库则全部基于LFR基准进行生成

LFR-benchmark基于调整μ值来平衡社区间边占总边的比例以及节点数|V|的数量，从而构建了具有多样特性的合成数据集。

该模块度指标用作衡量图划分成社区的优劣程度，并附带函数链接地址

• 本文在分析过程中，在每个图数据集的真实社区上比较重构前后系统的模块度变化。* 这旨在验证我们的系统重构是否有效地降低了误导性信息的影响。 * 然后随后采用标准化互信息（NMI），这是一种被广泛应用于社区检测研究的方法，来评估CD算法的准确性。 * 最后，标准化互信息（NMI）则用于衡量真实社区结构与预测结果之间的共同信息程度。

4 EXPERIMENTAL RESULTS

结果显示了通过计算社区间边占所有边的比率（|Einter|/|E|）以及模块度（Q），重构显著地减少了原始图中的误导信息

通过NMI分析可以看出，在与原始图相比时，\text{GRAPHREFORM}^\text{CD}重构后的图在社区检测方面表现更为准确。

5 CONCLUSIONS

该系统提出了一种名为\text{GRAPHREFORM}^\text{CD}的方法学框架，在社交网络分析领域具有重要应用价值。
该方法通过重组给定的图生成一个新的网络结构，并使相同的算法能够以更高的精度完成社区识别任务。
从社会网络分析的角度来看，在这种新的网络结构中误分类的可能性大幅降低。
大量实证研究表明使用这种方法构建的社会网络在进行社区识别时表现出显著的优势。