基于增量的不确定社团发现算法研究

发布时间：2017-08-15 14:38

  本文关键词：基于增量的不确定社团发现算法研究

  更多相关文章： 社会网络 社团发现 不确定图 势能模型

【摘要】：近年来,在全球信息化大潮的推动下,社会网络得到快速发展,各种不同的社会网络都表现出一种强的社团效应。一个网路中的成员趋于形成密切联系的社团。在不同的应用下,这些社团也被称为模块,簇等。总体上,社团内部联系紧密,社团外部联系稀疏。如何快速、准确的发现网络中的社团(即社团发现)仍然是一个关键问题。从是否考虑数据的不确定性,社团发现可分为确定社团发现和不确定社团发现。很多传统确定社团发现算法都依据全局信息进行社团发现,算法效率不高,并且没有考虑到数据的不确定性。然而在现实应用中,网络中的数据往往存在其内生的不确定性,网络中数据存在残缺现象、数据以一定概率存在等,这里称为不确定网络。从不确定网络中进行社团发现的算法称为不确定社团发现算法。本文充分考虑了确定网络和不确定网络,结合社团局部特征和数据本身特点,对社团发现算法进行了深入研究。本文主要工作及创新点如下:(1)对LFM(Largest Fitness Measure)算法进行改进。深入分析了局部社团发现算法LFM算法以及势能模型,在此基础上提出了LFM算法的改进算法—WLFM算法。该算法利用势能的思想对LFM算法中随机选取初始节点、划分准确性较低、算法结束条件难以达到等问题进行改进,最后通过两组实验验证了该算法具有良好的准确性和较高的效率。(2)对EM(Expectation Maximization)算法进行改进。首先对高斯混合模型的EM算法进行详细介绍,接着对此算法进行优化。利用势能的方法对高斯混合模型的EM算法进行初始化,得到优化的初始值。通过两组实验证明新的算法具有较低的错误率。(3)提出不确定相对K紧密子图发现算法。研究发现,寻找前K个最紧密子图具有较高的复杂性。本文研究了从不确定图中发现存在概率较高的前K个紧密子图问题,提出了不确定相对K紧密子图发现算法。在算法中,由不确定图的连通指数确定阈值,接着根据阈值计算子图的存在概率,最终得到存在概率较高的前K个紧密子图。最后,通过若干组实验,验证了此算法可以高效、准确的发现不确定图中的紧密子图。
【关键词】：社会网络 社团发现 不确定图 势能模型
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP301.6
【目录】：

• 摘要5-6
• ABSTRACT6-7
• 第一章 绪论7-12
• 1.1 研究背景及意义7
• 1.2 国内外研究现状7-10
• 1.2.1 传统社团发现研究现状8-9
• 1.2.2 不确定社团发现研究现状9-10
• 1.3 本文的研究工作及文章结构安排10-12
• 1.3.1 主要研究工作10-11
• 1.3.2 结构安排11-12
• 第二章 社团发现基本理论及方法12-18
• 2.1 社团的定义12-13
• 2.2 社团发现的基本方法13-15
• 2.2.1 网络的划分13-14
• 2.2.2 层次聚类14-15
• 2.2.3 划分聚类15
• 2.3 社团划分评价标准15-17
• 2.3.1 模块度15-16
• 2.3.2 社团密度和社团有效直径16-17
• 2.4 本章小结17-18
• 第三章 改进的传统社团发现算法18-24
• 3.1 改进的LFM算法18-21
• 3.1.1 LFM算法的基本原理18-19
• 3.1.2 势能场的基本原理19-20
• 3.1.3 改进的LFM算法—WLFM算法20-21
• 3.2 实验结果及分析21-23
• 3.3 本章小结23-24
• 第四章 改进的不确定社团发现算法24-36
• 4.1 算法初始化的改进24-29
• 4.1.1 相关定义24-26
• 4.1.2 改进的算法初始化方法26-28
• 4.1.3 实验结果及分析28-29
• 4.2 不确定相对紧密子图发现算法29-35
• 4.2.1 不确定概率模型29-31
• 4.2.2 问题定义31
• 4.2.3 不确定阈值UT31-32
• 4.2.4 RTop-k相对紧密子图发现算法32-33
• 4.2.5 实验结果及分析33-35
• 4.3 本章小结35-36
• 第五章 总结与展望36-38
• 5.1 论文工作总结36
• 5.2 未来工作展望36-38
• 参考文献38-41
• 攻读硕士学位期间取得的科研成果41-42
• 致谢42

【相似文献】

中国期刊全文数据库 前10条

1 邹汪平;;一种基于网络安全控制的蜂群算法应用研究[J];吉林师范大学学报(自然科学版);2013年04期

2 郭毅可;韩锐;;云计算中的弹性算法:概要和展望[J];上海大学学报(自然科学版);2013年01期

3 刘江华;戴新喜;白似雪;;基于模式矩阵的P_Matrix算法[J];南昌大学学报(理科版);2007年05期

4 胡俊鹏;;基于双向选择的蚁群相遇算法的优化[J];湖北民族学院学报(自然科学版);2013年01期

5 张丽;;关联规则挖掘算法的研究[J];赤峰学院学报(自然科学版);2013年02期

6 吴秋峰;尹海东;孟翔燕;;基于和积和最大积的信念传播算法的收敛性分析[J];数学的实践与认识;2011年09期

7 赵吉东;;蚁群算法的改进策略研究[J];中国科技信息;2012年12期

8 胡森森;周贤善;;一种改进蚁群算法的研究[J];长江大学学报(自科版);2006年10期

9 王恒娜;赵晓静;;基于属性覆盖的关联规则挖掘算法[J];安庆师范学院学报(自然科学版);2007年03期

10 曹建军;刁兴春;李凯齐;邵衍振;;基于进化强度的蚁群算法过程性能评价[J];解放军理工大学学报(自然科学版);2013年01期

中国重要会议论文全文数据库 前10条

1 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会——2004年学术年会论文集[C];2004年

2 黄纪武;毛泽华;李松涛;张锦雄;;SPMD并行查找算法的MPI实现[A];广西计算机学会2004年学术年会论文集[C];2004年

3 符丽锦;覃华;邓海;孙欣;;一种改进的Apriori算法的研究[A];广西计算机学会2012年学术年会论文集[C];2012年

4 王东锋;王军民;陈英武;;模糊定性仿真理论研究与算法实现[A];'2000系统仿真技术及其应用学术交流会论文集[C];2000年

5 赵唯;;晶粒度评级的改进算法[A];中国图象图形科学技术新进展——第九届全国图象图形科技大会论文集[C];1998年

6 刘启文;;可扩展的图形学算法演示系统的研究[A];’2004计算机应用技术交流会议论文集[C];2004年

7 佘智;蒋泰;朱延生;;基于Type C协议的防冲突改进算法[A];广西计算机学会25周年纪念会暨2011年学术年会论文集[C];2011年

8 朱绍文;赵培;朱秋云;;基于pSPADE并行挖掘序列算法的研究[A];2003年中国智能自动化会议论文集（下册）[C];2003年

9 杨霞;;新的基于启发式蚁群算法的QoS路由算法[A];广西计算机学会2009年年会论文集[C];2009年

10 陈黎飞;姜青山;董槐林;;基于图形轮廓的快速聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

中国博士学位论文全文数据库 前10条

1 钟永腾;基于近场MUSIC算法的复合材料结构健康监测研究[D];南京航空航天大学;2014年

2 刘燕;入侵杂草优化算法在阵列天线综合中的应用[D];西安电子科技大学;2015年

3 苗义烽;突发事件下的列车运行调度模型与算法研究[D];中国铁道科学研究院;2015年

4 杨玉婷;头脑风暴优化算法与基于视频的非接触式运动定量分析方法研究[D];浙江大学;2015年

5 刘杰;全局优化问题的几类新算法[D];西安电子科技大学;2015年

6 柏静;基于多种混合策略的人工蜂群算法改进研究[D];山东师范大学;2016年

7 孔翔宇;几类优化问题的人工蜂群算法[D];西安电子科技大学;2016年

8 单美静;求解非线性实代数系统的混合算法研究[D];华东师范大学;2008年

9 邱剑锋;人工蜂群算法的改进方法与收敛性理论的研究[D];安徽大学;2014年

10 潘磊;若干社区发现算法研究[D];南京大学;2014年

中国硕士学位论文全文数据库 前10条

1 安世勇;命题逻辑中随机3-SAT问题算法研究[D];西南交通大学;2015年

2 毕晓庆;油气探矿权竞争性出让系统设计与实现[D];中国地质大学(北京);2015年

3 王明明;铁路大机与线路固定设施间距检测算法研究[D];西南交通大学;2015年

4 李静;基于视频图像序列的运动目标检测与跟踪算法研究[D];宁夏大学;2015年

5 刘贝玲;基于天地图的租房平台开发及其关键技术研究[D];西南交通大学;2015年

6 曹海锋;IDS中串匹配臭算法并行优化研究[D];西安建筑科技大学;2015年

7 周攀;基于蚁群算法的山区高速铁路隧道火灾应急疏散最优路径研究[D];西南交通大学;2015年

8 张路奇;基于改进蚁群算法的WSN路由协议的研究[D];中国地质大学(北京);2015年

9 王晓晨;入侵杂草优化算法的应用与改进[D];长安大学;2015年

10 信琴琴;手势控制和识别算法研究[D];闽南师范大学;2015年

，

本文编号：678730