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

半监督的社区发现方法研究

作　者: 康旭彬
导　师: 贾彩燕
学　校: 北京交通大学
专　业: 计算机科学与技术
关键词: 复杂网络 社区发现 半监督
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 81次
引　用: 0次
阅　读: 论文下载
 

内容摘要


自然界中存在的很多系统可以用网络的形式表示,如人际关系网、蛋白质作用网络、交通网络等。这些网络具有很高的复杂性,因此被称为“复杂网络”。社区结构是复杂网络研究的几个重要分支之一,越来越受到人们的重视。现有的社区发现方法常存在算法复杂度高、需要事先指定社区的数目、需要预先制定评价指标等缺陷,有的甚至需要给出大致的社区大小,限制了算法的实际应用效率。LPA(Label Propagation Algorithm)是一种重要的社区发现算法,它具有思想简单、复杂度低、不需要指定社区数目等优点,但算法精确度比较低。针对LPA算法,本文设计了一种改进的基于节点局部相似性的半监督算法,本文的主要创新点有：一,LPA算法在节点的label传播过程中,由于平等的对待了节点的每一个邻居节点,当邻居节点中出现多个label数目相同时,LPA会随机的选择一个label作为候选label,此方法容易造成不同社区之间的label相互传播,从而造成社区划分的准确率比较低。本文通过计算相邻节点间的相似度,为网络的每条边加入权值,使得不同社区之间的label传播被阻断,提高了算法的精确率。二,现有的社区发现算法都属于无监督学习的范畴,无法处理事先给定的半监督知识。本文中,将LPA算法加入了对半监督知识的处理过程,通过增加must-link节点对之间的边,删除cannot-link节点对最短路径中权值较小的边,使得网络的社区结构趋于明显,从而提高了算法的精确度。三,将以上两种方法相结合,通过在不同规模的人工网络和多种真实网络中进行试验并与多种方法相比较,验证了该算法的有效性。

全文目录


致谢  5-6
中文摘要  6-7
ABSTRACT  7-10
1 引言  10-14
  1.1 研究背景  10-12
    1.1.1 复杂网络  10-11
    1.1.2 半监督学习  11
    1.1.3 社区发现  11-12
  1.2 研究意义  12-13
  1.3 本文的主要研究内容  13
  1.4 本文的组织结构  13-14
2 社区发现方法  14-26
  2.1 谱方法  14
  2.2 基于局部搜索的社区发现方法  14-17
    2.2.1 Kernighan-Liu算法  14-15
    2.2.2 快速Newman算法  15-16
    2.2.3 Guinera-Amaral算法  16-17
  2.3 启发式社区发现方法  17-22
    2.3.1 Maximum Flow Community算法  17-18
    2.3.2 Hyperlink Induced Topic Search算法  18
    2.3.3 Girvan-Newman算法  18-20
    2.3.4 Wu-Huberman算法  20-21
    2.3.5 Clique Percolation Method算法  21-22
  2.4 其他社区发现方法  22-24
    2.4.1 Label Propagation Algorithm算法  22-23
    2.4.2 LPA算法的一种改进LPAm  23-24
  2.5 社区发现方法研究现状分析  24-25
  2.6 本章小结  25-26
3 半监督学习  26-34
  3.1 半监督学习的历史  26
  3.2 半监督学习的基本假设  26-27
  3.3 半监督学习方法  27-31
    3.3.1 生成式模型  27-28
    3.3.2 协同训练  28-29
    3.3.3 基于图的半监督学习  29-31
  3.4 半监督学习在聚类中的应用  31-32
  3.5 一些半监督聚类算法  32-33
    3.5.1 COP-KMENAS算法  32
    3.5.2 CCL算法  32-33
    3.5.3 PC-KMENAS算法  33
  3.6 本章小结  33-34
4 一种新的半监督社区发现方法  34-41
  4.1 LPAS算法  34-36
  4.2 SLPAS算法  36-39
  4.3 本章小结  39-41
5 实验及结果分析  41-49
  5.1 实验数据  41-42
    5.1.1 人工网络  41
    5.1.2 真实网络  41-42
  5.2 实验结果及分析  42-48
    5.2.1 人工网络  42-45
    5.2.2 真实网络  45-48
  5.3 本章小结  48-49
6 总结与展望  49-50
  6.1 工作总结  49
  6.2 工作展望  49-50
参考文献  50-52
作者简历  52-54
学位论文数据集  54

相似论文

  1. 复杂网络的建模分析及其应用,O157.5
  2. 人工免疫分类和异常识别算法的改进,R392.1
  3. 应用层协议识别和还原方法的研究与实现,TP393.08
  4. 混合重叠社区发现研究及应用,D669.3
  5. 基于半监督模糊聚类的入侵防御技术研究,TP393.08
  6. 李群深层结构学习算法研究,TP181
  7. 大规模软件中社区结构的发现与研究,TP311.52
  8. 基于FCA的社区发现算法,TP301.6
  9. 复杂网络社团结构探测研究,O157.5
  10. 网络稳定性研究,O157.5
  11. 粗糙集与蚁群算法在网络社区结构发现中的应用研究,TP393.02
  12. 博客潜在朋友推荐技术的研究,TP391.3
  13. 领域知识指导的半监督学习和主动学习倾向性分类研究,TP181
  14. 复杂网络中的社团发现算法研究,TP301.6
  15. 社会网络的节点重要性评估与社区发现研究,O157.5
  16. 半监督学习方法研究,TP181
  17. 基于复杂网络数据挖掘的个性化电子商务推荐系统研究,TP311.13
  18. 复杂网络上迁移驱使的聚集体演化动力学,O157.5
  19. 结构相似度及其在推荐系统中的应用研究,TP391.3
  20. 随机环境下风险模型破产概率及复杂网络中的随机过程,F840
  21. 天津市公共交通网络复杂性研究,U491.17

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化基础理论 > 人工智能理论
© 2012 www.xueweilunwen.com