学位论文 > 优秀研究生学位论文题录展示

基于半监督学习的社团划分算法研究

作　者: 孔健
导　师: 谢福鼎
学　校: 辽宁师范大学
专　业: 计算机应用技术
关键词: 复杂网络 社团结构 半监督学习 信息传递 引力模型
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 75次
引　用: 0次
阅　读: 论文下载
 

内容摘要


自然界中存在的大量复杂系统都可以通过各种各样的网络进行描述。近年来,复杂网络的研究受到了越来越多的关注,并渗透到从自然科学到工程科学甚至社会科学的多个领域。研究所涉及的网络主要有:生命科学领域的各种网络、Internet/WWW网络、交通网络、社会网络、科学家合作网络和语言学网络等等。随着对网络性质的深入研究,人们发现许多网络具有一个共同的性质—社团结构。诸多学者从不同角度对如何发现网络中的社团结构问题进行了研究。而当复杂网络中存在已知标记节点时,如何更好的利用已知标记和未知标记节点训练出优秀的分类器进行社团划分成为了重点问题。而半监督学习方法恰恰是针对大量无标记节点集与有标记节点集共同进行训练,以得到高性能以及较好泛化能力的学习器。因此,半监督学习的方法能够更好的解决存在已知标记节点的复杂网络社团划分问题。本文从半监督学习角度出发提出了两种算法,旨在解决当网络中存在有标记节点时的社团划分问题。基于信息传递模型的划分算法:信息从已知标记节点开始通过节点间的边在网络中进行传播,直到每一个未知标记节点接收到所有已知标记节点的信息为止。然后算法分析每一个无标记网络所接收的每一类已知标记节点的信息量,最终根据分析结果对每一个未知标记节点进行标记。信息在传递过程中,为了更好的模拟现实中信号衰减现象,算法利用信号衰减公式来控制衰减程度。此算法为线性时间复杂度,因此运行速度较快。实验结果表明,在对一些网络进行社团划分时,此算法与GN、Wu-Huberman、Newman等算法有着相同的准确率,在个别网络中,其准确率要更高一些。基于引力模型的划分算法:该算法把节点看作引力实体,然后将物理学中的万有引力定律引入社团划分算法中。首先计算已知标记节点与未知标记节点之间的引力作用值的大小,然后分析并比较每个已知标记节点对未知标记节点引力作用值的大小,最后根据一定的规则将未知标记节点进行标记。在实验中,利用此算法对一些实际网络进行分析,结果表明虽然运行速度比信息传递模型算法有所下降,但精度有所提高。而与传统算法相比,虽然其时间复杂度相对较高,但是精度相对较高。本文所提出的两个算法均为半监督学习算法,通过已知标记与未知标记节点共同训练出学习器。运用统计学理论可以证明当无标记节点数量越多时,可以对模型参数估计越准确,进而提高学习器准确性。算法在局部与整体体现了比较好的一致性,避免了局部最优化对划分精度的不良影响。通过对实验结果的分析可知,算法在时间和空间复杂度方面均比较低,而在准确性方面相对较高。

全文目录


摘要  3-4
Abstract  4-7
1 绪论  7-18
  1.1 问题的背景  7
  1.2 半监督学习  7-12
    1.2.1 起源  7-8
    1.2.2 半监督学习中未知标记数据的价值  8
    1.2.3 半监督学习算法的种类  8-12
  1.3 复杂网络及其社团结构划分  12-16
    1.3.1 复杂网络的起源与发展  12-13
    1.3.2 社团结构划分  13-16
  1.4 本文研究的主要内容  16-17
  1.5 文章组织结构  17-18
2 社团划分经典算法  18-23
  2.1 社团结构划分算法  18-23
    2.1.1 Kernighan-Lin 算法  18
    2.1.2 谱评分法  18-19
    2.1.3 Wu-Huberman 算法  19-20
    2.1.4 GN 算法  20-21
    2.1.5 Newmen 快速算法  21
    2.1.6 K 均值算法  21-23
3 信息传递算法  23-31
  3.1 基本思想  23-24
  3.2 算法描述  24-25
  3.3 实验及分析  25-31
    3.3.1 Zachary 空手道俱乐部关系网络  25-28
    3.3.2 大学足球网络  28-29
    3.3.3 科学家合作网  29-31
4 引力模型算法  31-39
  4.1 基本思想  31-32
  4.2 算法描述  32-33
  4.3 实验与分析  33-39
    4.3.1 三社团网络  34-35
    4.3.2 Zachary 网络  35-37
    4.3.3 大学足球网络  37-39
结论  39-40
攻读硕士学位期间发表学术论文情况  40-41
参考文献  41-46
致谢  46

相似论文

  1. 社会消费方式变迁下的服装终端空间变化之研究,TS941.1
  2. 复杂网络的建模分析及其应用,O157.5
  3. 基于复杂网络特征的SNS社交网站传播特征研究,G206
  4. 绿色贸易壁垒对安徽省茶叶出口的影响研究,F426.82
  5. 不利公告的信息传递效应研究,F832.51;F224
  6. 电网分析计算中的可视化技术研究,TM769
  7. 领域知识指导的半监督学习和主动学习倾向性分类研究,TP181
  8. 基于复杂网络的供应链建模与网络效率研究,O157.5
  9. 服务贸易壁垒的度量及其对中国服务出口的影响研究,F752.62;F224
  10. 复杂网络可靠性评价指标研究,O157.5
  11. 代谢网络社团结构研究,Q251
  12. 城市大型活动应急交通疏散对策研究,U12
  13. 基于半监督哈希算法的图像检索方法研究,TP391.41
  14. 基于软件影响网络的软件度量研究,TP311.52
  15. 遇袭有向复杂网络抗毁性修复策略研究,O157.5
  16. 基于引力模型的中国企业海外并购流向分析,F224
  17. 中国服务贸易潜力及壁垒,F224
  18. 中国与东盟双边出口贸易流量与潜力,F224
  19. 基于半监督学习的时间序列分类研究与实现,TP181
  20. 乌鲁木齐市公交网络结构特性分析研究,U491.17
  21. 基于车辆出行特征的交通网络评价方法研究,U491.13

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com