网络数据局部分割的模型与算法

发布时间：2020-09-29 15:29

　　聚类是理解大规模数据内在规律和结构特性的重要手段。很多实际问题,数据和数据间的关联用图或者网络来描述,此时聚类问题也被称为网络和图的分割问题。目前的图分割算法大多数是对无向图进行分割,有向图分割的研究还处于起步阶段。无向图的邻接矩阵具有对称性质,可以充分利用谱的性质得到有效算法。而有向图的邻接矩阵是非对称的,这使得有向图的分割问题变得复杂。用有向图无向化的方法来处理有向图分割问题会丢失层级结构等有向图特有的结构信息,所以研究本质上基于有向图内在结构和性质的分割算法具有重要的理论意义和实用价值。Nevanlinna奖获得者,耶鲁大学Spielman教授2008年提出了一种复杂度接近线性的无向图局部分割算法[1],称为Nibble算法。该算法利用顶点度的信息构造随机游走规则,能够快速有效地提取初始节点所在的局部团簇。Nibble算法使用的是随机路的思想,因此避开了直接求解一个非对称矩阵的特征值问题,因此有可能用它来尝试解决有向图的分割问题。我们同时考虑有向图中每一顶点的出度和入度,改变随机路在点之间的转移概率,得出一个具有类结构的块。对于赋权的网络,可以把一条弧上权值看做边的个数,可以计算转移概率,因此可以用同样的方法处理赋权网络。我们对算法中转移概率矩阵中参数的选取以及度的使用规则等进行了分析讨论。本文以2008年JCR的关于学术期刊相互引用之间的部分数据构成的有向网络作为实例进行了实验来考察算法的效果。在45个期刊构成的有向网络中,以一个基础数学期刊为起点,算法输出结果中全是基础数学期刊而且分出这个网络中的所有基础数学期刊。在1582个期刊构成的有向网络中,我们仔细考察了输出结果的前70个期刊。以不同类别、等级的期刊为起始点搜索聚类,算法的输出均为与初始节点密切相关的子类。实验结果,表明了有向化推广后的Nibble算法对有向图进行局部分割和聚类的有效性。
【学位单位】：清华大学
【学位级别】：硕士
【学位年份】：2015
【中图分类】：O157.5
【文章目录】：
摘要
abstract
第1章引言
    1.1 聚类的概念和算法研究
    1.2 网络数据的局部分割模型
    1.3 有向网络数据的分割问题
第2章无向图聚类算法
    2.1 K-means算法
    2.2 谱聚类和谱对分法
    2.3 Kernighan-Lin 算法
    2.4 无向图的Nibble算法
    2.5 算例
        2.5.1 数据来源
        2.5.2 实验结果及分析
第3章 Nibble处理有向图的局限性
第4章有向化Nibble算法
    4.1 有向化Nibble算法
    4.2 计算实例与结果结果
    4.3 对算法的两点说明
        4.3.1 弧上的概率选择
        4.3.2 对顶点度的选取
    4.4 Nibble算法的拓展
第5章总结
    5.1 本文结果总结
    5.2 有向图Nibble算法的优缺点和改进方向
参考文献
致谢
附录A 45 个期刊的名称
附录B 有向图中的 Nibble 算法以 22 号期刊为起始点，?=0.7 输出结果的前 70
附录C 算法主要程序
个人简历、在学期间发表的学术论文与研究成果

【相似文献】