非重叠社区发现中近邻传播算法的研究与应用

发布时间：2017-12-25 22:34

  本文关键词：非重叠社区发现中近邻传播算法的研究与应用　出处：《中国矿业大学》2016年硕士论文　论文类型：学位论文

  更多相关文章： 社区发现 近邻传播 快速 半监督 增量

【摘要】：复杂社会网络可以抽象为由大量节点和节点之间的联系组成的拓扑结构,其在众多领域中广泛存在。聚类分析作为研究复杂社会网络的重要手段之一,目的在于发现其内部的社区结构,体现其内在属性,更好地对现实生活进行指导。本文主要针对近邻传播算法的执行速率较慢、无监督的缺点,给出其改进算法,并将近邻传播算法运用在增量社区发现中。首先,给出基于近邻传播的快速半监督社区发现算法(FSAP算法)。算法在研究近邻传播算法(AP算法)的基础上,根据因子图模型中信息在节点间的传递规则,通过将相似度值为0的节点对直接划分到不同的簇中而提高时间效率,成为快速近邻传播算法(FAP算法)。同时,结合部分Must-link和Cannot-link的成对约束信息,对相似度矩阵进行调整,在新的相似度矩阵上运行FAP算法。相比原始AP算法和其他算法,FSAP算法不仅具有良好的时间效率,而且可以有效利用先验知识去指导聚类过程,进而提高社区发现的准确率。其次,给出基于近邻传播的增量社区发现算法(IAP算法)。算法在FAP算法的基础上,根据网络动态变化的特点,将增量分为增加边、删除边、增加节点、删除节点四种类型,且给出对应的处理方法。由于算法对网络变化进行局部更新,一段时间之后可能造成算法结果相比于真实的社区结构存在失真,给出最小模块度进行检测。在动态社区发现中,相比静态AP算法对全局网络结构的更新,IAP算法不仅能够有效地降低时间复杂度,且能够保证聚类精度。最后,设计并实现了非重叠社区发现算法的原型系统。该系统可以实现数据录入、算法选择、结果显示、系统设置等功能,能够直观地体现社区发现的结果,在社区发现的研究中发挥了良好的作用。
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 李德胜;张才仙;陈淑铭;;选择策略对进化算法性能的影响[J];科技资讯;2007年11期

2 梁民,孙仲康;多层前馈神经网络的快速学习算法及其仿真研究[J];系统工程与电子技术;1993年09期

3 王忠;陈伏虎;;基于阵元域数据的联合检测与跟踪算法[J];声学学报(中文版);2007年06期

4 苏开乐;关于D.W.Etherington的扩充产生算法的一个注记[J];计算机工程与科学;1998年04期

5 江宇闻;;Overcomplete ICA算法研究[J];中山大学研究生学刊(自然科学、医学版);2004年02期

6 王杰;王加银;;Mean Shift算法的收敛性讨论[J];北京师范大学学报(自然科学版);2008年05期

7 胡梦佑;陈钧量;;快速加权滑窗RLS格型算法[J];中山大学学报(自然科学版);1992年02期

8 裴炳南;吴显鼎;张明武;;MLMS算法的伪收敛现象[J];河南科学;1993年Z1期

9 张承慧;一种工业过程时变参数估计新算法——修正目标函数法[J];中国工程科学;2001年11期

10 丁海军;李峰磊;;蜂群算法在TSP问题上的应用及参数改进[J];中国科技信息;2008年03期

相关会议论文 前10条

1 何敏;陈中显;梅松涛;;蚁群算法的研究与进展[A];中国计量协会冶金分会2010年会论文集[C];2010年

2 高玮;;免疫连续蚁群算法[A];第二十六届中国控制会议论文集[C];2007年

3 唐乾玉;韩曾晋;;基于扰动分析的优化算法[A];1994中国控制与决策学术年会论文集[C];1994年

4 金成勋;周广禄;郭恒业;;对ICP算法中稳定采样的研究[A];立体图象技术及其应用研讨会论文集[C];2005年

5 陈元琰;闫友彪;罗晓曙;;REM算法的改进[A];广西计算机学会2005年学术年会论文集[C];2005年

6 范瑛;;改进蚁群算法结合BP网络用于入侵检测[A];中国运筹学会模糊信息与模糊工程分会第五届学术年会论文集[C];2010年

7 万丽芬;钟炎平;;约束LMS算法研究[A];第二十届电工理论学术年会论文集[C];2008年

8 云飞;薛青;姚义军;;改进型LMBP算法在军事数据分析中的应用研究[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

9 朱双东;艾智斌;阎夏;;BP网络学习算法的改进方案探析[A];1998年中国智能自动化学术会议论文集（上册）[C];1998年

10 唐乾玉;陈翰馥;韩曾晋;;串行生产线的参数优化[A];1994年中国控制会议论文集[C];1994年

相关博士学位论文 前10条

1 杨扩军;TIADC系统校准算法研究与实现[D];电子科技大学;2015年

2 黄亚魁;几类优化问题的BB型算法研究[D];西安电子科技大学;2015年

3 王戈;通信信号若干联合处理技术研究[D];解放军信息工程大学;2013年

4 易雯帆;非线性偏微分方程多解计算大范围收敛算法及其应用研究[D];湖南师范大学;2016年

5 蔡永智;分布式电力系统状态估计研究[D];华南理工大学;2016年

6 苏雪平;基于交叉多模信息的新闻图像人物标识算法[D];西北工业大学;2015年

7 王可心;大规模过程系统非线性优化的简约空间理论与算法研究[D];浙江大学;2008年

8 鲍吉锋;平衡问题和优化问题若干算法的收敛性分析[D];浙江大学;2013年

9 韩飞;基于先验信息编码的约束学习算法研究[D];中国科学技术大学;2006年

10 袁东辉;蚁群算法在飞行模拟器平台中若干应用问题的研究[D];吉林大学;2011年

相关硕士学位论文 前10条

1 杨展;城轨列车自动调整系统模型与算法研究[D];西南交通大学;2015年

2 马英钧;基于人工蜂群算法的约束优化问题研究[D];华中师范大学;2015年

3 钱其;电网谐波和间谐波功率的计量算法研究[D];中国科学技术大学;2015年

4 蒋玉冰;无线通信信号到达角跟踪算法研究[D];电子科技大学;2014年

5 孙方亮;基于粒子群与中心引力的一种新混合算法及应用[D];西安电子科技大学;2014年

6 于诗杰;基于无波前探测的大气光通信自适应补偿方法研究[D];西安电子科技大学;2014年

7 柯家龙;压缩感知算法及其在成像中的应用[D];南京邮电大学;2015年

8 刘光泓;并行磁共振图像全变分恢复一阶算法研究[D];南京邮电大学;2015年

9 张德祥;基于改进蚁群算法的机器人三维路径规划研究[D];青岛科技大学;2015年

10 张申利;基于蜂群算法的GIS优化选址及其并行化研究与应用[D];中国石油大学(华东);2014年

，

本文编号：1334748