基于网络信息的社区发现算法研究

作     者：李昊康 

作者单位：河北师范大学 

学位级别：硕士

导师姓名：王静红

授予年度：2022年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：复杂网络 社区发现 模块度矩阵 动态网络 黑塞矩阵 

摘      要：复杂网络作为一门新兴科学,可以对存在的网络现象及其复杂性进行解释。社区发现是复杂网络分析的重要内容,有助于人们认识网络的组织结构和连接模式,进而指导实践。因此在复杂网络中进行社区发现研究具有重要的理论意义和实用价值。现有的研究还不能很好的处理社区结构不明显的网络,且把发生在不同时间的网络连边看作同质的,忽略了连边承载的信息随时间变化的现象。如何进一步拓展、完善不同类型数据中的社区发现方法依然是一个挑战。本文针对静态、动态网络各自的特点,分别提出一种社区发现算法,具体研究内容如下:首先,介绍了复杂网络社区发现的研究背景、研究意义和理论基础;综述了社区发现的国内外研究现状、真实网络中的属性信息、复杂网络的模型结构和度较正随机块模型(Degree Corrected Stochastic Block Model,DCSBM)的实现方法;阐述了论文的研究目的和研究内容。其次,针对社区结构不明显的网络,提出了基于复杂网络注意力模型的社区发现算法(Community Discovery Algorithm of Complex Network Attention Model,CCAM)。算法的主要创新如下:(1)通过引入注意力模型,提出一种将一阶、二阶邻居和模块度矩阵三种特征信息进行融合的模型,该模型可以更敏锐提取到网络的特征;(2)提出一种“复杂网络预处理——社区博弈归并社区发现组合方法,通过复杂网络预处理可以很好的对网络进行压缩,有效减少了算法的运行时间;(3)参照无权重网络的相对指数,提出一种适用于加权网络的相对指数,用以平衡社区博弈过程,优化社区划分结果。最后,针对连边承载的信息随时间变化的现象,提出了基于自由能的动态网络社区发现算法(Bethe-based Dynamic Network Community Discovery Algorithm,BDCD)。算法的主要创新如下:(1)针对现实世界中事件影响力随时间减弱的现象,提出一种网络事件影响力模型,该模型对不同时刻的事件进行综合,从而得到当前时刻的连边系数矩阵;(2)通过拓展自由能的黑塞矩阵算法,提出自由能的加权黑塞矩阵算法,该算法可以适用于动态网络的连边系数矩阵,并进行社区划分;(3)通过在DCSBM模型中引入时间属性,提出可变节点的动态随机块模型,模型的生成网络可以用作动态社区发现算法的实验数据。经过实验验证,在静态网络中,CCAM算法通过注意力模型来综合网络中三个特征维度信息,能够准确有效的划分社区,且在结构不明显的网络中优于传统的社区发现方法。在动态网络中,BDCD算法通过综合不同时刻的事件的影响力信息,可以在节点数量显著变化时保持相对优异的性能,同时在归一化互信息、模块度方面具有较好的实验结果。