基于时间局部性的网络拓扑结构发现算法

摘要

【目的】随着社交网络技术的快速发展，大规模复杂网络的拓扑结构获取成为电子、网络、生物和医学等多个学科领域亟待解决的问题。大规模复杂网络由参与节点和虚拟连接组成，其中节点代表个体、家庭与社会等角色，而连接则刻画了这些角色间的复杂关系。一般而言，复杂网络中存在严重的同源性现象，即存在大量的重复或相似组成架构，这极大地增加网络动态结构发现的难度。【方法】在时间局部性原理基础上，提出一种启发式网络社区发现算法，旨在进一步优化拓扑结构发现的精确度和运行耗时。通过修改相邻时间范围内节点的计算规则，利用余弦相似性判定准则与拓扑结构发现算法深入描述网络中多个参与节点之间复杂关系的可预测性。算法结合经典Louvain算法，通过计算增量模块度和余弦相似性优化社区检测的精确度和耗时。此外，算法使用模块度概念，对网络拓扑结构进行准确衡量，同时引入增量模块度指标计算表达式，以实时掌握拓扑结构发现算法指标的变化情况。【结果】为验证所提算法的有效性，利用智能电网实际通信数据集进行仿真，数据集包含115个用电单位的616条通信连接数据。仿真结果表明，与经典Louvain算法相比，所提算法在检测效率和运行耗时上均有显著优势。归一化互信息量指标的对比分析显示，所提算法在参与节点数量较多时，具有更高的归一化互信息量和更低的平均运行耗时。算法在大规模网络中具有优势，尽管在小规模网络中表现稍逊。通过实际数据集仿真可知，基于时间局部性的拓扑结构发现算法在大规模智能配电网络的精准发现方面具有明显优势，性能表现突出，为智能电网领域提供优化网络拓扑结构发现的策略。【结论】综上所述，基于时间局部性拓扑结构发现算法的创新性在于将时间局部性原理应用于网络社区发现，为复杂网络社区发现算法的研究提供了新的视角和方法，对相关领域的研究具有参考意义。未来将考虑该算法在小规模网络中的应用问题，并进一步分析算法的鲁棒性。

关键词

复杂网络 / 拓扑结构 / Louvain算法 / 社区发现算法 / 判定准则 / 时间局部性 / 运行耗时 / 模块度

基金资助

国家自然科学基金项目(52077146); 国网西南分部应用建设项目(71999821N005)