SASH：解码图中的社区结构-计算机科学-机器学习-算法.pdf

SASH：解码图中的社区

结构

AllisonBeemer,JessalynBolkema

DepartmentofMathematics,UniversityofWisconsin-EauClaire,EauClaire,WI54701

DepartmentofMathematics,CaliforniaStateUniversity,DominguezHills,Carson,CA90747

摘要—图中的社区检测涉及识别紧密相连的顶点集群；该领在于它针对问题进行了定制，并且在输出社区聚类的数

域具有多种重要应用和丰富的文献。问题以前曾被置于纠错码的量和规模方面具有灵活性。这项工作包括图聚类的一种

范畴内，将图视为假设的基础社区的噪声版本。本文介绍了一种新技术和技术分析的一个新视角。

社区结构的编码以及由此产生的代码参数。然后我们提出了一

必要的背景讨论见第II节，第III节给出了社区代

种新颖的算法SASH，用于根据观察到的数据集解码估计出的社

本码Cnm的参数。第IV节介绍了我们的解码器SASH。第

区。我们在同质种植划分模型和Zachary的KarateClub数据集

译上的模拟展示了SASH的性能。V节包含了SASH的仿真结果，第VI节总结了论文。

中II.预备知识

1I.介绍

v如上所述，图聚类问题可以通过将现有数据集的图

3社区检测是识别网络中集群的问题：这些节点子集视为其顶点被划分为不相交团的一种噪声版本来表述

8

5彼此之间的连接比与图的其余部分更密集。识别这种潜为一个编码理论问题。与传统的信道编码问题相比，我

6在结构是网络科学中的一个基本问题，具有广泛的应用们不能自由设计代码，而是专注于有效地准确解码接收

1

7.性，包括生物学、社会科学、网络安全等领域[1]。存到的图到最有可能表示允许的图聚类的码字。

0在许多聚类方法，每种方法都有其自己的优势和局限性因此，我们首先定义了一组社区代码，这决定了可

5

2[2]；不幸的是，不存在社区检测的统一理论，考虑到网以从我们的解码器输出的图的聚类情况。在整个论文

:

v络属性、规模和复杂性的广泛差异，可能也不会有[3]。中，我们将反复在讨论一个图及其对应的邻接矩阵的

i

x近期研究的一个分支试图理解社区检测算法的基本可上半部分之间转换。一个简单无向图G的邻接矩阵A，

r

a能性和局限性，识别出超出这些阈值后聚类变得不可能该图有n个标记的顶点，是一个对称矩阵，使得在条目

或不太可能的情况[4]。Aij,ij中出现一个1当且仅当顶点i和j在G中相邻。

社区检测挑战与错误校正工具之间的联系是直接否则，Aij0。

的：如果我们把理想化的社区结构视为一种编码信息，

定义II.1.令n2,Nn和1mn.社区代码

2

那么观察到的图就可以被解释为这种结构的一个噪声CnmN包含恰好对应于顶点数为n的（简单无向）图