孟 雪，许 英

(新疆财经大学 统计与数据科学学院，乌鲁木齐 830012)

社团检测技术广泛应用于社会网络、引用网络、食品网络、生物网络等多个领域[1]。 在社团中，人们通常理解节点的子集与网络的其余部分之间的互连更为紧密。利用生物学、物理学、社会科 学、应用数学和计算机科学等不同学科的技术和工具，开发了许多社团检测算法[2]。 在文献[3]中，Newman和Girvan引入了模块度函数Q，通过模块度函数Q，使我们找出网络分解到社团的最佳方式社团。

本文提出了一种基于局部随机游走距离轮廓系数的网络社团检测新算法(Silhouette算法，简记为SIL算法)，并给出一个新的定量函数平均轮廓来评估质量网络社团结构。 同时，通过四个现实世界网络和计算机生成网络(Girvan和Newman[3]提出的GN基准和Lancichineti Andrea等人[4]对GN Benchmark的缺陷提出的LFR基准)进行了测试。 实验结果表明，SIL算法能够以较高的NMI(Normalized Mutual Information)值、模块度和平均轮廓值准确有效地检测网络的社团结构。

1 算法架构

1.1 局部随机游走距离

给定无向无权网络G=(V，E)，其中V是节点集合，E是边集合。随机游走是一个重要的随机过程，它可以表示随机游走者经过的一系列节点。转移概率矩阵P，其中Pij=aij/kj代表在随机游走者i在下一步步行到j的概率。其中A=(aij)是网络的邻接矩阵，ki表示节点的i的度，与其他基于随机游走的距离度量相比，具有较低的时间复杂度。

给定随机游走者i开始，在t步骤之后，该游走者到达j的概率可以用πij(t)表示。这个系统的演变方程可表示为πi(t)=PTπ(t-1)，其初始系统状态为πi(0)=ei，第i个位置为1其他为0.随机游走者访问t步后，LRW(Local Random Walk)指数可以定义如下：