基于中介中心性的网络传播节点影响力发现

摘要

随着互联网+的盛行，互联网已经逐渐渗透到生活的方方面面。即时通讯如QQ、微信等，在互联网的兴起的初期已经得到了很好的发展，在当今互联网盛行的时代，以微博、Twitter、Facebook为代表的社交网络服务（SNS）微型博客，逐渐将人与人的关系变的更加直接，也变得更加复杂，信息的流通也变得更加迅速和即时。在海量的社交网络数据中，通过研究和分析，寻找出社交网络中影响力最大的Top-K节点，对信息在社交网络中的传播有着举足轻重的作用，影响力Top-K节点挖掘算法也成为了人们研究和改进的热点。本文主要基于传统的中介中心性算法，旨在提高中介中心性算法的效率和准确性。首先对海量的社交网络数据进行随机游走数据抽样，其次，在抽取的样本上采用基于局部因子的差异化中介中心性算法。之前大部分社交网络影响力发现的研究对象都是无权无向图，为了更加贴近实际，本文的研究对象是有向图。　　（1）由于互联网的快速发展，为社交网络研究提供了海量的数据，但是数据量过大，势必会对影响力研究造成影响，针对此问题，本文改进了现有的随机游走抽样算法，提出了针对有向图的基于不等概率的随机游走数据抽样算法（DUPRW）。通过优秀的抽样算法对集合进行抽样后的样本完全能够获取原有总体集合的特征，但是传统的抽样方法难以刻画出社交网络内部的复杂性、不确定性等特性。本文首先对社交网络划分社区，并为每个节点增加虚拟邻居节点，然后在社区内不等概率的随机选取起始节点Vi，标记其邻居节点，并以概率θ在邻居节点中随机选取或者远程跳转选取节点，作为随机游走的下一步起始节点，不断重复此步骤，当随机游走陷入局部子图时，优先选取未抽样集合中出度较大的节点作为下一次随机游走抽样的起始节点。抽取样本完成后，在剩余未被抽样的节点集合中，选取出度大于某一阈值以及社区间相连接的节点作为补充节点加入到样本集合中，避免重要节点未被抽样，无法精确刻画社交网络的复杂结构。抽取后的样本，将作为影响力发现算法的数据集进行社交网络影响力Top-K节点的发现。通过K-S检验等实验验证了本文提出的基于不等概率的随机游走数据抽样算法的有效性。　　（2）传统的中介中心性算法对经过节点Vi的不同长度的最短路径，以及节点所在位置不同的最短路径，都作同一度量。本文基于信息在传播中的衰减理论，即信息每传播一次，信息量衰减为之前信息量的δ(0<δ<1)倍，依据此理论对不同长度以及不同节点位置的最短路径做差异化处理。其次，传统的中介中心性算法对节点在整个社交网络全局中的重要性有着较为精准的刻画，但是忽略了节点在局部网络中的影响力，本文通过加入节点的局部影响力，对节点的全局影响力进行补充，形成了节点综合影响力，并总结提出了基于局部因子的差异化中介中心性算法（DLBC）。最后通过在不同数据集上进行了相关性等实验，验证了本文提出的基于局部因子的差异化中介中心性算法的有效性。

目录

声明

第1章 绪论

1.1研究背景和选题意义

1.2国内外研究现状

1.3论文的主要研究内容

1.4论文组织结构及内容安排

第2章 相关技术概述

2.1社交网络基本概念

2.2社交网络影响力最大化算法

2.3社交网络数据抽样相关理论

2.4本章小结

第3章 基于不等概率的随机游走数据抽样算法

3.1复杂网络的数据抽样理论

3.2基于不等概率的随机游走数据抽样算法

3.3实验及其结果分析

3.4本章小结

第4章 基于局部因子的差异化中介中心性算法

4.1中介中心性算法

4.2基于局部因子的差异化中介中心性算法

4.3实验及其结果分析

4.4本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢