一、前言
在现如今的信息化时代，随着互联网的应用和科学技术的不断进步，不同应用领域的数据呈现大规模的增长，而图作为一种用于信息表示的灵活的数据结构，图的规模也在日益增大并不断动态更新，因此大型图的分解，成为当今研究的一个重要问题。同时，可视化算法是对大规模复杂网络进行一般分析和研究其体系结构的一种方便的方法，也是一个有待研究的重要问题。
本次毕业设计在于利用稠密子图分解技术，完成一个图数据可视化原型系统。其中K-core、K-truss模型是较为简单的分解模型，在阅读文献的基础上，本文将对其具体的实现以及每一种算法适用的范围、优缺点进行概述；其次，本文概述了现有的一个基于k-core分解的大规模可视化工具；最后，本文总结了本课题提出的研究内容的意义所在。
二、正文
研究网络的拓扑结构对于一些问题非常重要。对于大规模网络，主要有两种简单的子图模型：k-core和k-truss；同时，基于k-core分解的策略，开发了一个通用的可视化算法，用来比较各种网络的结构属性，并突出它们的层次结构。
考虑一个无向图，其中V代表顶点集，E表示边集，n=|V|表示顶点的个数，m=|E|表示边的个数。对于图G中一个顶点v，NG(v)表示它的邻居集合，则v的度数为|NG(v)|，用dG(v)表示；对于图G中的一条边e，sup (e)表示边e的支持度， 即边e包含的三角形的个数。
2.1 k-core分解
k-core分解是将图从外部到更中心的顶点划分为多个层。它要求对于图G中的极大子图GK，GK中的所有顶点的度数dG(v) ge; k。计算图中k-core的算法有：GraphChi上的Montresor算法（GC_M）、Webgraph上的Batagelj和Zaversnik算法（WG_BZ）、Webgraph上的Montresor算法（WG_M）以及EM-core算法。GraphChi是一个现代的、通用的图形引擎，它采用一种新的技术来处理来自磁盘的大量数据，并使用“以顶点为中心”的计算模型；Webgraph是一个图数据压缩框架，它提供了一个API来访问一个使用延迟解压技术的压缩图数据。使用GraphChi和Webgraph的优点是：由于它们是通用的图形系统，提供了处理图形的简单API，因而简单、便于扩展和维护。
GC_M算法的主要思想是：为每一个顶点保持一个称为顶点值得估计值，该值是其相关性得上限，初始化为该顶点的度数。随着算法的进行，在每个迭代中使用updata（）函数进一步收紧上限，逐渐改变每个顶点的估计值，直至在终止之前达到真正的核心值。而update（）的主要思想为：根据从边内读取的值计算顶点相关性的更严格上限，在每次迭代中，顶点通过向外边缘写入它们当前的上界，广播给邻居，并通过读取内边缘的值来接收传入消息。分析结果表明：对于大多数图形数据集，该算法在几十次迭代中结束，在消费级PC上大约花费几分钟；而对于大规模图形数据集，需要进行上百次迭代，花费几个小时的时间。
WG_BZ算法的主要思想：通过递归删除具有最低程度的顶点和计算分解。在算法中有3个数组，L将保存每个顶点的核心值，d保存每个顶点的度数，D保存每个可能度数的一组具有该度数的顶点集。初始化之后，最小度顶点i位于第一个非空集合中，i的核心值为k，记录在L中。接下来，算法从图中逻辑删除i，并处理i的邻居，i的度数递减1，同时它的邻居改变在D数组中的位置，最终算法返回L，它包含了每个顶点的核心值。分析结果表明：该算法的运行极快，对于大型数据集也只需几百秒即可产生结果。但是，它要求图形的顶点数和边数适合内存。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
