论文部分内容阅读
复杂网络是具有自组织、自相似、吸引子、小世界、无标度部分或全部性质的网络。现实网络如社交网络、交通网络等都具有复杂网络特性。复杂网络的可视化是一个宽泛的概念,基于合理布局的可视化技术为其基本定义,从广义上讲,还可以包括基于压缩的网络保真分析和基于聚类的结构化分析。论文研究工作即为广义可视化技术的研究。论文的主要研究目的是为网络分析决策者从整体上更好地把握网络的主要成员、结构层次关系。论文对复杂网络压缩的研究目的主要是为了更清晰地展示网络的主要节点及主要关系,降低大规模网络分析的复杂性。论文后续的社区挖掘算法及可视化布局算法以压缩算法结果为基础。压缩方法基于图论分析。按照网络动力学原理,节点是网络局部的主要成因,边是网络全局的主要成因。论文分别从节点和边两方面对网络进行压缩。节点的重要性以节点的度和聚集系数为建模指标,因为节点的度反映了节点自身的局部聚集能力,而节点的聚集系数反映了节点对邻居节点的局部聚集能力的影响;边的重要性以边的介数为评价指标,因为该指标反映了边连接网络不同部分的能力。论文分别用仿真数据和真实数据对所提出的压缩算法进行了实验验证,结果表明在压缩比高达30-50%时,压缩后的网络仍能保持60-80%的原始信息量,并仍较好地展现原始网络的拓扑结构。该算法在实际应用时可根据原始网络规模、密集度及使用者需求选择合适的压缩比。论文基于复杂网络具有的社区特性,提出了一种基于核心节点的社区挖掘聚类算法。该算法以压缩算法分析获得的重要性较高的节点为初始种子节点,保证了种子节点较好的局部聚集性,有益于提高聚类效率与效果。论文对采用核心节点可能带来的社区重叠挖掘问题也给出了相应的解决方案,一是依据节点间距离大小对核心节点进行筛选,二是对社区划分结果进行去重叠处理。论文对聚类过程的优化,体现在适应度函数的计算综合考虑了社区聚集度和社区自身密度两个因素。论文给出了聚类分析的主要设计,包括核心节点选取、适应度函数计算、重叠节点处理等。实验结果表明:算法相比传统算法聚类质量提高。为了得到清晰直观的复杂网络拓扑结构,论文提出了一种基于社区结构的可视化布局算法。该算法在力导引布局算法和分层技术的基础上,利用聚类得到的社区结构,自顶向下逐级展开。基于社区紧密度的KK算法用于社区间的宏观布局,基于圆形显示方式的FR算法用于社区内部节点的微观布局。实验结果表明:改进的可视化布局美观、时间效率也较好。此外,该算法还可以用于辅助评价社区聚类结果的好坏。因计算量的限制,论文的实验结果基于有限的网络规模,但复杂网络的特性并不局限在网络规模上,论文的研究工作对大规模网络仍有意义。