一种基于极大连通子图的电信社群网分割算法.docx

一种基于极大连通子图的电信社群网分割算法
摘要
社交媒体和网络通信已成为现代生活的重要组成部分，电信社群网的分割对众多应用领域都有着重要的作用。本文提出了一种基于极大连通子图的电信社群网分割算法。该算法首先建立网络拓扑模型，然后基于最大连通子图分割原则，将网络划分为多个簇，在每个簇内进一步进行社群识别，实现了对复杂网络的快速分割。实验结果表明，该算法具有较高的准确性和可扩展性，可以在较短的时间内完成大规模电信社群网的分割。
关键词：电信社群网；极大连通子图；社群识别；分割算法
1.引言
随着社交媒体和网络通信的普及，电信社群网已成为信息传输和社交交流的重要载体。然而，电信社群网中的节点和边缘往往存在着复杂的关系、巨大的规模以及互连关系密集等问题，给其分割和分析带来了极大的挑战。因此，如何快速准确地分割网络、识别社群成为研究所关注的领域。
目前，电信社群网分割算法主要采用基于图结构和机器学习的方法。其中基于图结构的方法主要通过节点、边缘之间的度量及算法进行分割，如使用最小割算法、Louvian算法等。机器学习的方法主要是通过对数据特征进行提取和分类，如使用聚类、支持向量机等方法（Haiyingetal.，2019）。
在本文中，我们提出了一种基于极大连通子图的电信社群网分割算法。其主要思路是在网络建立之初，通过最大连通子图原则，将网络划分为多个簇，然后在每个簇内进行社群识别。实验结果表明，该算法具有较高的准确性和可扩展性，可以在较短的时间内完成大规模电信社群网的分割。
本论文结构如下：第二部分为相关工作的综述；第三部分为基于极大连通子图的电信社群网分割算法的详细描述；第四部分为实验设计及结果分析；最后第五部分为结论和展望。
2.相关工作综述
目前，电信社群网分割研究领域涵盖了多种算法和方法。早期采用的是最小割算法（Wangetal.，2014），主要通过计算节点之间的最小割，将其分割成两个子图。该方法的优点是简单、易于实现，但是对于规模较大、层级较多的网络缺乏有效性。
后来，引入到社交网络中的Louvian算法成为了主流（Blondeletal.，2011），该算法主要通过极大化“模块化度量”来达到社群划分的目的，其优点是一般性强、收敛效果好。极大化“模块化度量”本质上是极小化整个网络所包含的系统内部边缘和系统外部边缘的比值，最终形成最优的社群划分结果。但是，该算法对网络的分割受到节点数量和社群数量的影响很大。此外，该算法时间复杂度较高，在对大规模网络进行分割时不够实用。
最近几年，基于机器学习的方法发展快速，例如利用贝叶斯网络、聚类算法进行社会网络分析的研究正逐渐增多（WilderandKarmacharya,2019）。聚类算法是机器学习中常见的一种无监督学习方法，在社交网络分析中应用广泛。其中比较常见的聚类算法有k-means、DBSCAN（Densitybasedspatialclusteringofapplicationswithnoise）、MeanShift、SpectralClustering、BIRCH等。这些聚类算法效果较好，但是缺点显而易见，复杂度高、模型难以调整、参数繁多等。
在本文中，我们提出了一种基于极大连通子图的电信社群网分割算法，主要通过网络建立之初的最大连通子图分割，实现了对大规模网络的快速分割。
3.基于极大连通子图的电信社群网分割算法
3.1算法原理
本算法主要思想是先通过最大连通子图将社交网络分割成多个簇，再在每个簇内部利用社群识别算法划分出具有相同特征的社群。
所谓最大连通子图是指网络中由若干节点和边组成的子集，在没有新增节点或边的情况下，无法再加入一个新的节点。对于这种连通子图，我们可以将其看作是具有相似特性的社群。
3.2算法流程
（1）建立网络拓扑模型
在网络建立之初，我们需要建立其拓扑模型，并根据连通关系将节点和边分别记录在邻接矩阵和边界矩阵中。
（2）求最大连通子图
利用连通性的定义，我们用图中任意一个节点开始，从该节点依次遍历网络中的所有节点，并标记已经访问的节点。当当前节点已经没有相邻的节点可以访问时，我们便得到了一个连通子图。如果存在其他节点没有被标记，则重新从该节点开始遍历，直到所有节点都被遍历并标记为止。这样便得到了一个最大连通子图。
（3）簇的划分
在得到所有最大连通子图之后，我们就可以根据其节点/边的数量等特性对其进行分组，形成多个簇，最终识别出各自簇的社群。
（4）社群识别
在每个簇内部，我们依据社群识别算法的不同，可以通过节点度中心性、介数中心性等方式来计算节点重要性，然后将重要性较高的节点继续拆分为多个子簇，直到每个子簇内节点交集的大小达到预设阈值为止。
3.3算法优化及扩展
（1）优化算法效率
针对算法在网络分割时时间复杂度高、效率低的问题，我们需要对网络