摘要
在实际生活中许多领域如社交媒体、生物、交通物流等复杂系统大多都可以通过抽象成为复杂网络进行表示。网络社区结构指网络中社区内部节点连接紧密，社区与社区之间的节点连接相对稀疏的性质。网络中社区的概念极为广泛，在现实生活中其可能代表着拥有共同爱好的社团，也可能代表公司中某一个部门的人员，在很多情况下，这些复杂系统中的同一个节点往往同时存在于多个社区之中，即重叠社区。作为网络结构的一个重要特征，重叠社区发现已经成为了复杂网络研究的一个重要方向。近年来，研究人员已经提出了许多针对复杂网络的重叠社区发现算法。但是，现有的算法仍然存在一些问题，如许多重叠社区发现算法在社区结构较复杂的网络中表现欠佳；基于标签传播的重叠社区发现算法社区划分结果稳定性较差等。针对上述问题，本文主要工作如下： 1.提出了一种基于网络嵌入和节点密度的重叠社区发现算法OCDNED。算法基于网络中节点的一阶相似和二阶相似结构特征构建损失函数，通过网络结构嵌入保存节点的局部特征并得到节点的低维向量表示，避免了传统的节点表示在度量节点相似度时空间复杂度过高或难以捕捉到远距离节点之间相似度的缺点。同时，算法结合社区标签隶属度改进了密度峰值中节点社区的分配策略，通过参数?和?控制标签的传播程度，进而能够发现不同重叠程度的社区结构。在多个真实数据集和LFR生成数据集上进行的对比实验表明该算法不仅在社区结构明显的网络中有很好的表现，并且在社区结构复杂的网络中依然能够较好的发现重叠社区。 2.提出了一种基于节点中心度和三支决策的重叠社区发现算法OCDNC_3WD。目前大多数基于启发式的社区发现算法在社区划分时对网络中所有节点采用相同的分配策略。考虑到网络中的节点并不是统一均匀分布，不同节点在社区中所处的位置不同，算法基于三支决策的思想，将网络中节点分为三种类型：社区核心点，待确定节点，孤立节点，采用不同的策略进行划分。在节点标签分配过程中同时考虑了节点的中心度以及节点之间的相似度，不仅提升了社区划分效果，也保证了社区发现的稳定性。在多个数据集上的实验表明了OCDNC_3WD算法能够较好的发现网络中的重叠社区结构。
NETL