基于图论的社交网络关键节点挖掘和推荐算法研究.caj

基于图论的社交网络关键节点挖掘和推荐算法研究
作者 : 郑吉
学位授予单位 : 江苏大学
学位名称 : 硕士
导师姓名 : 周莲英
学位年度 : 2018
关键词 : 社交网络；关键节点挖掘；推荐算法；图论；介数
摘要 : 图论以图为研究对象,是研究现实各类网络最常用的建模语言和分析工具。用图论研究网络问题,可简化研究的复杂程度。社交网络是人们现实世界社交活动在网络的延伸。同现实世界相似,社交网络处于中心性地位的核心人物,基于威望、信任与活跃度等因素,仍然对信息的局部辐射起着重要作用,而处于社交网络区域之间的连通性关键人物,基于位置关系,则对信息在网络全局之间的穿透有着不可低估的力量。论文立足于社交网络信息传播选择谁作为主节点进行传播及推荐什么样的信息进行传播的问题,以社交网络中这两类关键节点的挖掘及信息推荐技术为研究内容,目的是更好地进行舆论引导与控制,同时更有效地为用户提供信息服务。论文的主要研究工作及成果包括:(1)提出了基于层次性过滤的关键节点挖掘方法,在降低挖掘算法计算规模的同时,能保证挖掘质量。层次性过滤以层次性指标代替单一指标体系为前提。论文对中心性节点的评价采用的是度和聚集系数。度和聚集系数相结合,不仅能过滤节点计算量,相比较常用的单一指标聚集系数,有一定度保证,且聚集系数较高的节点才能保证较大范围的信息渗透能力。论文对连通性节点的评价采用的是嵌入性和介数,嵌入性也是一简单的局部性指标,介数是一种挖掘精度较高、但需进行全局计算的指标,因嵌入性与介数的一致性,可以将嵌入性作为介数计算的先期过滤的指标。(2)基于流量的改进型介数计算方法设计,通过前期过滤和限层计算有效降低了计算规模。改进之处包括使用嵌入性指标过滤候选节点、考虑不同度节点发出的流量不同、先宽搜索只需进行到有限层等三个方面。过滤的作用是可以在过程中逐步淘汰无需计算的子树,大幅度降低计算规模;有限层计算设计思想来自“信息和节点用户都具有的类别属性会给信息传播范围带来抑制作用”,对应一次先宽搜索,层次之间的间隔越大,类别的差异性越大,表现在信息传输上就是从顶层发出的信息,实际到达低层的是很少的,由此可以适当忽略较低层的流量,以减少计算量。(3)基于选择性热传导/物质扩散的社交网络推荐算法设计,充分发挥了两种算法的各自优势,并体现了社交网络用户之间的相互影响。论文首先用过程论证的方法论证了两类推荐算法特点,以作为目前仅是实验验证的补充,并指出这两类算法本质上仍然与基于协同过滤的推荐算法是类似的;基于关键节点对信息传播的强大影响力,论文对社交网络推荐算法的研究以向网络中的关键节点进行推荐为前提,利用两类关键节点具有的特色鲜明的信息传播作用,选择精准性较高的基于物质扩散的推荐算法为中心节点推荐算法,选择多样性较好的基于热传导的推荐算法为连通性节点推荐算法,以最大限度发挥各自的优势;同时考虑社交网络中节点的相互影响,论文基于特征向量中心性对两类算法进行了改进。(4)基于适合于图操作的并行计算框架Spark,对论文所提出的算法进行了实验验证。实验设计工作包括评价方法设计、实验数据集获取、实验平台性能优化、实验结果分析等。关键节点挖掘算法以在SIR模型中影响的人数为评价指标,实验结果表明论文提出的关键节点挖掘算法效果较好。推荐算法以准确性、多样性为评价指标,实验结果表明论文提出基于选择性热传导/物质扩散的社交网络推荐算法,在保障一定准确性的同时提高了推荐结果的多样性。