基于度启发式的社交网络影响力最大化求解方法.pdf

(19)中华人民共和国国家知识产权局*CN101859315A*(12)发明专利申请(10)申请公布号CNCN101859315101859315A(43)申请公布日2010.10.13(21)申请号201010162309.2(22)申请日2010.04.30(71)申请人西北工业大学地址710072陕西省西安市友谊西路127号(72)发明人蔡皖东罗知林李勇军(74)专利代理机构西北工业大学专利中心61204代理人黄毅新(51)Int.Cl.G06F17/30(2006.01)权利要求书1页说明书4页(54)发明名称基于度启发式的社交网络影响力最大化求解方法(57)摘要本发明公开了一种基于度启发式的社交网络影响力最大化求解方法，其目的是解决现有贪婪方法全搜索社交网络节点具有复杂度高的技术问题。技术方案是将大量影响力较小的节点排除在种子节点搜寻范围之外，缩小了种子节点搜索范围，节约了大量盲目搜寻的时间，明显降低了社交网络影响力最大化求解方法的复杂度并提高了效率。实验验证和实际测试表明，本发明方法与现有技术贪婪方法相比，在影响力不受损失的情况下，运行时间只有现有技术方法的10％～50％。CN108593ACN101859315ACCNN110185931501859316A权利要求书1/1页1.一种基于度启发式的社交网络影响力最大化求解方法，其特征在于包括下述步骤：(a)输入社交网络数据，对节点按度数由大到小排序，选取前r％的高度数节点形成新的节点集合；其中r＝1～20；(b)申请大小与新的集合节点数目相同的堆栈并清空，在某一特定信息传播模型中计算新的集合中每个节点的影响力，并将所有节点的影响力建成一个最大堆，影响力最大的节点在最大堆顶部；将最大堆顶部的节点加入到种子节点集合中，对最大堆顶部清零并重新排序，第一个种子节点选取过程结束；(c)选取最大堆顶部的节点，重新计算最大堆顶部的节点加入到种子节点集合后影响力增值式中，表示影响力函数，S表示种子节点集合，v表示新加入节点；然后用堆排序算法重新排序，如果最大堆顶部的节点未发生改变或者是在本轮选择种子过程中重新计算过的节点，则将最大堆顶部的节点加入到种子节点集合中，然后对最大堆顶部清为零并重新排序，本轮种子节点选取过程结束，否则再次计算最大堆顶部的节点加入到种子节点集合后影响力增值，并对最大堆重新排序，直到最大堆顶部的节点不发生改变或者在本轮选择种子中重新计算过的节点为止。2CCNN110185931501859316A说明书1/4页基于度启发式的社交网络影响力最大化求解方法技术领域[0001]本发明涉及一种社交网络影响力最大化求解方法，特别是基于度启发式的社交网络影响力最大化求解方法。背景技术[0002]社交网络影响力最大化问题是指在社交网络中如何寻找一部分节点(种子节点)，使其具有最大影响力，此问题是一个NP难问题，目前提出的解决方法主要采用贪婪方法，即每次选取影响力增值最大的节点。Kempe等在文献Maximizingthespreadofinfluencethroughasocialnetwork(SIGKDD，pages137-146，2003)中针对社交网络影响力最大化问题提出了一种原始的贪婪方法。该方法在每次选择种子节点过程中，选取加入到种子节点集合后影响力增值最大的节点作为种子节点，并将它加入到种子节点集合中。该方法得到种子节点的影响力不低于最优方法的(1-1/e)，但此贪婪方法每次选择种子节点需要搜索社交网络所有节点，因此该方法的效率非常低。[0003]Leskovec等在文献中Cost-effectiveoutbreakdetectioninnetworks(SIGKDD，pages420-429，2007)提出一个CELF(Cost-EffectiveLazyForwardselection)优化贪婪方法，该方法是基于影响力具有子模函数特征提出的，即所有节点的影响力随着种子节点集合中节点数目增加在减弱，具有单调递减性。该方法分为两个步骤：第一个步骤用于选择第一个种子节点，在全部节点中搜索种子节点，选择影响力最大节点加入到种子节点集合中；第二个步骤用于选择余下种子节点，利用影响力具有单调递减性这一性质在部分影响力较大节点中搜索种子节点。由于在第二个步骤中此方法搜索种子节点空间的减少，该方法的效率有了较大提高。[0004]陈卫等在文献中Efficientinfluencemaximizationinsocialnetworks(SIGKDD，pp.199-208，2009)提出了NewGreedy和MixGreedy两个新的贪婪方法，均用于特定信息传播模型中，比如独立级联模型、带权级联模型等。其中NewGreedy方法是以节点间影响因子p选择相关边，建立一个全新的