基于社区结构的Top-K影响力节点发现算法研究

发布时间：2017-07-14 12:24

  本文关键词：基于社区结构的Top-K影响力节点发现算法研究

  更多相关文章： 社区发现 相似度 线性阈值模型 影响力最大化 动态规划

【摘要】：社会网络是由个体及其之间的各种关系所组成的复杂网络,它在我们的人类生活中随处可见,例如蛋白质相互作用网、演员合作网、病毒传播网等等,各种信息往往是通过这种复杂的社会网络以“口碑(Word of Mouth)”形式来进行传播和扩散的。按照一定的传播模型,如何找到K个具有影响力的节点,使得信息在社会网络中传播范围达到最大的问题,被称为影响力最大化问题,也叫做目标集合选择问题,它在市场营销、广告推广、病毒传播以及舆论预警等方面有着非常重要的作用。基于影响力在社区内部更易扩散的特性,首先对社区发现问题进行了深入地研究。通过分析发现现有的社区发现算法存在错分节点和遗留外围节点的问题,利用凝聚层次聚类思想,提出了一种基于相似度序列的社区发现算法ACSS(Agglomerative Clustering Algorithm Based on the Similarity Sequence)。在真实网络和计算机生成网络数据集上的实验结果表明,相比于一些典型的社区发现算法,ACSS算法具有更高的聚类精度,更能体现真实的社区结构。以发现的社区结构为基础,利用线性阈值传播模型,提出了一个基于社区结构的Top-K影响力节点发现算法IMBC(Influence Maximization Algorithm Based on the Community Structure)。首先,利用k-shell分解方法度量节点的潜在影响力,选择部分具有最大潜在影响力的节点;然后,通过减少一些不必要的计算,来改进传统的贪心算法;最后,基于发现的社区结构,利用动态规划思想来发现Top-K影响力节点。实验结果表明,对于一些真实网络数据集,与其他一些具有代表性的算法进行比较,对于给定的K值,IMBC能够影响更多的节点,同时具有更高的准确性。为了验证IMBC算法的合理性、有效性和正确性,将算法在新浪微博数据集上进行了应用研究。利用ACSS对网络进行了社团的挖掘,然后以发现的社区结构为基础,对新浪微博网络进行了Top-K影响力节点的发现,最后选取了一个最大的社区来进行信息传播过程的模拟,从而得出信息传播以“口碑效应”形式由内向外扩散的规律。
【关键词】：社区发现 相似度 线性阈值模型 影响力最大化 动态规划
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-18
• 1.1 研究背景与意义8-10
• 1.2 国内外研究现状10-16
• 1.3 本文主要工作16-17
• 1.4 本章小结17-18
• 2 基于相似度序列的社区发现算法18-32
• 2.1 问题描述18-19
• 2.2 相关研究19-21
• 2.3 ACSS算法的设计与实现21-25
• 2.4 仿真实验与结果分析25-31
• 2.5 本章小结31-32
• 3 基于社区结构的TOP-K影响力节点发现算法32-47
• 3.1 问题描述32
• 3.2 符号定义32-33
• 3.3 IMBC算法的设计与实现33-40
• 3.4 仿真实验与结果分析40-45
• 3.5 本章小结45-47
• 4 IMBC算法在社交网络上的应用47-54
• 4.1 微博的功能特性分析47-48
• 4.2 对微博的TOP-K影响力节点的发现48-52
• 4.3 信息传播过程的模拟52-53
• 4.4 本章小结53-54
• 5 总结与展望54-56
• 5.1 本文主要研究成果54-55
• 5.2 下一步工作展望55-56
• 致谢56-58
• 参考文献58-66
• 附录I 攻读硕士学位期间发表的论文目录66-67
• 附录II 攻读硕士学位期间参与的科研工作67

【相似文献】

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

1 智源;行飞;;复杂网络社区结构问题综述[J];阴山学刊(自然科学);2011年03期

2 王林;戴冠中;赵焕成;;一种新的评价社区结构的模块度研究[J];计算机工程;2010年14期

3 韩瑞凯;孟嗣仪;刘云;郭英慧;张彦超;;基于兴趣相似度的社区结构发现算法研究[J];铁路计算机应用;2010年10期

4 刘旭;易东云;;基于保守合并策略的复杂网络社区结构发现[J];复杂系统与复杂性科学;2011年04期

5 黄发良;肖南峰;;用于网络重叠社区发现的粗糙谱聚类算法[J];小型微型计算机系统;2012年02期

6 马瑞新;邓贵仕;王晓;;启发式动态社区挖掘算法研究与实现[J];大连理工大学学报;2012年02期

7 梁沙沙;;复杂网络重叠社区结构发现算法研究[J];阴山学刊(自然科学);2013年02期

8 刘大有;金弟;何东晓;黄晶;杨建宁;杨博;;复杂网络社区挖掘综述[J];计算机研究与发展;2013年10期

9 时京晶;;三种经典复杂网络社区结构划分算法研究[J];电脑与信息技术;2011年04期

10 黄发良;肖南峰;;基于线图与PSO的网络重叠社区发现[J];自动化学报;2011年09期

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

1 刁元波;李梦龙;文志宁;印家健;郑波;;人类细胞信号网络社区结构分析[A];第九届全国计算（机）化学学术会议论文摘要集[C];2007年

2 刘欣;李德毅;李兵;王树良;陶志伟;;复杂网络社区发现研究[A];2006全国复杂网络学术会议论文集[C];2006年

3 单波;姜守旭;张硕;高宏;李建中;;IC:动态社会关系网络社区结构的增量识别算法[A];第26届中国数据库学术会议论文集（A辑）[C];2009年

中国重要报纸全文数据库 前1条

1 记者 熊明 实习生 李瑞莹;度假区不断创新社区结构[N];云南日报;2013年

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

1 闵磊;复杂网络社区发现算法研究[D];华中师范大学;2015年

2 蔡清;基于群体智能优化的大数据复杂网络结构分析[D];西安电子科技大学;2015年

3 陈毅;基于统计推理的复杂网络社区结构分析[D];哈尔滨工业大学;2016年

4 杜楠;复杂网络中社区结构发现算法研究及建模[D];北京邮电大学;2009年

5 李一啸;基于复杂网络和演化博弈理论的社会[D];浙江大学;2010年

6 韩院彬;Web服务网络分析和社区发现研究[D];天津大学;2014年

7 谢辉;基于复杂网络的若干动态机制研究[D];西安电子科技大学;2013年

8 任薇;基于微博的社会网络特征研究[D];西南大学;2014年

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

1 王童童;社区框架与隐藏社区的挖掘[D];山东建筑大学;2015年

2 贺成龙;复杂网络中的社区发现算法研究[D];解放军信息工程大学;2015年

3 贾娜;基于矩阵分解的重叠社区探测研究[D];吉林大学;2016年

4 李青云;多阶信息模型及推荐技术研究[D];北京理工大学;2015年

5 万云;基于模块度最大化的社区发现算法的研究[D];燕山大学;2016年

6 邹杰;日照滨海民俗村社区结构与旅游发展互动研究[D];曲阜师范大学;2016年

7 王焕杰;社会网络数据发布中有效保护社区结构的匿名方法研究[D];广西师范大学;2016年

8 王洪珏;复杂网络节点相似性研究及其应用[D];华北电力大学;2016年

9 纪开祝;复杂网络重叠社区结构发现的算法研究与实现[D];闽南师范大学;2016年

10 赵倩;基于社区结构的Top-K影响力节点发现算法研究[D];华中科技大学;2015年

，

本文编号：541028