位置导航 —毕业论文范文传播组织传播

算法方面在职研究生毕业论文范文,与基于势函数的标签传播社区发现算法相关论文范文文献

本文关于算法及计算机应用及节点方面的免费优秀学术论文范文,算法方面论文范文文献,与基于势函数的标签传播社区发现算法相关在职研究生毕业论文范文,对不知道怎么写算法论文范文课题研究的大学硕士、本科毕业论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。

摘 要 :针对标签传播算法(LPA)存在大量随机性、算法稳定性差的问题,提出了基于数据场势函数的标签传播算法(LPAP).该算法计算所有节点的势值,搜索势值极值点.初始化时仅赋予势值极值点以标签,迭代过程中根据邻接节点中相同标签节点势值之和更新标签,所有节点标签不再改变时迭代结束.实验结果表明:该算法得到的社区划分方式平均是LPA的4.0%,是平衡传播算法(BPA)的12.9%;信息变化参数平均是LPA的45.1%,是BPA的73.3%.具有更好的稳定性,适用于大型网络的社区发现.

关 键 词 :社区发现;标签传播算法;数据场;势函数;稳定性

中图分类号: TP391.1; TP18

文献标志码:A

Abstract:

Because of randomness, the robustness of Label Propagation Algorithm (LPA) is severely hampered. To improve the robustness, a LPA based on potential function of data field (LPAP) was proposed. The potential of every node was calculated, and local extreme potential was searched. Only the node with extreme potential was labeled initially, and the label was updated according to the sum potential of its neighbors with equal label during iteration. When there were no nodes changing its label, iteration stopped. The experimental results show that the average distinct munity partition of LPAP is 4.0% of that of LPA, 12.9% of that of Balanced Propagation Algorithm (BPA), and the average Variation of Information (VOI) of LPAP is 45.1% of that of LPA, 73.3% of that of BPA. LPAP is significantly more robust, and is suitable for munity detection in large work.

Key words: munity detection; Label Propagation Algorithm (LPA); data field; potential function; robustness


该文转载于:http://www.eduxue.com/chuanbo/zzcb/382426.html

0引言

现实网络不仅具有小世界和无标度等特性,还呈现明显的社区结构.社区结构在现实网络中发挥着重要作用,可以用来揭示社会网络中具有相同兴趣、爱好以及社会背景的社会团体,可以用来发现生物系统中功能相关的组织单元,可以用来提高万维网的搜索效率和准确性.因此,各种社区发现算法不断地被提了出来.典型的算法包括递归去除连接边的分裂算法[1]、重复地合并小部分的聚合算法[2-3]以及极值优化的模块度算法[4-7]等.

由于算法时间复杂度原因,只有少数算法适合大型现实网络.Raghavan等[8]提出了标签传播算法(Label Propagation Algorithm, LPA).初始时每个节点被赋予唯一的数字标签,迭代过程中选择邻接节点标签出现频率最高的标签来更新当前节点的标签.经过几次迭代,密集连接的节点拥有相同的标签,形成一个社区.近年来,标签传播算法又被不断地改进提高.Barber等[9]为了避免LPA中所有节点划分到同一社区,提出了一种模块化标签传播算法;Liu等[10]将模块化标签传播算法与多步贪婪凝聚算法融合,能够避免陷入局部极大值,更加准确识别社区;Leung等[11]采用启发式方法提高算法性能,通过简单参数调整使算法适应于不同规模网络.

基于势函数的标签传播社区发现算法参考属性评定
有关论文范文主题研究: 关于算法的论文范文集 大学生适用: 电大毕业论文、学年论文
相关参考文献下载数量: 44 写作解决问题: 怎么写
毕业论文开题报告: 标准论文格式、论文摘要 职称论文适用: 刊物发表、高级职称
所属大学生专业类别: 怎么写 论文题目推荐度: 免费选题

尽管取得了一定的改进,LPA的一个重要问题还没有很好的解决.由于更新顺序是随机的、邻接节点标签频率相同时标签选择也是随机的,算法的鲁棒性受到严重损坏,社区结构的稳定性也就受到严重损伤.为了得到稳定的社区结构,Kato等[12]通过整合多种网络结构信息,降低不相干网络结构的重要性,来提高标签传播算法的稳定性.ubelj等[13]提出了一种平衡传播算法,利用节点的平衡因子来抵消LPA的随机性.上述算法中,权重因子与节点内在属性无关,无助于发现合理的网络社区.为了减少随机性,本文引入数据场势函数,以节点的势值这一内在属性作为权重因子,并根据势值之和更新标签.

2基于势函数的LPA

既然随机性严重破坏了算法的稳定性,就应该尽可能避免或减少随机性.如果按照预先定义好的顺序更新,算法稳定性明显得到提高.尽管没有哪一种顺序对所有网络都有效,不过对于某一网络确实存在一些可以得到正确而稳定的更新顺序[13].如果一个节点充当其社区的抽象中心,那么在该社区中只赋予该节点以初始标签即可,而其他节点在初始化阶段并不赋予标签.这种情况下,其他节点趋于从其靠近的抽象中心获取标签,最终加入该社区.

2.1势函数

数据场的基本思想来源于物理场的概念,用于描述空间数据之间的相互作用.空间数据通过向外辐射数据能量形成虚拟的数据场,数据场中某点的势定义为作用于该点所有能量之和.物理场通常分为长程场和短程场.重力场和静电场是长程场,势值与作用距离成反比.核子的中心势场是短程场,势值随着距离的增加而急剧下降.引入长程场描述网络节点之间的相互作用,算法的收敛性很差.因此,本文引入代表短程场的高斯势函数来计算数据场的幅值强度. LPAP得到的平均社区数显著少于LPA和BPA的,同时也避免了划分过小社区或过大社区.尽管DBLP子集存在着确定的社区结构,但却没有明确的社区划分方式.每次实验,节点划归的社区可能都不同,以100次实验里节点最可能的划归方式作为已知的社区划分,计算VOI.LPAP得到的VOI远小于LPA的,略小于BPA的,说明LPAP比LPA稳定得多,比BPA也稳定.比较两种算法的模块度Q,LPAP得到的Q值略高于LPA和BPA的,社区划分质量有一定的提高.另外,LPAP标签更新的迭代次数只有LPA的一半多.但由于势值估算也花费了相当的时间,LPAP只是略快于LPA.

4结语

由于LPA中存在大量的随机性,严重破坏了算法的鲁棒性,进而破坏了所识别的社区结构的稳定性.为了减少随机性的影响,提出了基于势函数的标签传播算法.该算法将势值极值点作为社区的抽象中心,并赋予初始标签,其他节点根据邻接节点中同一标签的势值之和更新标签.迭代过程中,虽然节点的选取是随机的,但标签的更新大致是有序的.节点标签的更新是依据势值之和,而非简单数量,较少出现相等的情况,也就降低了随机性.将LPAP应用到基准网络,社区划分方式稳定、集中,收敛快.应用到DBLP大型网络,社区划分的种类显著减少,Q值也有一定程度提升.可见,LPAP既保持了LPA简单快速适合大型网络的优点,又明显提升了算法的稳定性.

参考文献:

[1]CHEN D, XU X. A munity discovery method based on breadthfirst search [J]. Journal of Northeastern University: Natural Science, 2010, 31(3): 346-349.(陈东明,徐晓伟.一种基于广度优先搜索的社区发现算法[J].东北大学学报:自然科学版,2010,31(3):346-349.)

[2]CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in works [J]. Nature, 2008, 453(7191): 98-101.

[3]WANG G, ZHONG G. Study on algorithm of munity detection based on information entropy [J]. Computer Science, 2011, 38(2): 238-240.(王刚,钟国祥.基于信息熵的社区发现算法研究[J].计算机科学,2011,38(2):238-240.)


算法学术论文撰写
播放:32159次 评论:7450人

[4]SHUI C, LI H. Community structure identification algorithm based on subcenter [J]. Journal of Computer Applications, 2012, 32(8): 2154-2158.(水超,李慧.基于次中心的社区结构探寻算法[J].计算机应用,2012,32(8):2154-2158.)

[5]LUO J, YUAN C, YANG W, et al. Community structure division in plex works based on gene expression programming algorithm [J]. Journal of Computer Applications, 2012, 32(2): 317-321.(罗锦坤,元昌安,杨文,等.基于基因表达式编程算法的复杂网络社区结构划分[J].计算机应用,2012,32(2):317-321.)

[6]HU H, GENNIP Y, HUNTER B, et al. Multislice modularity optimization in munity detection and image segmentation [C

关于基于势函数的标签传播社区发现算法的在职研究生毕业论文范文
算法方面论文范文文献
]// Proceedings of the 12th IEEE International Conference on Data Mining Workshops. Washington, DC: IEEE Computer Society, 2012: 934-936.

[7]CHANG H H, FENG Z R, REN Z G. Community detection using ant colony optimization [C]// Proceedings of the 2013 IEEE Congress on Evolutionary Computation. Washington, DC: IEEE Computer Society, 2013: 3072-3078.

[8]RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect munity structures in largescale works [J]. Physical Review E, 2007, 76(3): 036106.

[9]BARBER M J, CLARK J W. Detecting work munities by propagating labels under constraints [J]. Physical Review E, 2009, 80(2): 026129.

[10]LIU X, MURATA T. Advanced modularityspecialized label propagation algorithm for detecting munities in works [J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(7): 1493-1500.

[11]LEUNG I X Y, HUI P, LI P, et al. Towards realtime munity detection in large works [J]. Physical Review E, 2009, 79(6): 066107.

[12]KATO T, KASHIMA H, SUGIYAMA M. Robust label propagation on multiple works [J]. IEEE Transactions on Neural Networks, 2009, 20(1): 35-44.

[13]UBELJ L, BAJEC M. Robust work munity detection using balanced propagation [J]. European Physical Journal B, 2011, 81(3): 353-362.

相关参考资料:

计算机编程算法
计算机图形学及算法实现%,三维图形基本理论与算法40%,(四)题型比例,填空题20%,问答题30%,计算与证明题30%,编程20%,第二部分考查要点,计算机图形。计算机编程课程广。

计算机编程函数
:计算机网络技术授课单位:武汉软件工程职业学院,学时:134学。初中数学函数的教学均增长率;[来源:学科网zxxk],(2)如果2016年仍保持相同的年平均增长率,请你预测2016。

计算机算法论文
置的.其中,计算。基于模板算法的动五"科技支撑计划课题,"863计划"(子课题)项目,国家自然科学基金项其它省部级及以上项目78项,横向开发项目40项.总研究经费达万元,其中纵向研。

初中数学函数小论文
初中数学函数的教学2016年广东省初中毕业生学业考试数学试题,全卷共4页,考试用时100分钟,满分为120分.,一,选择题(本大题5小题,每小题3分,共15分),1.—5的相反。

传播心理学
传播心理学:meilingj@mail.tku.edu.tw,【上课时间:周四3,4堂(10:10-12:00);上课地点:sg-318】,【课程主旨】,探索与解析资讯传播相。

发现
车,医疗,快消,消防,电。毕业论文以启发我们探索新问题,发现新规律,及早做出相应的决策.,3,调查报告——是对某一问题,某一情况,某一事件,某一经验进行深入细致的调查,并把调。

计算机算法分析论文
置的.其中,计算。基于模板算法的动五"科技支撑计划课题,"863计划"(子课题)项目,国家自然科学基金项其它省部级及以上项目78项,横向开发项目40项.总研究经费达万元,其中纵向研。

论文检测算法
部《学位论文作。基于模板算法的动五"科技支撑计划课题,"863计划"(子课题)项目,国家自然科学基金项其它省部级及以上项目78项,横向开发项目40项.总研究经费达万元,其中纵向研。

新闻传播论文发表
研项目1.017赵勋新闻传播学院社会转型背景下城市社区冲突与社区传播研究2016年度国家社科基金项目国家级或省部级重要科研项目1.018何爱平经济管理学院我国生。传播学论文发表新。

初中数学二次函数论文
二次函数在高中数学的作用公告标题:2016年广州市普通高中数学教师职务培训(第一期),公告,公告内容.,作业:针对新课程下数学教育教学的某一问题或某一环节进行研究,写出体会,报。

word版本基于势函数的标签传播社区发现算法全文下载

热门阅读