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

发布时间：2020-11-20 12:49

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

西安电子科技大学硕士学位论文8图2.1 算法的遗传表示与解码过程算法的编码与解码过程如图 2.1 所示。该图例展示了在算法初始化阶段，TJA-net赋予每个节点一个唯一的标签，代表着该节点所属的社区标签。通过解码，拥有相同标签值的节点将被划分到同一社区。如同图 2.1 所示，图中用不同的颜色与形状来表示不同的社区，由于节点集{1, 2, 3, 4, 5}具有相同的社区标签而被划分为社区 1；同理，节点集{6, 7, 8, 9}被划分到社区 2 中。2.2.2预处理策略在介绍 TJA-net 算法的预处理策略之前，本节首先给出一些相关背景知识。KNN算法[47]是机器学习算法中比较成熟且较为简单的分类算法之一，它是由 Cover 与 Hart于 1967 年提出的用于解决分类问题的算法。直观来讲

(a) 社区检测示例图 (b) 利用 ILPA 完成图图2.2 ILPA 预处理实例为了更好的解释 ILPA 与 LPA 的不同之处，本章使用图 2.2 来进行说明。由于 (a) 中的节点集{v1, v2, v3}属于社区 C1 而被标记为“1”，而节点集{ v5, v6, v7, v8于社区 C2，被标记为“2”。此时的节点 v4为待处理节点。利用 LPA 对节点 v4进类，可以看出此时节点 v4与社区 C1、社区 C2 的连接数相等。因此，利用 LPA对此时的节点 v4进行聚类。与此相比，ILPA 则首先计算节点 v4与其邻接节点{v1 v5, v7, v8}的亲密程度，计算结果如表 2.2 所示。示例中，设置 K = 3，计算得到 v4最亲近的节点集为{v1, v2, v3}，其类别最多的社区标签为 1，因此将节点 v4划社区 C1，如图 2.1 (b)所示。表2.2 节点 v4与其邻接节点的亲近度邻接节点 v1v2v3v5v7v社区标签 '1' '1' '1' '2' '2' '2亲近度值 3 3 3 2 3 2

合的阈值δ = 1，算法的迭代次数iterm = 5，目标函数中参数λ的取值为{0.2, 0.3, 0.4, ...,1.0}。则算法运行 30 次所得到的最佳 NMI 值如图 2.3 所示。图2.3 算法在 GN 扩展网络上所得的 NMI 值对比从图 2.3 中可以看出，TJA-net 算法与 Memetic-net 算法在 0.2 ≤ λ ≤ 0.5 时的效果基本相同，而 CSA-net 算法在 0.2 ≤ λ ≤ 0.4 且 γ = 0.4 时要稍微优于其他算法。此外，TJA_v-net 算法在 λ ≤ 0.6 时表现得不如其他算法，但是在 0.8 ≤ λ ≤ 1.0 时，无论是TJA_v-net算法还是TJA-net算法均要比CSA-net算法和Memetic-net算法表现得优秀。需要注意的是，即使当社区结构比较明显时，即 0.2 ≤ γ ≤ 0.3，利用了 LPA 算法作为预处理策略的 TJA_v-net 算法也无法检测出真实的社区结构
【相似文献】

相关期刊论文 前10条

1 张明红;佘廉;耿波;;基于情景的结构化突发事件相似度研究[J];中国管理科学;2017年01期

2 陈叶斐;张学军;黄卫东;;基于干扰相似度的多话题演化模型[J];电信科学;2017年09期

3 任雪利;代余彪;;软件相似度在成本估算中的应用[J];计算机应用与软件;2015年06期

4 谭明超;刁兴春;曹建军;冯径;;一种基于函数依赖的属性相似度调整算法[J];上海交通大学学报;2015年08期

5 陈立凤;;河马找亲戚[J];学生之友(童花果);2016年12期

6 周娴莉;;十个中文流行语翻译[J];初中生辅导;2016年36期

7 杜碧涵;;母爱[J];少年月刊;2017年05期

8 张呈宇;;热点话题相似度常用算法比较[J];好家长;2017年12期

9 仇丽青;陈卓艳;;基于共同邻居相似度的社区发现算法[J];信息系统工程;2014年05期

10 詹雪艳;林兆洲;段天璇;李磊;乔延江;;色谱指纹图谱相似度方法的适应性研究[J];中国中医药信息杂志;2012年05期

相关博士学位论文 前10条

1 高欣健;多模态相似度学习方法研究[D];合肥工业大学;2017年

2 夏云庆;IHSMTS系统中启发式类比翻译处理机制（HATM）的设计与实现[D];中国科学院研究生院（计算技术研究所）;2001年

3 武威;异质数据相似度学习及其在网络搜索中的应用[D];北京大学;2012年

4 张明西;信息网络中的相似度搜索问题研究[D];复旦大学;2013年

5 朱娜斐;基于RTT相似度的网络延迟估测理论和方法[D];北京工业大学;2012年

6 钱鹏飞;基于模糊相似度的异构本体映射、合并及校验方法的研究[D];上海交通大学;2008年

7 朱笑尘;异质过程数据集成与修复[D];清华大学;2015年

8 贾连印;内存数据库中集合相似度及集合包含问题的研究[D];华南理工大学;2012年

9 崔晓兰;面向在线抱怨自动处理的推荐方法研究[D];华中科技大学;2017年

10 马海平;基于概率生成模型的相似度建模技术研究及应用[D];中国科学技术大学;2013年

相关硕士学位论文 前10条

1 刘佳雯;语句相似度匹配在自动问答系统中的应用与实现[D];南京邮电大学;2018年

2 边青全;基于动力学模型的网络社团检测算法研究[D];西安电子科技大学;2018年

3 程亚男;在线问答社区意见型问题的答案摘要研究[D];大连理工大学;2018年

4 戴东庆;鲁棒局部保持投影技术研究及应用[D];西安电子科技大学;2018年

5 刘欢;基于节点邻域信息与相似度矩阵的社区检测[D];西安电子科技大学;2018年

6 方敏;基于节点相似度的线要素匹配方法设计[D];北京建筑大学;2018年

7 张学理;基于多因子标签相似度的标签聚类算法的研究[D];辽宁大学;2018年

8 李凯翔;产科知识图谱的构建与研究[D];郑州大学;2018年

9 李超男;基于节点相似度的社会网络社团发现的算法研究[D];重庆师范大学;2018年

10 花凌锋;面向位置的移动新闻推荐研究[D];安徽理工大学;2018年

本文编号：2891438