论文部分内容阅读
社交网络由节点和边构成,节点通常指个人或者组织,边指其关联关系。信息通过社交网络进行传播,影响力最大化即是研究在网络中寻找k个目标节点作为信息传播的源点,使这些节点按照某种信息传播机制去影响其它节点,最终使信息达到最大化的扩散范围。研究如何使信息在社交网络中广泛的传播达到网络营销的目的就具有一定的现实意义。随着互联网技术的不断发展,微博因具有“平民化”使用门槛在国内发展迅速,所以选择在微博网络研究影响力最大化问题。影响力最大化算法的研究主要分为两个部分:贪心算法和启发式算法。贪心算法由于其时间复杂度高而不能用于大规模网络上,启发式算法由于最终得到的目标节点影响力效果不理想也不被广泛使用。由于在线社交网络用户量庞大以及关系复杂,需要大数据集下快速准确的找到目标节点集合,现有算法的时间复杂度和准确性仍待改进,如何在大规模数据集下依据网络平台本身特性来提高算法结果的有效性和减少算法的时间消耗仍是值得研究的问题。通过对微博数据进行分析,发现微博网络具有无标度性、异配性、以及较小的聚类系数等,同时网络中节点之间的连接存在不平等的偏斜关系,节点在网络中具有不同的可用度。传统独立级联模型没有考虑网络节点的以上特性,因此在节点间影响大小的度量上存在偏差。基于此,改进了传统独立级联模型中对节点间影响大小的计算方式,构建了基于节点偏斜关系和节点可用度的微博信息传播模型IDSA(Information Diffusion Based on Skewed Relationship and Availability of Node),并提出了基于IDSA的影响力最大化算法,该算法利用节点影响力的有限性和覆盖性改进了贪心算法中对节点影响力增量的计算,将其限制在4层好友范围并且忽略被覆盖节点的计算。最后,分别在新浪微博和腾讯微博数据集上实施该算法并与传统的算法做比较,结果显示该影响力最大化算法有较好的表现。