论文部分内容阅读
随着互联网技术和社交媒体的快速发展,人们开始在社交媒体如Facebook,微博,领英,微信上进行信息的传播和分享。影响力最大化问题就是在网络中寻找k个节点,通过这k个节点可以影响网络中更多数目的节点。相比于传统的大众传媒如电视、报纸和广播,利用社交媒体进行信息传播具有高效、便捷、可信度高等优点,但同时一些不当舆情的传播也会给社会稳定造成很大的危害。在此背景下,本文基于复杂网络开展了一系列的影响力最大化研究,重点在普通网络中、带符号网络中以及带有竞争的社交网络中研究如何基于传播路径分析的方法使得网络中的影响力达到最大化,具体的研究内容如下:(1)我们提出了独立级联模型下基于最大似然的影响力最大化算法MLIM。首先我们根据网络中的节点度或者边上的权重值将复杂网络抽样成缩略图,其次将构造缩略图筛选出的节点作为顶点分层,在得到的顶点分层中,对每一层顶点计算其祖先顶点到该顶点的路径的概率,通过最大似然方法得到每个顶点的激活概率L(u),最后输入路径概率最小的k个顶点构成种子集合。通过在现实世界的网络上进行实验,结果表明与传统的Greedy算法相比,MLIM算法的复杂度更低,能更好的适用于各类大型网络。(2)我们提出了有符号网络中基于传播路径分析的影响力最大化算法GREEDY-SIM。首先我们提出了有符号网络中的独立级联模型SNIC,并在此模型上提出了独立路径算法,并试图通过单源最短路径法找到每个顶点对之间的前m条独立路径,利用得到的m条独立路径我们可以构造覆盖集合R(v),然后利用覆盖集合R(v)计算正影响力节点以及负影响力节点的传播范围,最后利用贪婪策略筛选出k个正状态下的节点作为种子节点集合。通过在无符号网络以及带符号网络中进行实验,结果表明该方法可扩放性好,可以更为精准的发现有影响力的节点,且影响力最大化的传播范围更为广泛。(3)我们提出了在竞争性的社交网络中带有unwanted user的影响力最大化算法IMPP。该方法首先寻找顶点v和u之间所有的独立路径L,通过L得到节点的传播路径,并计算出激活概率值a(v,u),随后通过对候选顶点的独立路径进行分析,计算其加入某个节点后的传播增量△s(x),最后依据△s(x)的变化,选择变化最大的k个节点更新种子集合S。通过对真实世界的社会网络进行实验,结果表明,无论是算法的运行时间还是影响力的传播范围,IMPP算法都能取得很好的性能。