基于线性谱统计量的社区发现算法

发布时间：2021-01-16 18:19

　　社区发现作为网络研究的重要课题,其应用涉及到从查找通信网络和生物网络社区到金融风控中老赖识别等多个领域,受到了统计学,物理学和计算机科学等不同学科的广泛关注.然而过去使用的聚类算法多数要求社区个数k已知.我们将要通过假设检验算法自动获取社区数目k.在随机块模型假设下,单个社区可以看做是ER图,本文从理论上证明了ER图邻接矩阵的线性谱统计量弱收敛到N（0,15）.从而在原假设为ER图的情况下,提出基于线性谱统计量的假设检验算法检验网络是否是ER随机图,创新性地将高维随机矩阵的线性谱统计量等相关定理用于随机网络的社区发现问题.本文结合基于motif谱聚类算法与基于线性谱统计量的假设检验算法提出两种k未知时的聚类算法框架.本文的难点主要集中在两方面,第一个难点是证明经过标准化的ER图邻接矩阵的线性谱统计量弱收敛到高斯分布,第二个难点是如何基于线性谱统计量的假设检验算法构建k未知的聚类算法. 

【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校

【文章页数】：56 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 国内外研究现状
    1.3 主要研究内容
    1.4 论文组织结构
第二章 预备知识
    2.1 复杂网络
        2.1.1 图的基本定义
        2.1.2 复杂网络性质
    2.2 随机网络模型
        2.2.1 Erd（?）s-R（?）nyi随机图模型
        2.2.2 广义随机图模型
        2.2.3 随机块模型
        2.2.4 度校正随机块模型
    2.3 社区发现算法
        2.3.1 谱聚类算法
        2.3.2 基于模块度的算法
        2.3.3 基于最大特征根的假设检验社区发现算法
第三章 ER随机图线性谱统计量的中心极限定理
    3.1 大维随机矩阵谱理论
        3.1.1 Wigner矩阵与半圆律
        3.1.2 Wigner矩阵线性谱统计量的中心极限定理
    3.2 ER随机图线性谱统计量的中心极限定理
    3.3 定理证明
第四章 社区发现方法及算法
    4.1 假设检验算法
    4.2 基于假设检验的聚类算法
    4.3 基于motif的谱聚类算法
第五章 模拟
    5.1 假设检验算法对比
    5.2 其他块模型模拟结果
    5.3 聚类算法评价指标
    5.4 真实网络
第六章 结论与展望
    6.1 结论
    6.2 展望
参考文献
致谢



本文编号：2981307