基于成本预算的信息影响力最大化算法

作     者：李彦慧 

作者单位：燕山大学 

学位级别：硕士

导师姓名：刘永山;张淑杰

授予年度：2020年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：社交网络 影响力最大化 成本预算 路径优化 信息传播 

摘      要：社交网络是信息化时代下的一个重要产物,并且网络中的数据每天以指数形式增长,如何有效分析并处理好这些数据,是社交网络中研究的内容,而影响力最大化则是其中的一个重要研究方向。影响力最大化涉及到日常生活中的各个方面,例如:产品推广,信息安全,网络搜索等,在现实生活中,是否达到影响力最大化通常与成本预算有关。因此,基于成本预算影响下的最大化具有重要的研究意义,本文通过研究影响力最大算法和信息传播模型,结合图论的相关理论,将进行以下研究。首先,基于网络中节点成本问题,提出了基于成本预算的节点影响力最大化算法,本文提出的第一个算法首先分析节点的KS指标和结构洞属性,以及节点的介数中心性和聚类系数,通过平衡系数,有机的将节点内外属性结合起来,使得这些属性更好的反映出节点的重要性,此外,结合节点的成本和节点属性提出了一种新的传播概率,使得节点影响力最大化的同时,信息的传播更加符合真实情况。然后,基于网络中边的传播成本问题,提出了一种基于成本预算的路径优化算法,该算法基于Dijkstra算法的思想,实现信息传播到最终节点路径的同时路径成本最小,该算法首先分析边权值的计算方式,并基于带权图中边的传播成本以及响应时间,提出了一种新的边权值计算方式,以及结合节点的重要性,提出等效路径的概念,该算法可以在成本预算的前提下,实现路径最优。最后,对提出的两个算法进行对比实验,在实验中分别使用不同类型的网络数据集,与同类型算法进行比较,通过实验综合分析可知,两种算法的运行时间虽然不是最短,但是影响范围最大,总体效果较为理想。