基于节点邻域信息与相似度矩阵的社区检测

摘要

复杂网络是对现实复杂系统的抽象化描述，如社交网络、科学合作网络、生物蛋白系统等。社区是用于描述复杂网络中连接紧密的节点簇或模块，复杂网络的社区检测就是利用网络中特殊的拓扑结构来识别这些连接紧密的节点簇，有时也被称为复杂网络的聚类。对复杂网络进行社区检测，能够帮助人们发现网络中潜在的结构模式，并进一步理解网络的组织功能。近些年来，研究者从不同的角度设计出许多复杂网络的社区检测算法，但是大多数算法都是针对于单一的网络结构，即无符号复杂网络。然而，现实的复杂系统往往涵盖着多种特征，如符号网络可以描述实体之间的多种关系，而属性网络不仅可以描述实体之间的关系，还可以描述实体的属性或特征。这些网络能够更真实地描绘现实系统的复杂性，给社区检测问题带来更多信息的同时也带来了更大挑战。此外，充分利用节点的邻域信息，更为针对性地设计出合理的操作步骤，能够更大程度上提高算法的检测精度。针对以上现存算法普遍存在的问题，本文对不同类型的网络进行深层次研究。设计出具体的解决方案如下： 1）提出一种基于节点邻域信息与三步策略的社区检测算法。首先，算法将K近邻思想引入标签传播算法，并提出网络的预划分策略。该策略充分考虑节点间的亲近度，并且克服了标签传播算法在社区结构较为模糊的情况下无法识别社区的缺陷，使得算法初期能够精确识别局部连接紧密的子社区。其次，在预处理的基础上设计了基于社区互隶属度的子社区融合策略，并对亲密度高的子社区进行有效合并。最后，一种精制策略被用来对误划分的节点进行重划分。算法对初始点个数及迭代次数的依赖性很小，因此能够节省大量时间成本，适合大规模网络的社区检测问题。 2）提出一种基于K节点更新策略与相似度矩阵的多目标社区检测算法。首先，建立泛化的相似度函数来计算无符号网络或符号网络的相似度矩阵，并根据节点的相似度矩阵设计了一种预划分技术，这种预划分技术仅仅考虑相似度值较高的部分节点，能够有效地避免噪声节点对标签更新过程的影响，因此可以将连接紧密的节点迅速聚集成局部子社区。其次，交叉合并算子被设计并用于合并预处理策略所得到的子社区，以及基于相似度矩阵的变异算子被用于调整边界节点所属的社区。最后，构建多目标优化模型并用于处理不同类型的网络。因此，算法能够处理无符号网络与符号网络的社区检测问题。 3）提出一种基于边结构与节点属性的多目标离散粒子群社区检测算法。首先，该算法计算边结构的相似性矩阵与节点的属性相似度矩阵，通过混合参数将两者结合得到网络的混合相似度矩阵，并基于此设计一种更新邻居节点标签的初始化策略。其次，考虑到粒子群算法的易操作性以及其时间效率较高，该算法首次将多目标离散粒子群算法引入属性网络中。最后，设计属性网络的平均属性相似度函数并用于构建多目标优化模型，能够兼顾社区内部节点连接紧密的同时使得社区内节点属性同质化程度高。

目录

第一个书签之前

摘要

ABSTRACT

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.1 课题研究背景及意义

1.2 复杂网络的社区结构概述

1.3 社区检测算法国内外的研究现状

1.4 论文主要内容与结构安排

第二章 基于节点邻域信息与三步联合策略的社区检测

2.1 引言

2.2 基于节点邻域信息与三步联合策略的社区检测算法

2.2.1 遗传表示与初始化

2.2.2 预处理策略

2.2.3 社区融合策略

2.2.4 局部节点的精制策略

2.2.5 目标函数—模块度密度

2.2.6 算法的整体框架

2.3 仿真实验及结果分析

2.3.1 评价指标

2.3.2 对比算法

2.3.3 测试网络

2.3.4 人工网络的实验结果与分析

2.3.5 现实网络的实验结果与分析

2.3.6 算法的有效性分析

2.3.7 算法运行时间分析

2.4 本章小结

第三章 基于K节点更新与相似度矩阵的多目标社区检测

3.1 引言

3.2 相关工作与模型建立

3.2.1 结构平衡理论

3.2.2 多目标优化模型的构建

3.2.3 契比雪夫方法

3.3 基于K节点更新与相似度矩阵的多目标社区检测算法

3.3.1 节点相似度矩阵与K节点更新策略

3.3.2 基于局部节点集的交叉融合算子

3.3.3 基于相似度矩阵的变异算子

3.3.4 算法的整体框架

3.4 仿真实验及结果分析

3.4.1 评价指标

3.4.2 对比算法与参数设置

3.4.3 无符号网络的实验结果与分析

3.4.4 符号网络的实验结果与分析

3.5 本章小结

第四章 基于边结构与节点属性的多目标离散粒子群社区检测

4.1 引言

4.2 相关工作与模型建立

4.2.1 相似度计算方法

4.2.2 模型建立

4.3 基于边结构与节点属性的多目标离散粒子群社区检测算法

4.3.1 遗传表示与粒子群的初始化策略

4.3.2 粒子的更新策略

4.3.3 基于近邻的变异操作

4.3.4 算法的整体框架

4.4 仿真实验及结果分析

4.4.1 评价指标

4.4.2 测试网络

4.4.3 参数敏感度分析

4.4.4 算法在社交网络上的实验结果与分析

4.4.5 算法在文本网络上的实验结果与分析

4.5 本章小结

第五章 总结与展望

5.1 本文总结

5.2 未来工作展望

参考文献

致谢

作者简介

1. 基本情况