社会网络中的节点影响力度量和k-节点集的影响力最大化问题研究

发布时间：2018-01-07 23:05

  本文关键词：社会网络中的节点影响力度量和k-节点集的影响力最大化问题研究　出处：《山东大学》2017年博士论文　论文类型：学位论文

  更多相关文章： 社会网络 信息传播 影响力度量 影响力最大化 传播概率

【摘要】：互联网技术的快速发展使得微博、微信等社会网络逐渐成为大众获取信息、分享信息的重要媒介。社会网络的出现使所有的网络用户都有机会参与到信息传播的过程中,用户不仅是信息的接收者,同时也是信息的发布者和传播者。用户的影响力在信息传播过程中发挥着巨大的作用,有影响力的用户能够推动信息的大规模扩散,快速地吸引更多的用户关注。因此,选择一定数量的有影响力的用户(被称为种子节点)在社会网络中进行口碑营销已成为一种重要的产品营销手段。除了在市场营销领域,识别和利用有影响力的用户在挖掘意见领袖、控制谣言传播、推荐等方面也有着巨大的应用价值。随着网络规模的不断扩大,如何衡量大规模社会网络中用户的影响力、如何选取一定数量的用户利用他们的影响力以实现信息的最大化传播(也被称为影响力最大化)等问题已成为目前国内外研究的热点,也是本文关注的主要问题。本文以国家自然科学基金为依托,围绕社会网络中的影响力传播这一研究主题,主要针对社会网络中的用户影响力度量和影响力最大化这两个关键问题展开研究。本文的主要工作和创新点包括以下几个方面。(1)本文提出了一种考虑传播概率的动态节点影响力度量方法。网络中节点的影响力可看作节点的传播能力,即以该节点为起始节点的传播过程最终在网络中覆盖的节点数量。传播概率是影响传播结果的重要因素,同一节点的传播能力在不同的传播概率下是不同的。传统的影响力度量方法没有考虑这一因素,导致这些度量方法对传播概率敏感,例如度中心性在传播概率较小时度量效果较好,而半局部中心性在传播概率较大时度量效果较好。为了减轻度量方法对传播概率的敏感性,本文利用度中心性和半局部中心性在不同传播概率下表现恰好相反的特点,将传播概率作为一个参数将这两者结合,提出了混合度中心性方法。本文的方法可自然地根据传播概率的变化调整度中心性和半局部中心性的比例以适应节点影响力在不同传播概率下的传播特点。实验结果表明,该方法在不同的传播概率下表现稳定,且在绝大多数传播概率下均能取得最优的度量效果。(2)本文提出了一种可调节的基于有限步传播的节点影响力度量方法。通过对比大量的实验,本文发现常见的节点影响力度量方法不仅对传播概率敏感,对网络结构也存在敏感性。面对一个未知的网络,无法确定哪种度量方法有效。针对这个问题本文提出一种强鲁棒性的度量方法——可调节的有限步传播方法。根据社会网络的传播特点,本文的方法基于传播路径计算了一个节点对其四步之内的节点的影响力。为了降低时间复杂度,我们将距离该节点二三四步远的节点看作一个整体,粗略估算了节点对这部分较远节点的影响力。通过设置并调节参数,该方法可以适应不同网络的传播特点。实验表明,我们的方法在不同类型、不同规模的网络中均有较好的表现,具有很强的鲁棒性,且方法中参数的选取有一定的规律可循,具有很好的实用性。(3)本文提出了一种适用于微博网络的影响力最大化算法。本文关注并致力于解决影响力最大化在微博网络中应用存在的两个问题:一是如何将微博中的行为、内容等信息应用到影响力最大化问题中,二是解决贪心算法及其改进算法在大规模社会网络中运行效率低的问题。本文利用微博网络中的行为、内容等信息对用户之间的影响力强度建模,并将其与传播模型相结合,增强了传播模型的实用性;针对贪心算法在大规模网络中运行效率低的问题,本文将节点影响力度量与影响力最大化问题相结合,提出了一种基于候选节点的影响力最大化算法。该算法首先对节点影响力进行简单评估,保留影响力较大的节点作为候选节点,再运用贪心算法从候选节点中选择种子节点。本文系统地分析比较了常见的节点影响力度量方法所选择的候选节点对种子节点选取结果的影响。实验表明,该方法可以大大缩短种子节点的选取时间,且不影响种子节点的选取效果。(4)本文提出了为未激活的种子节点寻找替补节点的问题及解决方法。当部分种子节点无法激活时,如何有效地寻找替补节点来代替它们以减少损失,这是影响力最大化在实际应用中很有可能遇到的问题。通过对问题的分析本文提出了三种寻找替补节点的策略:1.通过对影响力最大化问题中的静态贪心算法进行扩展,提出了有理论依据的扩展的静态贪心算法;2.为了提高贪心算法寻找替补节点的效率,本文利用静态图模拟传播过程的特点,提出了全静态算法;3.提出了在选择种子节点时多选一部分预备种子节点作替补节点的预选式贪心算法。实验结果表明:本文提出的三种方法选出的替补节点均能很好地代替未被激活的种子节点。
[Abstract]:This paper puts forward a method of measuring the influence of users in social networks . This paper presents a method for maximizing the influence of greedy algorithm in large - scale network .

【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：G206;TP393.09
，

本文编号：1394585