论文部分内容阅读
社交网络是一种包含大量节点以及节点间错综复杂关系的网络,其中存在着明显的社区结构。所谓社区是指网络中的节点聚集而成的子图,同一社区的节点之间连接紧密,不同社区的节点之间连接稀疏。已有相关研究针对网络中这样的结构进行社区发现并提出了相关的算法。目前社区发现的算法如随机模型或者模块度最大化算法本质上都是将网络结构映射到一个特征空间,从而表示并且重构网络的拓扑逻辑,但是这种映射是线性的,而真实网络中包含大量的非线性特征,这使得上述模型在实际中的效果并不好。另外,在发现的社区中还存在着一些与社区主要部分连接不紧密的节点,他们可能是单个节点,从而形成社区离群点,也有可能是几个相连的节点形成的小团体,即离群子社区。离群子社区往往存在一些潜在的、有意义的信息,但离群子社区发现的相关研究工作还比较少,现有社区发现算法也很难发现这样的结构。本文基于深度学习方法,围绕着非线性提取缺陷、离群子社区描述和分布式并行等问题,提出了社区发现的算法及其改进方案,主要工作如下:第一,针对现有社区发现算法对非线性特征提取的缺陷,本文提出了基于深度学习的社区发现算法。本方法结合了卷积神经网络和自动编码器的优点,构建了一个深度网络卷积—自动编码器。本模型能够较好的提取网络的非线性特征,且卷积操作的局部感知也符合网络中相连节点具有相似性的特性,因而提高了社区发现的效果。同时为了更好地表征节点的关系,本文提出了相似度的概念,并把网络的相似度矩阵作为模型的输入。在实验部分,本文在人造数据集和真实数据集上比较了本文所提方法和传统的社区发现方法以及其他使用深度学习的社区发现方法的实验结果。在大多数数据集上,本文的方法要优于其他方法。同时,本文还将算法提取到的特征通过不同聚类方法得到了社区发现的结果,其互信息指标表明了本模型具有有效地特征表示能力。第二,针对现有社区发现的描述和定义没有很好地体现离群特性的问题,本文提出了一种基于深度学习的离群子社区发现方法。离群子社区是网络子社区中的一种,是一种与整体社区结构连接稀疏的子社区。在很多情况下,离群子社区都隐藏着一些信息,但总是为人们忽略。本文重新定义了边的介数中心性,将其定义为能够反映社区内两个子社区间连接的紧密程度,并且构建了一个结合卷积和自动编码器的网络,从而学习到一个能够表征网络的数值。在实验部分,本文提出了三个用来评估本文所提方法的评估函数和作为对比的Baselines,并在人造数据集和真实数据集上验证了方法的有效性。最后,本文对部分真实数据集上的离群子社区进行了详细分析,表明了离群子社区发现的意义。第三,网络结构的复杂使得单机社区发现算法面对庞大数据量时显得力不从心。为了能够更有效的处理结构复杂而庞大的网络,本文提出了基于并行化深度学习过程的社区发现算法。本文将第一部分提出的基于深度学习的社区发现算法在分布式TensorFlow框架下进行并行化处理,通过设置参数服务器和工作节点,将深度学习的训练过程分发到多个节点上,从而提高了算法运行的效率,减少了运行时间。实验部分,本文将该算法在不同数据集和不同数量的工作节点上运行的时间进行对比,从而验证本文提出算法的有效性。同时,本文还对比了单机和分布式情况下的社区发现效果,验证了本文所提算法能够在保证社区发现效果的情况下减少算法的运行时间。