基于种子扩展的社区发现算法及其并行化

论文摘要

社区发现是数据挖掘领域针对复杂网络的一个热门研究话题。随着网络的不断复杂化,传统的社区发现算法早已无法满足人们对网络更深层次的要求,因此,基于种子扩展的社区发现算法成为近年来社区发现算法研究的一个热点,它在种子选择和社区扩展等方面发挥着很大的优势。如何选择最合适、最准确的种子,如何制定社区扩展的策略,最大限度的提高社区划分的准确性和效率是重中之重。结合上述问题,本文从种子选择和社区扩展两方面,提出了一种新的基于种子扩展的社区发现算法,并对其改进和并行化处理,其具体工作如下:(1)针对大多数重要节点衡量方法的片面性和不准确性等问题,本文提出了一种基于局部信息和全局信息的节点影响力计算方法(LGI,Local and Global Information based Node Influence Method),利用节点在网络中的局部信息和全局信息,衡量每个节点的综合影响力,挑选前k个影响力大的节点作为种子。实验表明,LGI方法不仅能发现影响力高的节点,而且与其他节点影响力计算方法相比,节点影响力排序结果更加准确。随后,本文提出了一种基于种子扩展的社区发现算法(SELCDA,Seed Expansion and LDA based Community Detection Algorithm)。种子和邻居节点共同组成初始社区。引入基于Gibbs采样的LDA主题模型,根据未分配节点到各个主题的概率,获得到各个社区的概率,将未分配节点划分到概率大的社区,从而获得网络的社区结构。实验表明,与其他社区发现算法相比,SELCDA算法发现的网络社区结构更加精确。(2)针对SELCDA算法初始社区重叠率过高,社区扩展策略不稳定等问题,本文提出一种基于相似性和距离的社区发现算法(SDCDA,Similarity and Distance based Community Detection Algorithm)算法。在种子选择阶段,加入过滤操作,防止种子相邻,初始社区过度重叠;在社区扩展阶段,根据未分配节点与社区的相似性和到社区的距离倒数之和,计算未分配节点到各个社区的优先级,将其划分到优先级较高的社区。对社区融合归并,获得网络社区结构。实验证明,与SELCDA算法相比,SDCDA算法进一步提高了社区发现的准确性。最后,基于Spark并行化计算框架,实现SDCDA算法的并行化(PSDCDA)。实验证明,随着CPU核数的增加,PSDCDA执行时间不断减少,且与其他并行化社区发现算法相比,PSDCDA算法在大规模数据集上表现出高准确性。

论文目录

文章来源

类型: 硕士论文

作者: 刘琴

导师: 马廷淮

关键词: 社区发现,节点影响力,模型,社区扩展,并行化

来源: 南京信息工程大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 南京信息工程大学

分类号: O157.5

DOI: 10.27248/d.cnki.gnjqc.2019.000191

总页数: 70

文件大小: 3966K

下载量: 29

相关论文文献

• [1].面向过程的任务并行化设计方法[J]. 计算机系统应用 2015(09)
• [2].“地理计算并行化”专辑导言[J]. 地球信息科学学报 2015(05)
• [3].“地理计算并行化”专辑征稿[J]. 地球信息科学学报 2014(06)
• [4].迎接并行化的明天[J]. 软件世界 2009(06)
• [5].并行化改进遗传算法的FPGA高速实现方法[J]. 信息与电子工程 2012(01)
• [6].设计结合建造——我国建筑运作模式的“并行化”操作研究[J]. 建筑学报 2019(04)
• [7].图染色算法的并行化[J]. 电脑编程技巧与维护 2018(03)
• [8].交通网络微观仿真并行化实现方法[J]. 系统管理学报 2014(04)
• [9].有限差分法的并行化计算实现[J]. 电脑知识与技术 2008(07)
• [10].有限差分法的并行化计算实现[J]. 微型电脑应用 2008(05)
• [11].装箱问题近似算法的并行化研究[J]. 中国科技信息 2009(17)
• [12].面向场景的人群疏散并行化仿真[J]. 系统仿真学报 2008(18)
• [13].C形状分析在函数和路径层次上的并行化[J]. 电子技术 2015(08)
• [14].提升小波并行化处理研究[J]. 价值工程 2011(34)
• [15].聚类分析的并行化实现技术研究[J]. 电子设计工程 2015(02)
• [16].太赫兹通信中高速数字信号处理并行化算法[J]. 太赫兹科学与电子信息学报 2017(06)
• [17].人体姿势估计中随机森林训练算法的并行化[J]. 计算机应用研究 2014(05)
• [18].基于深度学习的文本情感分析并行化算法[J]. 西南交通大学学报 2019(03)
• [19].自优化转导支持向量机并行化[J]. 计算机应用 2017(S2)
• [20].基于海量日志的入侵检测并行化算法研究[J]. 现代电子技术 2016(19)
• [21].电力通信大数据并行化聚类算法研究[J]. 电子技术应用 2018(05)
• [22].全景监控视频并行化处理[J]. 软件导刊 2015(11)
• [23].基于MapReduce的主成分分析算法研究[J]. 计算机科学 2017(02)
• [24].基于Spark平台的热点话题发现算法并行化研究[J]. 软件导刊 2016(09)
• [25].云平台下全维度电力设备监测数据并行化处理技术[J]. 电测与仪表 2020(09)
• [26].基于Spark的分布式大数据并行化聚类方法研究[J]. 湖北第二师范学院学报 2019(08)
• [27].基于ATM并行化采样优化算法的研究[J]. 长春师范大学学报 2018(06)
• [28].面向非规则Doacross循环的反馈式编译框架[J]. 信息工程大学学报 2018(01)
• [29].基于Geant4的射线探测仿真并行化研究[J]. 核电子学与探测技术 2011(11)
• [30].不同操作平台上的MCNP并行化计算[J]. 中国原子能科学研究院年报 2009(00)

标签：社区发现论文;  节点影响力论文;  模型论文;  社区扩展论文;  并行化论文;