● 摘要
研究表明复杂网络在现实世界中广泛存在，由于网络中节点的异构性，簇结构成为其普遍而重要的拓扑结构属性。研究复杂网络聚类算法并准确揭示真实的网络簇结构是分析网络中节点关系及其演化规律、模拟信息在网络中的传播过程，预测网络中节点行为等问题的理论基础。目前复杂网络聚类技术的主要研究问题有：在规模庞大的复杂网络数据集中，如何实现快速准确地高效聚类；在普遍存在的以人为节点的复杂网络中，如何模拟簇结构形成的社会过程，挖掘更加真实的社区结构；在没有先验知识的复杂网络中，如何准确的自动提取先验知识并基于此实现高精度聚类。本文针对以上三个问题，在国内外研究的基础上，给出了三种基于不同思想的复杂网络聚类算法，主要工作包括：1.给出了一种基于群思想改进的Fast-Newman（FN）聚类算法。该算法将“群”定义为节点在聚类过程中的局部信息环境和聚类决策范围，并利用群内的节点连边期望值，改进原FN算法中基于全局最优思想的优化目标函数。该算法针对大规模复杂网络数据集，能够有效降低算法有偏性，提高聚类速度和精度。2.给出了一种基于节点核心影响力的聚类算法。该算法综合了启发式算法和优化算法的思想，基于介数中心度理论定义并找出具有核心影响力的节点，通过判定函数建立复杂网络簇的核心结构，再对其余节点进行聚类。该算法模拟了社会学中群体形成的驱动过程，对于由人构成的复杂网络具有优秀的聚类性能。3.给出了一种基于Laplace矩阵Jordan型的聚类算法。该算法通过对Laplace矩阵进行Jordan型变换，实现了对先验知识的自动获取和对网络的初始划分，并结合Jordan型中的特征值实现了完整的聚类过程。该算法解决了谱聚类方法对于先验知识的过度依赖，其聚类方法基于严密的数学理论，聚类结果具有极高的精度。4.实现了复杂网络聚类运算及聚类结果评价原型系统。本文通过实验以及原型系统的实现，验证了三种复杂网络聚类算法的正确性，以及其在聚类速度、精度和对先验知识依赖程度等方面相比主流算法的优越性。