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

发布时间：2020-05-21 00:48

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

网络节点,覆盖率,有限层,直径

图 5.2 网络节点覆盖率与直径关系Figure 5.2 relationship between node coverage and diameter一种用于排序节点连通性的指标，为了衡量基于有限层先宽法所得结果的准确性，定义有限层先宽搜索的排名前 10%的节计算方法得到的排名前 10%的结果集概率为准确率。当确定，有限层先宽搜索对在不同阈值 D 下计算出的介数与的介数比较，实验结果如图 5.3 所示。当 D 值为 3 时，，有限层介数计集上的准确率都达到了 70%以上，在 Karate 数据集上甚至 D 值的增大，有限层介数计算准确率也逐步提高，当 D 达宽搜索介数方法在所有的数据集上的准确率都超过了 90%。经出的有限层介数计算方法在有效地控制计算规模的情况下准

影响图,有限层,准确性,阈值

图 5.3 有限层介数计算方法准确性与阈值 D 关系Figure 5.3 relationship between accuracy of limited breadth first searbetweenness calculation method and threshold D图 5.4 关键节点对用户影响图Figure 5.4 impact of key nodes on users对论文提出的算法挖掘出的关键节点进行影响力分析。图 5
【学位授予单位】：江苏大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.3;O157.5

【参考文献】