大规模图聚类优化算法研究

论文摘要

当前以社交网络为代表的复杂网络规模庞大且充满活力,如Twitter的日活跃用户数量超过为1.34亿,Snapchat的日活用户数超2亿,Facebook的月活用户突破20亿。这些海量数据构成了超大规模的社交网络图,类似的网络还包括交通网络,智能电网网络,生物网络,学术协作网络等。复杂网络提供了一种自然而有效的方法模拟各个领域中复杂的现实世界系统,由于现实世界网络在许多范围内都表现为有意义的结构社区,有效地挖掘大规模网络的结构信息具有重要的研究价值和意义。对复杂网络的聚类可以从不同的视角上进行研究,可以检测整个网络社区结构,也可以查询某些节点所属的局部社区,或者探索整个网络的演变方向等。随着新生信息技术的进步,不同领域中真实网络数据集迅速增加,网络数据集的规模和复杂性正呈数量级的增加。在各种科学领域中,图聚类是分析、建模和预测复杂网络演变的有效工具。图聚类中,簇通常是一组节点的集合,其中簇内节点彼此连接到其他组成员的可能性更大,或者说节点间的相似度更高。许多学者尝试解决图聚类问题,如基于启发式算法,图分割算法,标签传播算法,在面对大规模图聚类问题时缺乏有效的框架,聚类指标较差,分析理论公式复杂,计算复杂度高而令人望而却步。如何处理大规模网络图数据仍然是一个非常困难的挑战:大量数据、不规则数据访问模式和计算密集型。针对已有工作的不足,本文研究大规模图聚类挖掘相关技术,设计了快速图聚类模型、提出了基于高阶结构的图聚类模型及面向大规则复杂网络的并行距离动态模型,主要工作如下:（1）针对大规模复杂网络的节点之间缺乏有效地全局距离度量方式,提出了一种基于随机路径抽样的图节点距离表示方法,可以快速而有效的求解节点间的全局距离,当采样路径超过到一定比例时,准确率就会有较高的质量保证。为解决密度峰聚类算法无法有效地处理网络图中的稀疏区域,提出了一种局部K-近邻密度,可以实现对局部稀疏图聚类的检测,而不是简单地将其合并到其他聚类中,或者将其视为噪音节点。考虑到常规的密度峰图聚类模型对于异常点存在误分配的情况,设计了二度优化规则:直接邻居连接规则和S-Core-KNN连接规则,能够识别被误分配的噪音点,减少异常噪音节点数量。实验结果表明,RPDPC算法具有较好的社区结构发现性能,可以高效的完成图聚类任务,在稀疏网络也能够发挥较好的性能。（2）复杂网络图聚类任务除了检测社区结构之外,对特殊角色节点（如异常节点和枢纽节点）的识别也是理解复杂网络的功能结构的一项有价值的任务。如何检测复杂网络中的社区结构以及识别关键角色节点已成为一项具有挑战性的问题。基于密度的图聚类算法如SCAN,能够在一定程度上发现复杂网络中的社区结构,并识别出复杂网络中的异常节点和枢纽节点。然而,传统算法仅从单个节点或边的角度出发,并未考虑对复杂网络中的高阶结构信息。为此,提出了一种新颖的高阶密度图聚类模型（HSCAN）,基于高阶结构连接密度实现对复杂网络中的社区结构,枢纽节点和异常节点的识别。考虑到传统的基于密度的聚类算法存在参数异常敏感问题,及其核心节点的选取存在一定的随机性问题,提出了基于社区节点的相似度衡量指标,当存在多个节点满足核心节点备选条件时,优先选择与社区相似度最大的节点作为核心节点完成下一阶段社区扩充的种子。实验结果表明,提出的高阶密度图聚类算法可以在多项式时间内完成复杂网络中的社区结构检测,识别枢纽节点和异常节点。（3）考虑到复杂网络中存在多个节点形成的高阶混合结构,而基于单个顶点或边的传统聚类方法不能满足要求。基于高阶结构密度图聚类模型具有较好的聚类质量,但时间复杂度也较高,为此提出了一种局部高阶图聚类算法（MLEO）。首先,引入了一个新的聚类质量评分标准（局部Motif率）,可以更有效地反映高阶结构的聚类密度。然后,提出了一种局部高阶扩展算法,使用贪婪的方法来最大化聚类质量评分。此外,在此基础之上提出了一种新的种子处理策略（Motif-seed）,它扩展节点度的概念（M-degree）,通过获得具有更好聚类质量分数的初始社区来改进最终社区。研究结果表明,提出的策略可以比其他方法获得更好的性能,尤其是混合参数的值达到0.6以上时。（4）针对经典的距离动态模型无法快速处理超大规模（上亿级边）图聚类问题,提出了面向超大规模网络的并行图聚类算法（H-Attractor）。首先基于局部领导力模型建立节点间强弱链接关系的约束,在动态交互之前加入先验约束,以此来减少参与计算边的数量。然后定义了收敛系数以判断动态交互过程是处于慢收敛还是非收敛状态。在动态交互过程中,当非收敛距离的百分比小于收敛系数时,提前预判断距离的最终值。最后基于双克隆图划分方法实现了并行距离动态模型,实验结果表明算法处理大规模网络（例如Uk-2007）的时效性和准确性,在并行度为4和32时的执行时间分别约为10小时和2小时。改进的并行距离动态模型具有收敛速度快,检测结果准确,具备快速处理超大规模的网络的特点。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 研究背景和意义
•     1.1.1 图聚类与社区结构挖掘
•     1.1.2 图聚类研究意义
•     1.1.3 大规模复杂网络图聚类需求
•   1.2 国内外研究现状
•     1.2.1 经典图聚类算法
•     1.2.2 基于密度及密度峰的图聚类方法
•     1.2.3 面向高阶结构的图聚类方法
•     1.2.4 基于动态过程的图聚类方法
•   1.3 面临问题
•   1.4 研究内容和组织结构
• 第2章 大规模图聚类相关技术
•   2.1 复杂网络与图论基础
•     2.1.1 一些基本定义
•     2.1.2 图论的代数表达方法
•     2.1.3 复杂网络与社区结构
•   2.2 随机游走理论基础
•   2.3 相似性表示方法
•   2.4 评价指标
•   2.5 并行编程模型
•     2.5.1 共享内存
•     2.5.2 分布式存储器
•     2.5.3 MapReduce并行框架
•   2.6 本章小结
• 第3章 基于随机路径采样的密度峰图聚类算法
•   3.1 引言
•     3.1.1 主要问题
•     3.1.2 主要贡献
•   3.2 密度峰聚类模型
•   3.3 随机路径抽样密度峰图聚类算法
•     3.3.1 随机路径抽样距离
•     3.3.2 局部k-近邻密度
•     3.3.3 局部密度峰图聚类方法
•     3.3.4 异常噪音点分配策略
•     3.3.5 时间复杂度分析
•   3.4 实验评估
•     3.4.1 实验数据集
•     3.4.2 聚类结果决策分析
•     3.4.3 K近邻参数影响分析
•     3.4.4 噪音点优化参数分析
•     3.4.5 人工合成SW网络
•     3.4.6 真实网络数据集
•   3.5 本章小结
• 第4章 基于高阶结构密度的图聚类算法
•   4.1 引言
•     4.1.1 主要问题
•     4.1.2 主要贡献
•   4.2 密度图聚类
•   4.3 高阶结构密度图聚类
•     4.3.1 高阶结构密度
•     4.3.2 核心节点选取策略
•     4.3.3 HSCAN算法
•     4.3.4 时间复杂度分析
•   4.4 实验评估
•     4.4.1 实验环境
•     4.4.2 参数k的敏感性分析
•     4.4.3 人工网络
•     4.4.4 真实网络
•   4.5 本章小结
• 第5章 基于局部扩充的高阶图聚类算法
•   5.1 引言
•     5.1.1 主要问题
•     5.1.2 主要贡献
•   5.2 背景知识及问题定义
•     5.2.1 问题描述
•     5.2.2 Motif电导率
•     5.2.3 新的聚类质量评分
•   5.3 高阶局部扩充算法
•     5.3.1 种子阶段
•     5.3.2 扩张阶段
•     5.3.3 检查阶段
•     5.3.4 时间复杂度分析
•   5.4 实验评估
•     5.4.1 实验环境
•     5.4.2 社区结构检测
•     5.4.3 种子策略评测
•     5.4.4 参数讨论
•   5.5 本章小结
• 第6章 基于距离动态模型的并行图聚类算法
•   6.1 引言
•     6.1.1 主要问题
•     6.1.2 主要贡献
•   6.2 强弱链接关系模型
•   6.3 优化的距离动态模型
•     6.3.1 新的互动模式
•     6.3.2 并行策略及图划分
•     6.3.3 慢收敛优化模型
•     6.3.4 并行的动态交互
•     6.3.5 并行图聚类
•     6.3.6 运行时间分析
•   6.4 实验评估
•     6.4.1 实验环境
•     6.4.2 模型优化结果分析
•     6.4.3 时间分析
•     6.4.4 扩展性能
•   6.5 本章小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读博士学位期间的研究成果
•   发表学术论文情况
•   本人参与课题已获的软件著作权
• 附录B 攻读博士学位期间参与的科研课题

文章来源

类型: 博士论文

作者: 何庭钦

导师: 蔡立军

关键词: 复杂网络,随机游走,高阶图聚类,密度峰,电导率,距离动态模型

来源: 湖南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 湖南大学

分类号: O157.5

DOI: 10.27135/d.cnki.ghudu.2019.004011

总页数: 133

文件大小: 6544k

下载量: 5