A New Community Detection Algorithm Based on Adding and Deleting Links

摘要

随着复杂网络的不断深入发展，逐渐了解网络结构对检测的要求越来越高，社区检测算法被提出并得到了深入的改进。针对网络分裂和凝聚算法的高时空复杂度，以及许多相对稀疏网络聚类算法的不确定性，提出了一种基于链路预测的自动添加和删除网络链路的非重叠算法(ADL)(add and delete the network links automatically)。通过链路预测来补充网络中信息丢失的问题，通过删除链路来划分网络冗余信息。自动获取社区数量和核心节点集，并对孤立节点进行标签传播，处理后到达最终的网络分簇。最后，在LFR数据集和四个真实数据集上与其他算法进行比较，该算法表现出稳定有效的特征。

1. INTRODUCTION

随着互联网的快速发展，计算机网络已经进入我们的生活。过去，欧拉为“七桥问题”构建了地理实例，而如今，随着复杂网络的兴起，我们进入了“大数据”时代。复杂网络正在为新兴领域探索新的视角和新的方法，特别是在生物、社会和金融等领域。<今天，复杂网络是一门新兴的交叉学科，涵盖了物理、数学、数据挖掘、机器学习等多个领域。到目前为止，已经发现了一些复杂网络的拓扑性质，如小世界效应、幂律分布和动态特性[1]，其他性质如随机模型、克莱因伯格模型、BA无标度模块(Small world effect,power law distribution ,adnd dynamic characteristics have been found and other properties like stochastic model,Kleinberg model,BA scale-free module,)，甚至网络通信也促进了复杂网络学科的发展和进步。

在复杂网络中，社区发现促进了尺度的探索和新的视野。其中，复杂网络的小规模是节点和边，大规模是整个网络。社区发现(Community detection )也叫社区发现(community discovery)。它旨在通过使用不同级别和类别的研究算法来挖掘社区内紧密连接和不同社区间稀疏连接的集群。虽然社区本身的定义存在争议，但可以分为强社区(strong community )、几乎强社区(almost astrong community )、几乎弱社区(almost weak community)、弱社区(weak community)[2]。

链路预测是复杂网络领域的另一个重要概念[3]。一方面，由于世代消失、生长压缩和融合分裂，在真实网络中一些丢失的边缘没有被显示并且产生丢失的边缘。另一方面，由于网络的不断扩展，一些看似不存在的边缘会随着网络的扩展而逐渐出现。因此，链接预测在辅助社区挖掘过程中具有十分重要的意义[4]，这是本文的精髓和重要方法。

社区检测类似于聚类分析，因为它们都是无监督的，并且可以为人类分析提供服务。此外，两者都可以在没有先验知识的情况下划分数据集。然而，它们之间有一些本质的区别。例如，社区检测和聚类分析的领域分别是网络和点集。由于它们的相似性，许多社区检测算法都与聚类算法相似。例如，聚类算法DBSCAN使用半径中的点数作为其密度，然后根据最小密度阈值确定核心点，以形成一组间接可访问的核心点，用于通过扩展和聚集的方法到达聚类。相应地，社区检测中的CPM算法通过k-clique共享k-1个节点得到重叠社区，与DBSCAN相似方法到达extension of k-clique。

2. RELATED WORKS

根据划分的角度不同，网络可以分为不同的类别。根据方向、权重和划分，网络可分为无向和有向网络、加权和不加权网络、二分网络和多分网络。因此，不同类型的网络对应着不同的算法。同时，社区检测算法的划分也依赖于模块化优化、网络划分、特征选择等因素[5，6]，接下来将介绍一些不重叠的社区算法。

一些划分社区的算法是从不同的角度操作的。著名的例子是基于图的划分、层次聚类、标签传播(LPA)、目标优化和种子扩展(partition based on graphs, hierarchical clustering, label propagation (LPA), goal optimization, and seed expansion)。

基于🐸图的划分[7]。首先要确定群落的数量和大小，并采用最大流和最小割等方法达到指定的分区。精确解是NP-Hard。典型的算法是基于拉普拉斯图特征的Kernighan-Lin算法和谱平分算法[5，8]。

基于🐸层次聚类的划分。该算法将相似度大的节点归为一类，相似度小的节点归为不同的类。它是一种基于度量节点和社区相似性的内聚算法。它将单个节点视为一个群体，根据相似度的权重来合并边和节点。同时，它也是一种分裂算法，首先将整个网络看作一个社区，删除相似度权重最弱的边。典型的算法是基于节点或边中值的GN分裂算法和基于贪婪模块化优化的快速GN和边聚类系数的聚集算法[9]。它类似于聚类分析中基于单连接或多连接的距离相似度聚类。

基于🐸标签传播的划分(LPA) [10]:它与分类或机器学习中的标签传播算法相似，不需要先验知识。每个节点首先被唯一标记，然后随机选择一个节点，根据其邻居中出现次数最多的节点来修改其标识。重复迭代，直到网络节点标签不变或达到某个标准。其时间复杂度接近线性。

基于🐸目标优化的划分:仿生智能优化算法用于最大化模块化或划分密度，并通过连续编码迭代改变个体的轨迹。经过最优解码，可以得到最优的社区划分。该方法也可用于重叠社区检测。典型的算法有粒子群优化算法和模拟退火算法。

基于🐸种子扩展的划分[11]:首先，利用随机选择、度优先等策略获得有用的社区先验知识。然后，我们逐渐将其扩展到整体的外延，以了解社区的内部结构。这种算法好像是KNN算法和K-means算法从局部到整体，从小到大依次聚集。

3. THE PROPOSED APPROACH

现在将详细描述ADL的步骤如下。
☀️首先用邻接矩阵计算两个端点有边的相似度，相似度要和删除阈值Low比较。如果两个端点的相似度小于阈值，则应将其删除。

类似地，计算两个没有边的端点的相似度，并将其与添加阈值Up进行比较。如果相似度大于Uo，将添加这些端点。然后，它将被迭代，以自动获得社区的核心节点集和关联的数量。

☀️然后，应该对孤立节点进行标签传播等后处理。标记的核心节点应该首先被标记，它从内向外扩散，直到每个节点都被标记。

链路预测中有很多节点相似性的度量，我们只选择节点间的公共邻居数量来展示基本原理。对于网络中的节点$V_x$，其邻居集被定义为$\Gamma (x)$；因此，节点$v_x$和节点$v_y$之间的相似性定义为公共邻居的数量，如下式所示:
$$s_{x,y}=|\Gamma (x)\cap \Gamma (y)|\text{\hspace{1em}(1)}$$

图1显示了一个不重叠的社区。在链路预测中，应该选择节点间的公共邻居数作为节点的相似性度量。假设阈值Low=1和Up=4，如果有一些边连接两个节点，并且它们的公共邻居的数量小于或等于1，则连接它们的边将被删除。如果没有边来连接两个节点，并且它们的公共邻居的数量大于或等于4，则将添加边来连接它们。

Step 1: In Fig. 1(a), $S_{6,7},S_{4,9},and{S}_{7,11}$的值都是等于或者低于Low的，所以边$e(6,7),e(4,9),e(7,11)$的边删除掉。此外，$S_{1,4},S_{2,5},S_{3,6}$的值是高于或者等于Up,所以边$e(1,4),e(2,5),e(3,6)是被添加的。图1(b)显示了下一次迭代的情况。

Step 2: In Fig. 1(b), $S_{5,9},S_{6,8},S_{7,8}$的值低于或者等于Low，所以他们的边$e(5,9),e(6,8),e(7,8)$被删除了。没有添加边的符合条件，故没有边添加。图1©显示了下一次迭代的情况。

Step 3: In Fig. 1( c),$S_{5,8}$的值低于或者等于Low,所以边$e(5,8)$删除。没有符合添加边的边。图1(d)显示了下一次迭代的情况.

Step 4: In Fig. 1(d), 没有符合条件去增加或者删减的边。所以迭代结束。.现在，两个社团成为了， V 1 = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } V_1=\{v_1,v_2,v_3,v_4,v_5,v_6\} V1​={v1​,v2​,v3​,v4​,v5​,v6​}和 V 2 = { v 7 , v 8 , v 9 , v 10 , v 11 } V_2=\{v_7,v_8,v_9,v_{10},v_{11}\} V2​={v7​,v8​,v9​,v10​,v11​}。此外，我们得到一个孤立节点$v_7$.
对这个节点，我们采用标签传播(tag propagation)的思想来处理。与原始图相比，很容易发现链接$v_7$节点和社团$V_1$的一个边，然而对于$v_7$和$V_2$则有两条边。因此，节点$v_7$应该被划分为$V_2$在图1(e)中显示。现在算法结束，所以社区划分的划分结果如图1(f)所示。

与不能自动获取社区数量的快速纽曼算法(fast Newman 算法)相比，以及与不稳定的LPA算法相比，自动数据学习的主要贡献可以归纳如下:

1. 基于两个节点间相似性度量边的重要性，通过删除相似性小于阈值的边来把握社区
2. 基于两个节点间相似性预测边的存在，可以通过增加相似性大于阈值的边来增强社区结构
3. 在迭代添加和删除边的过程中，达到分离社区的数量，使社区内部的结构更加紧密，社区之间的连接自动断开。
4. 采用标签传播算法对孤立节点进行聚类。

4. RESULTS AND ANALYSIS

A. Evaluation Standard 评估标准

通过将LPA算法与快速纽曼算法进行比较，验证了该算法的可靠性和准确性。实验结果的评估标准是模块化的[14，15]，可表示如下:
$$Q=\frac{1}{2M}\sum _{i,j}(a_{ij}-\frac{k_i{k}_j}{2M})\delta (C_i,C_j)\text{\hspace{1em}(2)}$$

在这个公式中，$Q$表示模块化程度，Q值越大，社会结构越明显，意味着越好。$M$代表网络中边的总数，$a_{ij}$代表邻接矩阵的二进制元素值。$k_i$代表节点$i$的度，$C_i$代表包含$i$的社区，$\delta (C_i,C_j)$是一个值，如果$i$和$j$属于同一个社区，则为1；否则，它为0。

为了度量不同社区结构之间的相似性，归一化互信息(NMI)是比较社区的最流行的度量标准之一。NMI的定义如下:
$$NMI(A,B)=\frac{-2{\sum }_{i=1}^{C_A}{\sum }_{j=1}^{C_B}{N}_{ij}\log (\frac{N_{ij}N}{N_{.i}{N}_{.j}})}{{\sum }_{i=1}^{C_A}{N}_{i.}\log (\frac{N_{i.}}{N})+{\sum }_{j=1}^{C_B}{N}_{.j}\log (\frac{N_{.j}}{N})}\text{\hspace{1em}(3)}$$

在公式(3)中，A和B是两个图的社群结构.$C_A$是A分区的社区数，$C_B$是B分区的社区数；N为节点数，在两种群落结构中相同的节点；$B_{ij}$是A的社区$i$和B的社区$j$之间的重叠，它是社区共有的节点数；$N_{i.}$.是A的com munity$i$中的节点总数；$N_{.j}$是B的社区$j$中的节点总数。该计算遵循$0\times \log (0)=0$的惯例。NMI的范围从0到1，其中0表示社区结构完全独立，1表示它们是相同的。

B. LFR Benchmark DatasetsLFR基准数据集

分别对LFR基准数据集和真实数据集进行了实验。用于比较的实验参数是$N=128，minc=maxc=32，\bar{k}=16，\mu =0.1或\mu =0.3；N=1000，minc=20，maxc=50，\bar{k}=15，\mu =0.1$。其中N为节点数，minc为一个社区内的最小节点数。而且maxc是指一个社区内的最大节点数；$\bar{k}$是平均度数，$\mu$是节点数与节点总数的比率。

Truth Datasets真实数据集

真实数据集采用扎卡里的空手道俱乐部网络、海豚、波尔布特和足球[12，13]，如下所示:

图5和图10中描绘的Q值表明，ADL算法达到的社区划分具有更合理的社区结构，其值优于其他两种算法。

由于LPA的不确定性，使用50次迭代中Q值最大的社区进行比较。表中NMI值后面括号中的值代表数据集上算法的社区划分数。表格的最后一列代表了真实的社交社区的数量。从表1中可以清楚地看出，ADL的效果优于Fast Newman，并且它与LPA在足球数据集上具有相同的结果。结果表明，自适应学习算法的效果最好，同时也证明了该算法的可行性和准确性。

根据LPA的不稳定性，选择最佳值与其他人进行比较。快速纽曼算法是稳定的，但出于时间效率的考虑，不宜处理大数据集。ADL算法比LPA稳定，时间效率比Fast Newman高，实验结果良好。

V. CONCLUSIONS AND FUTURE WORK

社区检测算法层出不穷，而检测网络结构的基本核心点是不变的。由于网络的复杂性和动态性，网络中出现了边缘丢失现象；因此，适当地增加网络中的边可以增强社区结构以便于检测，而删除一些边可以去除网络结构中的一些冗余信息并达到关联的数量和节点的核心集。由于标签传播的不稳定性和分层分裂算法的高时空复杂度，结合链路预测，提出了一种基于边缘添加和删除的检测算法，该算法具有较好的复杂度和鲁棒性。

以后也有一些地方需要改进。例如，这个过程的时间复杂度是O(㼿㼿)，数据类型小，数据集的数量也不大。因此，大规模复杂数据集的处理是后期工作中需要关注的问题。