社交网络中的子图结构挖掘研究

论文摘要

社交网络以社交个体之间社交活动为研究对象,将其抽象为个体间相互作用的网络.从社交网络进行子图结构挖掘对更深层次地认识客观世界是非常有意义的,也是社交网络中安全性问题分析的重要基础.社交网络产生的用来记录个体之间关系的数据被称为关系数据.最为常见的用来描述关系数据的数据结构是图.图有有向和无向之分,其中无向图可以很容易地转化为有向图,反之则不能,故研究针对有向图的子图结构挖掘方法比无向图更为重要.针对信息安全问题,对社交网络中存在的各种子图结构进行挖掘是非常有必要的.例如,以智能体为社交个体的多智能体协同系统网络中,强连通分量结构对于智能体之间信任协议的渐进收敛具有促进作用,而以社交用户为个体的加密信息传输网络中,若是存在有向圈结构,则可能引起逻辑死锁问题.当前子图结构挖掘研究中,最常用的方法是基于图论的方法.近年来,由于经典图论在处理不确定性关系数据中的缺陷,以及粗糙集在处理不确定信息方面的优势,基于粗糙集理论的子图结构挖掘研究受到了许多学者的关注.本文结合粗糙集理论和图论,研究如何从刻画现实社交网络的有向图中挖掘子图结构,以及其在信息安全领域的应用问题,主要创新研究内容和成果包括:（1）针对强连通分量的挖掘问题,刻画了粗糙集理论与图论在有向图处理中的一种对应关系,并设计了基于粗糙集的强连通分量挖掘算法,以及其并行实现方案.粗糙集是一种有效的处理不确定信息的数学工具,可以从信息表这种属性数据中挖掘知识.然而,对于有向图这种关系数据,目前还没有基于粗糙集理论的方法对其进行处理,更不用谈从不确定的有向图中挖掘子图结构.为了突破粗糙集理论在有向图子图结构挖掘任务中的局限,在二元关系和有向图之间的互表达性这一基础上,刻画了有向图处理中粗糙集理论与图论之间的对应关系;以这种对应关系为理论基础,针对简单有向图中强连通分量子图结构挖掘任务,提出了一种基于粗糙集的强连通分量挖掘算法（RSCC）.进而,为提高强连通分量挖掘效率,提出了RSCC算法的并行实现方案（PRSCC算法）.通过实验验证了上述算法的有效性和高效性.上述算法的提出首次实现了基于粗糙集的有向图子图结构挖掘,将粗糙集理论作为一种新的强连通分量挖掘模型方法引入到有向图子图结构挖掘研究,为未来利用粗糙集方法从不确定有向图中挖掘子图结构奠定了基础.（第2章）（2）通过对有向图顶顶点集的粒化,提出了一种基于粒化策略的强连通分量挖掘算法,提高了挖掘效率.粗糙集理论与图论的对应关系是粗糙集理论应用于关系数据子图结构挖掘的理论基础.为了说明RSCC算法利用粗糙集6)步上近似和6)步相关集算子来挖掘强连通分量这种有向图子图结构的合理性,证明了这两个粗糙集算子与宽度优先搜索之间的等价性,进一步扩充了粗糙集理论和图论之间的对应关系内容.此外,利用相关集、下近似集和上近似集这三个粗糙集概念对强连通分量进行了分析,发现在挖掘强连通分量时,顶点间存在三种相关性.继而根据这三种相关性提出了有向图顶点集粒化策略.将RSCC算法与顶点集粒化策略相结合,提出了基于粒化策略的强连通分量挖掘算法（GRSCC）.实验结果说明了新算法具有更高的挖掘效率.（第3章）（3）基于启发式式深度优先搜搜索策略,设计了强连通分量中的一种有向圈挖掘算法,将其应应用于加密信息传输网络,可为逻辑死死锁检测提供解解决方案.有向圈是有向图中的一种重要子图结构,是强连通分量的一种特例,因此有价值强连通分量中必然可以挖掘到有向圈.基于这一事实,提出了一种基于启发式深度优先搜索的有向圈挖掘算法（HL-DPC）.进而,将该方法应用于加密信息传输网络,可为逻辑死锁检测等信息安全问题提供解决方案.实验结果说明了该算法的有效性,及使用启发式信息来提高挖掘效率的必要性.（第4章）（4）提出了一种基于顶顶点坐标的可视化结果对称性度量,实现了有向圈和星星型子图的的对称性可视化.关系数据可视化是关系数据子图结构挖掘研究的分支之一.图布局就是实现关系数据可视化的一种重要手段.首先,对称性这种图布局美学准则需要被客观地度量.因此,提出了基于顶点坐标计算的对称性度量方法,从理论角度证明了该度量对于布局的等比例放缩以及旋转是鲁棒的,实验结果也验证了这一点.该度量的鲁棒性与人类关于对称性的理解是相一致的.其次,从子图结构挖掘的角度来说,对于有向圈和星型子图这两种具有本质上对称性的子图结构,存在可视化需求,需要一种图布局算法将这两种子图结构对称地、突出地布局出来.因此,提出了一种力导向图布局算法（FDS）来满足对有向圈和星型子图的可视化需求.通过实验测试,对于有向图所包含的有向圈和星型子图结构,FDS算法可将其明显地,更为对称地布局出来.本算法在时间效率上也有优势.（第5章）

论文目录

• 摘要
• abstract
• 第1章 绪论
•   1.1 本文研究背景
•   1.2 相关研究工作
•     1.2.1 基于图论的关系数据子图结构挖掘
•     1.2.2 基于粗糙集的关系数据子图结构挖掘
•     1.2.3 关系数据可视化
•     1.2.4 待解决的关键问题
•   1.3 本文的主要研究内容及成果
•   1.4 本文的研究工作和组织结构
• 第2章 基于粗糙集的强连通分量挖掘
•   2.1 引言
•   2.2 广义粗糙集与图论基本知识
•     2.2.1 广义粗糙集基本知识
•     2.2.2 图论基本知识
•   2.3 面向有向图的广义粗糙集模型
•     2.3.1 简单有向图引导出的二元关系
•     2.3.2 粗糙集与图论之间的对应关系
•   2.4 有向图的强连通性和强连通分量
•     2.4.1 有向图的强连通性
•     2.4.2 有向图中的强连通分量
•   2.5 基于粗糙集的强连通分量挖掘算法
•     2.5.1 基于粗糙集的强连通分量串行挖掘算法
•     2.5.2 基于粗糙集的强连通分量并行挖掘算法
•     2.5.3 实例分析
•   2.6 仿真实验
•   2.7 小结
• 第3章 基于粒化策略的强连通分量挖掘
•   3.1 引言
•   3.2 k步上近似和k步R相关集与BFS之间的等价关系
•   3.3 RSCC算法的局限性分析
•   3.4 基于粒化策略的强连通分量挖掘算法
•     3.4.1 算法描述
•     3.4.2 实例分析
•   3.5 仿真实验
•   3.6 小结
• 第4章 基于启发式深度优先搜索的有向圈挖掘
•   4.1 引言
•   4.2 有向圈相关定义
•   4.3 启发式有向圈挖掘算法（HL-DPC算法）
•     4.3.1 HL-DPC算法描述
•     4.3.2 HL-DPC算法时间复杂度分析
•     4.3.3 实例分析
•   4.4 仿真实验
•     4.4.1 实验环境与数据集
•     4.4.2 HL-DPC算法有效性实验
•     4.4.3 HL-DPC算法使用两个启发式信息的必要性实验
•   4.5 小结
• 第5章 绘制有向圈与星型子图的力导向图布局算法
•   5.1 引言
•   5.2 相关的图布局基本知识
•     5.2.1 相关定义
•     5.2.2 FR算法
•   5.3 基于顶点坐标计算的对称性度量
•   5.4 绘制有向圈和星型子图的力导向图布局算法（FDS算法）
•     5.4.1 基于圆环定位的有向圈布局算法
•     5.4.2 叶顶点布局算法
•     5.4.3 FDS算法描述
•     5.4.4 实例分析
•   5.5 仿真实验
•   5.6 小结
• 第6章 结论与展望
•   6.1 本文工作总结
•   6.2 未来工作展望
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果

文章来源

类型: 博士论文

作者: 徐泰华

导师: 王国胤

关键词: 社交网络,信息安全,有向图,粗糙集,图论

来源: 西南交通大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 西南交通大学

分类号: O157.5;TP309

DOI: 10.27414/d.cnki.gxnju.2019.001836

总页数: 119

文件大小: 5062K

下载量: 105