基于局部标签信息的半监督社区发现算法研究

发布时间：2020-11-18 21:56

　　 现实世界里,许多复杂系统都可以被描述成复杂网络的形式。社区结构作为复杂网络的重要特性之一,在人们的生活中扮演着重要的角色。及时、准确的发现网络中所隐藏的社区结构,进而分析复杂系统的内部特征,不仅可以指导人们的生产活动,而且对于理解并控制复杂系统也有很大的帮助。传统的社区发现算法由于时间复杂高、划分结果准确率低、需要事先指定社区规模等原因而不能得到广泛的应用。基于此,本文提出了基于局部标签信息的半监督社区发现算法,以期在时间复杂度和社区发现准确度方面都能有较好的表现。网络按其节点归属类别的多少可以分为非重叠社区的网络结构和重叠社区的网络结构,本文分别从两方面入手,对传统的社区发现算法进行改进。在非重叠社区发现领域,本文对传统的具有较快运行速度的LPA算法进行改进。首先,本文提出了结合Pearson相似度的LPA_S算法,利用网络中节点间的相似度信息来辅助标签传播过程,以此来降低标签选择的随机性。然后,本文提出了基于正标签先验信息的半监督社区发现算法LPA_SI,充分利用网络中的Must-link、Must-in等正标签先验信息,并以此来指导标签传播过程,从而大大提高了社区发现的准确率。最后,本文提出了基于正负标签先验信息的半监督社区发现算法LPA_SNI,将网络中的正标签先验信息与Cannot-link、Cannot-in等负标签先验信息结合起来,共同指导社区发现过程,使得社区发现的准确度得到了进一步的提高。通过在真实网络和人工生成网络上的实验,并分别以模块度Q和标准化互斥信息NMI来作为社区发现的准确度衡量标准,有效证明了本文所改进算法较传统LPA算法优异。此外,实验也表明,适当增加网络中正负标签等先验信息,可以明显提高非重叠社区发现的准确率。在重叠社区发现领域,本文对传统的COPRA算法进行了改进。COPRA算法时间复杂度低,但其在标签传播上仅仅考虑了网络的邻居节点信息,故其社区发现准确度不高。因此,本文首先提出了基于Pearson相似度的COPRA_S算法,结合网络中节点间的相似度信息,有效提高了社区发现的准确率。然后,本文结合网络中的少量Must-link、Must-in等正标签先验信息,并对传统的COPRA算法进行改进,提出了基于正标签先验信息的COPRA_SI算法,使得社区发现的准确度得到了一定的提高。最后,本文充分利用网络中的少量正标签先验信息与Cannot-link、Cannot-in等负标签先验信息,提出了基于正负标签先验信息的COPRA_SNI算法,大大提高了社区发现的准确度。通过在真实网络和人工生成网络上的实验,并以扩展模块度EQ和标准化互斥信息ONMI来作为社区发现的准确度衡量标准,有效证明了本文所提算法的准确性。此外,实验也表明,适当增加网络中正负标签等先验信息,在重叠社区发现领域也可以提高社区发现的准确率。基于局部标签信息的半监督社区发现算法能有效提高社区发现的准确度,其为半监督学习在社区发现领域的研究打下了坚实的基础,而且为社区发现走向应用提供了理论支撑。
【学位单位】：电子科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP301.6;O157.5
【文章目录】：
摘要
abstract
第一章 绪论
    1.1 课题研究背景与意义
    1.2 国内外研究现状
    1.3 本文主要贡献及创新
    1.4 本论文的结构安排
第二章 社区发现相关研究
    2.1 复杂网络相关概念
        2.1.1 邻接矩阵
        2.1.2 边介数
        2.1.3 节点相似性
            2.1.3.1 基于邻居节点的相似度度量
            2.1.3.2 皮尔逊（Pearson）相似度
        2.1.4 先验信息
        2.1.5 标签隶属矩阵
        2.1.6 标签转移矩阵
        2.1.7 标签存在性矩阵
        2.1.8 节点隶属度矩阵
    2.2 非重叠社区发现算法
        2.2.1 GN算法
        2.2.2 FN算法
        2.2.3 谱聚类方法
        2.2.4 InfoMap算法
        2.2.5 BGLL算法
    2.3 重叠社区发现算法
        2.3.1 派系过滤算法CPM
        2.3.2 LMF算法
        2.3.3 SLPA算法
    2.4 本章小结
第三章 基于半监督的非重叠社区发现算法
    3.1 基于标签传播的无监督社区发现算法LPA
S'>    3.2 基于Pearson相似度的改进LPA算法LPAS

    3.3 基于正标签先验信息的半监督社区发现算法LPA_SI
SNI'>    3.4 基于正负标签先验信息的半监督社区发现算法LPA_SNI
    3.5 本章小结
第四章 基于半监督的重叠社区发现算法
    4.1 基于标签传播的无监督社区发现算法COPRA
S'>    4.2 基于Pearson相似度的改进COPRA算法COPRA_S

    4.3 基于正标签先验信息的半监督社区发现算法COPRA_SI
SNI'>    4.4 基于正负标签先验信息的半监督社区发现算法COPRA_SNI
    4.5 本章小结
第五章 实验与分析
    5.1 实验数据集
        5.1.1 人工基准网络数据集
        5.1.2 真实网络数据集
            5.1.2.1 ZacharyKarateClub数据集
            5.1.2.2 海豚网简介
            5.1.2.3 美国足球联盟网络
            5.1.2.4 美国政治书网络
            5.1.2.5 科学家合作网络
    5.2 实验评价标准
        5.2.1 模块度函数
        5.2.2 标准化互斥信息（NMI）
    5.3 实验结果
        5.3.1 非重叠社区发现结果
            5.3.1.1 真实网络
            5.3.1.2 GNbenchmark人工网络
            5.3.1.3 LFRbenchmark网络
            5.3.1.4 时间复杂度分析
        5.3.2 重叠社区发现结果
            5.3.2.1 真实网络
            5.3.2.2 LFRbenchmark网络
            5.3.2.3 时间复杂度分析
    5.4 本章小结
第六章 总结与展望
致谢
参考文献

【参考文献】

相关期刊论文 前7条

1 李金泽;徐喜荣;潘子琦;李晓杰;;改进的自适应谱聚类NJW算法[J];计算机科学;2017年S1期

2 汪晓锋;刘功申;李建华;;基于模糊聚类的多分辨率社区发现方法[J];电子与信息学报;2017年09期

3 肖永嘉;朱征宇;;基于LFM算法的改进社区发现算法[J];现代计算机(专业版);2017年14期

4 王李冬;张赟;;大规模社交网络重叠社区发现技术综述[J];杭州师范大学学报(自然科学版);2016年03期

5 张鑫;刘秉权;王晓龙;;复杂网络中社区发现方法的研究[J];计算机工程与应用;2015年24期

6 辛宇;杨静;谢志强;;基于随机游走的语义重叠社区发现算法[J];计算机研究与发展;2015年02期

7 刘大有;金弟;何东晓;黄晶;杨建宁;杨博;;复杂网络社区挖掘综述[J];计算机研究与发展;2013年10期

本文编号：2889251

suoshi