基于最小描述长度的大规模图数据结构分析

摘要

在现今网络高速发展的时代，网络空间数据与日俱增。这些大量的数据包含了现实生活中人们的隐私和信息。通过网络空间数据挖掘方法对这些数据进行信息提取，同时挖掘出数据所包含的隐私信息，是当前社交网络结构分析和网络空间安全研究的一个重要方面。出于理论研究和应用的需求，需要对大规模的网络数据进行压缩，同时进行拓扑结构挖掘，分析和理解其拓扑语义。 本文研究了在当前安全背景下网络空间中的结构数据以及图拓扑数据的结构分析问题。重点研究了子图重叠结构挖掘、子图结构语义识别与分析和图结构挖掘的问题。本文的图分析方法主要适用于社交网络，但是也可以应用到具有幂律分布的其他网络类型中去。论文通过引入最小描述长度准则，作为子图聚类、子图语义结构识别和图结构模型评估的判别标准。为统一挖掘图中的多样子结构，本文通过基于枢纽点的子图分解算法和基于自网络的子结构聚合算法，根据几类子图的短径长共性进行挖掘，获得图的分解以及子图集合。随后通过最小描述长度准则以及图编码算法对子图的结构语义进行统一地识别和挖掘。最后借助最小描述长度，将子结构组合获得图的拓扑结构聚集。通过本文的研究，对图的结构进行了挖掘和语义分析，理解了网络的结构。实验表明，本文的方法对图的拓扑结构是一个相对较好的压缩、挖掘和理解。 本文充分利用了最小描述长度准则。在图结构挖掘上，通过最小描述长度准则确定了图合并的条件和子图间的重叠关系;在图的编码和结构语义挖掘上，仍然利用最小描述长度帮助识别子图类型，结合引入应对稀疏结构的树结构模板，获得了对当前图结构聚集算法Vog的一个改进。

目录

声明

摘要

第1章绪论

1．1研究背景及意义

1．2国内外研究现状

1．2．2．大规模图数据分析方法与框架

1．2．3．基于最小描述长度的图结构研究

1．2．4．存在的问题

1．3论文组织结构及安排

第2章图结构分析基本概念与工具

2．1图论相关知识

2．2图数据结构分析相关技术

2．2．1．图结构聚类和图分解方法

2．2．2．子图挖掘技术

2．3本章小结

第3章基于最小描述长度的图数据结构挖掘算法

3．1最小描述长度

3．2问题定义与研究框架

3．3图分解算法

3．3．1．Slashburn-RS算法

3．4图结构编码与子图语义挖掘

3．4．1．子图结构语义挖掘算法

3．4．2．子图的编码

3．4．3．图模型的编码

3．5子结构组合算法

3．6 SRS-GP算法

3．7实验结果与分析

3．8本章小结

第4章基于最小描述长度的子图重叠语义挖掘

4．1 TSM算法

4．2基于枢纽点的重叠子图挖掘算法

4．2．1．HM算法

4．2．2．算法时间复杂度

4．2．3． HM-rd算法

4．2．4． HM-sd算法

4．3实验结果与分析

4．4本章小结

第5章总结与展望

5．1论文总结

5．2未来展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果