复杂网络的社团划分和网络重构技术研究

• 作 者: 谢征
• 机 构: 南开大学
• 出 处: 南开大学
• 发表日期: 2015年期
• 关键词: 复杂网络 社团发现 局部相似性 非负矩阵分解 拓扑特性

复杂网络是研究自然界各种复杂系统的有力工具。通过对复杂系统进行观测、分析和抽象，提取出由节点和连边构成的复杂网络结构，进一步可以借助图论和网络科学的工具，进行拓扑特性、信息传播行为和系统控制等方面的研究。　　社团是复杂网络中普遍存在的一种中观结构，是协调网络宏观规律和微观特性的连接点，对于研究网络的功能和动力学等有着重要意义。另一方面，复杂网络的研究需要有真实准确的数据，客观条件的限制使得观测到的网络数据存在缺失和误差，在研究网络结构前应该先推断出网络的真实结构。针对这两个问题，本文在社团划分和网络重构两个方向上做了一些探索，主要贡献如下：　　(1)分析了现有节点拓扑结构相似性指标的特点，指出它们不适用于网络的社团划分过程。结合刻画相似性的局部路径（LP）指标和Katz指标的优点，提出一种新的节点局部相似性指标，反映局部网络的联系紧密程度，并适用于社团划分过程。　　(2)提出基于局部相似性的社团划分算法。利用节点间的相似度定义了节点和社团之间的相似度，根据加权投票和多数表决原则决定节点的社团归属，多次迭代后得到网络的“自然”社团结构，并能发掘出社团结构核心节点和桥接点。将该算法在基准网络和真实的电网系统中仿真，验证了算法的有效性。　　(3)针对网络重构，首先对现实网络的结构和连边产生机制进行分析，做出社团结构决定网络连边的基本假设，进一步推导出节点连接概率矩阵的矩阵乘积形式，利用非负矩阵分解得到节点间的连接概率矩阵进行网络重建，并提出了正则化和集成化的改进措施，最后在几个真实的网络数据上测试了不同社团个数、不同正则化参数以及集成化的算法，和基于相似度的算法相比，本算法的网络重构准确率更高。　　本文的工作能够满足复杂网络的社团划分和网络重构的现实需求，同时对于两者的联系以及复杂网络演化机制的研究也有一定的指导意义。