论文部分内容阅读
社团结构分析是复杂网络研究中的一个重要方向。而社团探测是社团结构分析的基础。在现实网络中，大多数社团结构具有任意尺度和形状的特点，而密度聚类恰好具有聚类结果不受簇形状和大小影响的优势。因此，借鉴密度聚类的思想对网络社团进行探测通常能够收到良好的效果。随着对这一类方法研究的深入，研究人员逐渐发现基于密度的社团探测中存在参数优化不全面、节点相似度模型不完善、社团探测评判准则分辨率欠佳等问题，这些问题影响了社团探测的性能。因此，研究基于密度的社团探测中的这些问题，对提高算法性能、为社团结构分析提供保障具有重要的意义。 本文以基于密度的复杂网络社团探测为主线，分别对密度聚类框架下的社团探测和密度模型框架下的社团探测中存在的问题进行了研究。主要研究内容有以下几个方面： ①对密度聚类框架下和密度模型框架下的两类的社团探测进行了研究，分析了两类社团探测方法中存在的主要问题。前者存在的问题是密度聚类参数优化和参数求解方法不够完善、社团探测结果对参数敏感。后者存在的问题是相似度模型适用范围有限、网络密度模型难以对最新的社团结构定义进行刻画、评判准则分辨率存在缺陷。 ②针对密度聚类参数优化和参数求解方法不够完善的问题，研究了一种典型密度聚类中的参数优化和求解方法。针对算法中的三个参数，分别提出了三种求解参数最优值的方法：1)针对平滑参数σ，给出了一种基于最小化密度熵的优化方法，方法还讨论了噪点对求解最优σ值造成的影响，并针对含噪和非含噪数据集，提出了用数值法求解最优σ值的具体步骤；2)针对噪音阈值ξ，论文基于密度吸引点，用可变合并阈值ξij和任意形状簇的fC指标来替代ξ；3)针对步长参数δ，论文给出了一种基于数据点间距离的求解方法，用可变化的步长替代固定步长。并提出了一种基于数据分布求解参数的密度聚类。以上成果解决了密度聚类参数优化和参数求解方法不够完善的问题，为解决基于密度聚类的社团探测中参数设置问题提供了理论基础。 ③针对基于密度的社团探测结果对参数敏感的问题，研究了网络到低维数据集的映射方法及密度聚类在社团探测中的应用。提出了一种基于密度聚类的社团探测算法和另一种针对平均节点度较小、节点度方差相对较大的网络的快速社团探测算法。第一种方法构建网络的拉普拉斯矩阵，通过拉普拉斯特征映射，将网络投影到低维的特征空间，并将投影后节点对应的特征向量看成是节点在该空间的坐标，从而将网络映射为低维数据集，在此基础上直接应用本文提出的密度聚类完成社团探测。第二种方法专门针对平均节点度较小、节点度方差相对较大的网络，在用最小化密度熵求解高斯窗σ和截断距离d的过程中，将求解节点核密度估计问题转换为求解节点度的问题，并利用本文提出的密度聚类中爬山算法的思想，完成社团探测。通过数值实验表明了上述研究结果在聚类性能上具有的优势。 ④针对相似度模型适用范围有限、网络密度模型难以对最新的社团结构定义进行刻画、评判准则分辨率存在缺陷等问题，研究了新的社团结构框架下相似度模型、密度模型、评判准则及社团探测算法。提出了一种基于节点t步转移矩阵的节点相似度模型和一种社团相似度模型。还提出了基于节点相似度的相对密度模型和基于该模型的社团探测评判准则S值。并给出了一种基于相对密度的社团探测算法。算法通过节点相似度对网络进行预处理，得到一个初始划分；再基于社团相似度对这些初始节点簇进行层次聚类；根据提出的评判准则S值选择最优的社团探测结果。通过数值实验表明了上述算法在基于密度的社团探测中具有上佳的划分效果。 在以上理论分析与数值实验的基础上，最后对论文的主要工作与研究成果做了总结与分析，并展望了下一阶段的研究工作。