一种社交网络中影响力最大化节点的探测方法及系统

摘要

本发明提供一种社交网络中影响力最大化节点的探测方法，包括获取网络模型；遍历网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；以节点的影响力传播期望值为指标，依次将所有节点对应的放入初始为空的大顶堆中；从堆顶弹出影响力期望值最大的节点加入种子节点集合，更新该节点的所有邻居节点的影响力期望值；计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些节点作为影响力最大化种子节点集合输出。实施本发明，不仅计算复杂性低且效率高，还能解决影响力覆盖范围重叠的问题。

权利要求

1.一种社交网络中影响力最大化节点的探测方法，其特征在于，包括以下步骤：步骤S1、获取社交网络所给定的网络模型；

步骤S2、遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；

步骤S3、以节点的影响力传播期望值为指标，依次将所有节点对应地放入初始为空的大顶堆中；

步骤S4、从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

步骤S5、计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些节点作为影响力最大化种子节点集合输出；

所述网络模型表示为G(V,E)；其中，V表示社交网络中的节点，代表网络中的用户；E表示社交网络中的边，代表用户之间的关系；

根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时节点u激活节点v的概率；

根据公式(2)，更新节点的所有邻居节点的影响力传播期望值：2

e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p    (2)；

其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻居节点v的二阶邻居中被选择成为种子节点的个数；

根据公式(3)，计算各节点各自与所有邻居节点之间的相似性；

其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

2.一种社交网络中影响力最大化节点的探测系统，其特征在于，包括：社交网络模型获取单元，用于获取社交网络所给定的网络模型；

节点影响力传播期望值计算单元，用于遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；

节点集合排序单元，用于以节点的影响力传播期望值为指标，依次将所有节点对应地放入初始为空的大顶堆中；

邻居节点影响力传播期望值更新单元，用于从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

影响力最大化节点输出单元，用于计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些节点作为影响力最大化种子节点集合输出；

所述网络模型表示为G(V,E)；其中，V表示社交网络中的节点，代表网络中的用户；E表示社交网络中的边，代表用户之间的关系；

根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时节点u激活节点v的概率；

根据公式(2)，更新节点的所有邻居节点的影响力传播期望值：2

e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p   (2)；

其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻居节点v的二阶邻居中被选择成为种子节点的个数；

根据公式(3)，计算各节点各自与所有邻居节点之间的相似性；

其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

说明书

一种社交网络中影响力最大化节点的探测方法及系统

技术领域

[0001] 本发明涉及社交网络技术领域，尤其涉及一种社交网络中影响力最大化节点的探测方法及系统。

背景技术

[0002] 随着科学技术的飞速发展，人类进入了Web2.0时代。随着微博，微信，抖音等网络应用的用户越来越多，网络的使用越来越普及，人们日常生活中的沟通和交流通过网络应
用进行连接，构成庞大的社交网络。社交网络结构中蕴含着巨大的信息，对社交网络的研究
和分析具有巨大的经济价值和社会价值。

[0003] 影响力最大化问题是社交网络分析中一个实际问题，由于其应用场景非常丰富，已经成为社交网络研究领域中的热点问题。例如，当商家需要推广产品时，选择那些人群作
为初始传播者，才能使得产品推广的效果达到最好呢？这就是影响力最大化问题对应的原
始问题。

[0004] 影响力最大化问题就是在一个真实社交网络中通过某种方法找到k个最有影响力的种子节点作为信息传播源，使得整个种子节点集合产生的影响力传播范围最大，适用于
包括但不限于病毒营销、生物细胞结构分析、舆情控制和病毒传染等等场景。

[0005] 目前，社交网络中解决影响力最大化问题的近似算法主要有多种算法。例如，Kemp和Kleinberg等人在独立级联模型和线性阈值模型上证明了影响力最大化问题是一个NP难
的问题，提出贪心算法来计算种子节点集的影响结果能够达到最优解。但是上述贪心算法
存在不足之处，其不足之处在于：(1)该算法使用蒙特卡洛模拟去近似估计网络中每个节点
的影响力增益，为保证准确性而导致蒙特卡洛模拟的次数很高(一般设置为10000次)；(2)
当选择一个节点之后，后续仍需要对每一个节点重新计算影响力增益，使得计算量非常大，
从而造成在庞大的社交网络数据集中，难以快速高效找出具有最大影响力的种子节点集。
又如，Leskovec和Krause等人提出了对原始的贪心算法进行改进的CELF算法，通过计算节
点影响力增益的上界，然后利用目标函数的子模性，在计算过程中使用节点的影响力上界
代替节点的真实影响力，尽管能够避免贪心算法中大量不必要计算，大幅度提高计算效率，
但是在大型网络中选择少量种子节点仍然需要很长的时间。

[0006] 因此，许多启发式算法被相继提出，启发式算法通过分析网络的拓扑结构，从而提取出一个能够近似度量节点影响力的指标，基于此指标对节点的影响力进行排序，从而快
速有效的选择出有较大影响力的种子节点集。

[0007] 在社交网络中，常用的启发式指标有度、接近中心性、介数中心性、距离中心性、特征向量中心性、核数等。介数中心性、接近中心性等个别指标具有较大的计算复杂度，在大
型网络中仍然不适用于评估节点重要程度，从而用于求解影响力最大化问题，所以选择计
算复杂性较小的指标精确的度量节点在社交网络中的影响力是我们接下来努力的方向。例
如，Chen等人基于度指标提出DegreeDiscount算法。节点的度是一个重要指标，基于节点度
选取的种子节点传播范围通常优于其他指标。度大的节点可能大概率集中在同一区域，这
样虽然单个节点的影响力较大，但是造成了影响力范围覆盖较大的问题，造成整体上影响
力传播范围较小。考虑到这一点，度折减算法首先按照节点的度选择第一个种子节点，在后
续的选择过程中，考虑到节点和邻居节点之间的相互影响，为了减少邻居节点在下一轮被
选中的几率，因此对节点的度进行折减，使选择的种子节点具有较大的度同时，也让节点尽
量分散，该算法运行时间短并且能到达到与贪心算法近似的传播范围，但是该方法只是基
于一阶邻居范围，经过详细分析，二阶范围邻居也是一个非常重要的参考因素。

[0008] 然而，上述现有社交网络中解决影响力最大化问题的方法，要么准确率高且计算复杂性也高，要么复杂度低且准确性也较低，同时还存在影响力覆盖范围重叠的问题。因
此，有必要对现有社交网络中解决影响力最大化问题的方法进行改进。

发明内容

[0009] 本发明实施例所要解决的技术问题在于，提供一种社交网络中影响力最大化节点的探测方法及系统，不仅计算复杂性低且效率高，找到的种子节点集合传播范围广，还能解
决影响力覆盖范围重叠的问题。

[0010] 为了解决上述技术问题，本发明实施例提供了一种社交网络中影响力最大化节点的探测方法，包括以下步骤：

[0011] 步骤S1、获取社交网络所给定的网络模型；

[0012] 步骤S2、遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；

[0013] 步骤S3、以节点的影响力传播期望值为指标，依次将所有节点对应地放入初始为空的大顶堆中；

[0014] 步骤S4、从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

[0015] 步骤S5、计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些节点作为影响力最大化种
子节点集合输出。

[0016] 其中，所述网络模型表示为G(V,E)；其中，V表示社交网络中的节点；E表示社交网络中的边。

[0017] 其中，根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：

[0018]

[0019] 其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时
节点u激活节点v的概率。

[0020] 其中，根据公式(2)，更新节点的所有邻居节点的影响力传播期望值：

[0021] e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p2   (2)；

[0022] 其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻
居节点v的二阶邻居中被选择成为种子节点的个数。

[0023] 其中，根据公式(3)，计算各节点各自与所有邻居节点之间的相似性；

[0024]

[0025] 其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

[0026] 其中，所述预定排序方式为从大到小的排列方式。

[0027] 本发明实施例还提供了一种社交网络中影响力最大化节点的探测系统，包括：

[0028] 社交网络模型获取单元，用于获取社交网络所给定的网络模型；

[0029] 节点影响力传播期望值计算单元，用于遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值：

[0030] 节点集合排序单元，用于以节点的影响力传播期望值为指标，依次将所有节点对应地放入初始为空的大顶堆中；

[0031] 邻居节点影响力传播期望值更新单元，用于从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

[0032] 影响力最大化节点输出单元，用于计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些
节点作为影响力最大化种子节点集合输出。

[0033] 其中，根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：

[0034]

[0035] 其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时
节点u激活节点v的概率。

[0036] 其中，根据公式(2)，计算各节点的所有邻居节点的影响力传播期望值：

[0037] e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p2    (2)；

[0038] 其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻
居节点v的二阶邻居中被选择成为种子节点的个数。

[0039] 其中，根据公式(3)，更新节点各自与所有邻居节点之间的相似性；

[0040]

[0041] 其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

[0042] 实施本发明实施例，具有如下有益效果：

[0043] 本发明将二阶邻居范围评估节点的影响力计算和节点期望值折减计算相结合，并在网络中引入节点相似性概念，用于减少影响力范围重叠的问题，同时利用网络中节点的
局部信息评估节点的重要程度，不仅计算复杂性低且效率高，找到的种子节点集合传播范
围广，还能解决影响力覆盖范围重叠的问题。

附图说明

[0044] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本
发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，根据
这些附图获得其他的附图仍属于本发明的范畴。

[0045] 图1为本发明实施例提供的社交网络中影响力最大化节点的探测方法的流程图；

[0046] 图2为本发明实施例提供的社交网络中影响力最大化节点的探测方法中单个种子节点的三个局部结构连接示意图；

[0047] 图3为图2中a所示一阶邻居和二阶邻居中被选择为种子节点的示意图；

[0048] 图4为本发明实施例提供的社交网络中影响力最大化节点的探测系统的结构示意图。

具体实施方式

[0049] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。

[0050] 如图1所示，为本发明实施例中，提出的一种社交网络中影响力最大化节点的探测方法，包括以下步骤：

[0051] 步骤S1、获取社交网络所给定的网络模型；

[0052] 具体过程为，一个社交网络可以被描述为一个无向图，用网络模型G(V,E)来表示；其中，V表示社交网络中的节点，代表网络中的用户；E表示社交网络中的边，代表用户之间
的关系，比如家人，朋友等。

[0053] 每个节点有两种初始状态，即激活和未激活，只有处于激活状态的节点才对它指向的节点具有影响力，当一个节点被另一个节点成功影响时，就称此节点的状态为激活状
态，节点只能从未激活状态变为激活状态，该过程不可逆。

[0054] 步骤S2、遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；

[0055] 具体过程为，影响力的传播离不开传播模型，社交网络影响扩散的传播模型中，最常见的有独立级联模型(IC Model)、线性阈值模型(LT Model)和带权级联模型(WC 
Model)。

[0056] 在本发明中采用独立级联模型，该独立级联模型(IC Model)是一种概率模型，节点u和节点v之间的边上有一个概率值pu,v； 表示节点u激活节点v的概率；概率越
大，则节点v被节点u激活的可能性就越大。因此，基于独立级联模型，在社交网络中给定每
条边的传播概率为p，则近似去计算节点在两阶范围内的影响力期望值。

[0057] 在图2(a)中，节点1的影响力期望值为1+4p+8p2；图2(b)中，节点1的影响力期望值2 4 2 4
约等于1+4p+8p‑4p ；在图2(c)中，节点1的影响力期望值为1+4p+8p‑6p。因为传播概率p
4
较小，p项可以忽略不计，因此在以上三个例子中节点1的影响力期望值都可以近似为1+4p
2
+8p。

[0058] 因此，遍历网络模型G(V,E)中所有节点，根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：

[0059]

[0060] 其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时
节点u激活节点v的概率。

[0061] 步骤S3、以节点的影响力传播期望值为指标，依次将所有节点对应地放入初始为空的大顶堆中；

[0062] 具体过程为，从大到小的预定排列方式，对所有节点计算所得的影响力传播期望值进行排序，根据排序后的顺序，依次将所有节点对应的放入初始为空的堆 中，即种
子节点集合。此时，堆顶节点为影响力传播期望最大的节点。当然，也可以按照从小到大的
排列方式或其它方式。

[0063] 步骤S4、从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

[0064] 具体过程为，当弹出堆顶节点时，根据公式(2)，更新节点的所有邻居节点的影响力传播期望值：

[0065] e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p2   (2)；

[0066] 其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻
居节点v的二阶邻居中被选择成为种子节点的个数。

[0067] 基于图2，av为图3中a所示的灰色区域节点集合的大小，bv为图3中b所示的最上方灰色区域节点集合的大小。

[0068] 步骤S5、计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这些节点作为影响力最大化种
子节点集合输出。

[0069] 具体过程为，首先，根据公式(3)，计算各节点各自与所有邻居节点之间的相似性；

[0070]

[0071] 其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

[0072] 其次，设定一个全局的相似性的预设阈值θ，检查节点u的所有邻居节点，如果邻居节点v的相似性超过预设阈值θ，说明该节点u的传播范围重合度较大，给邻居节点v设置标
记，表示在后续种子节点的选择过程中，不再考虑该节点，即在堆中删除，直至算法结束，得
到S中节点有k个，则说明已经找到k个种子节点为影响力最大化节点并输出。

[0073] 如图4所示，为本发明实施例中，提供的一种社交网络中影响力最大化节点的探测系统，包括：

[0074] 社交网络模型获取单元110，用于获取社交网络所给定的网络模型；

[0075] 节点影响力传播期望值计算单元120，用于遍历所述网络模型中所有节点，计算出各节点在二阶邻居范围内的影响力传播期望值；

[0076] 节点集合排序单元130，用于以节点的影响力传播期望值为指标，依次将所有节点对应的放入初始为空的大顶堆中；

[0077] 邻居节点影响力传播期望值更新单元140，用于从堆顶弹出影响力期望值最大的节点，并更新该节点所有邻居节点的影响力期望值；

[0078] 影响力最大化节点输出单元150，用于计算该节点和所有邻居节点的相似性，在大顶堆中将相似性不大于预设阈值的邻居节点进行重新插入操作，直至堆中弹出k个节点，这
些节点作为影响力最大化种子节点集合输出。

[0079] 其中，根据公式(1)，计算每个节点在二阶邻居范围内的影响力传播期望值：

[0080]

[0081] 其中，e(u)表示节点u在二阶邻居范围内的影响力传播期望值；du表示节点u的度；N(u)表示节点u的一阶邻居节点集合；p表示在社交网络影响扩散的独立级联模型中传播时
节点u激活节点v的概率；

[0082] 其中，根据公式(2)，更新节点的所有邻居节点的影响力传播期望值：

[0083] e(v)＝1+(dv‑2tv‑(dv‑tv)tvp)p+((av‑bv)·(1‑tvp))·p2   (2)；

[0084] 其中，e(v)表示节点u的邻居节点v的影响力传播期望值；dv表示邻居节点v的度；tv表示邻居节点v的一阶邻居中被选择为种子节点的个数；av表示二阶邻居的个数；bv表示邻
居节点v的二阶邻居中被选择成为种子节点的个数。

[0085] 其中，根据公式(3)，计算各节点各自与所有邻居节点之间的相似性；

[0086]

[0087] 其中，sim(u,v)表示节点u和邻居节点v的相似性；Nv(v)为N(v)∪{v}，表示邻居节点v的邻居节点集；Nu(u)为N(u)∪{u}，表示节点u的邻居节点集；∩表示交集；∪表示并集。

[0088] 实施本发明实施例，具有如下有益效果：

[0089] 本发明将二阶邻居范围评估节点的影响力计算和节点期望值折减计算相结合，并在网络中引入节点相似性概念，用于减少影响力范围重叠的问题，同时利用网络中节点的
局部信息评估节点的重要程度，不仅计算复杂性低且效率高，找到的种子节点集合传播范
围广，还能解决影响力覆盖范围重叠的问题。

[0090] 值得注意的是，上述系统实施例中，所包括的各个单元只是按照功能逻辑进行划分的，但并不局限于上述的划分，只要能够实现相应的功能即可；另外，各功能单元的具体
名称也只是为了便于相互区分，并不用于限制本发明的保护范围。

[0091] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，所述的程序可以存储于一计算机可读取存储介质中，
所述的存储介质，如ROM/RAM、磁盘、光盘等。

[0092] 以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。