开放科学(资源服务)标志码(OSID)：

0 概述

随着智能移动设备的普及和5G网络的应用，社交网络发展迅速。影响力最大化问题作为社交网络分析领域的热点研究问题，旨在从社交网络中寻找k个最具影响力的节点，并最大化以这些节点作为种子节点的最终信息传播范围，被广泛应用于在线广告^[1-2]、病毒营销^[3]、专家发现^[4]、个性化推荐^[5]等任务。用户影响力度量是影响力最大化问题的核心。网络拓扑结构^[6]是影响力度量的重要依据。与网络拓扑结构相关的影响力度量指标可以分为全局性指标和局部性指标。介数中心性^[7]、接近中心性^[8]、离心中心性^[9]、流介数中心性^[10]、Katz中心性^[11]、连通介数中心性^[12]等都属于全局性指标。全局性指标需要依靠网络完整拓扑结构，在整个网络范围内计算节点影响力，因此时间复杂度很高。度中心性^[13]、半局部中心性^[14]、特征向量中心性^[15]等都属于局部性指标。局部性指标仅依据局部范围的拓扑信息计算节点的影响力，与全局性指标相比时间复杂度较低。然而，影响力传播具有三度分隔特性，即社交网络中相距三度是强连接，强连接可以引发行为，相距超过三度是弱连接，弱连接只能传递信息。节点有自环^[16]特性，拥有自环的节点比没有自环的节点自身活跃度更高，两个节点之间还可能存在多边，这些因素都与节点的影响力密切相关。现有的局部性指标往往忽略这些因素，导致对影响力的度量不够全面，从而影响信息的最终传播范围。

本文结合三度分隔原理^[17]，提出用节点在局部范围内的影响力近似其在全局范围内影响力的算法。根据网络拓扑结构构造生成图，依据生成图划分每个节点对应的局部域，根据节点在对应局部域内的影响力筛选候选种子节点。计算每个节点与种子集合的重叠比因子，并据此决定候选种子节点是否能成为种子节点。通过在真实数据集上的实验结果以验证本文算法的正确性和有效性。

1 相关知识 1.1 影响力最大化问题

社交网络可用有向图$ G=(V, E) $表示，其中，$ V $是节点集合且$ V= ${$ {v}_{1}, {v}_{2}, \cdots ，{v}_{n} $}，$ E $是边集合且$ E= ${（$ {v}_{i}, {v}_{j} $）$ |{v}_{i}, {v}_{j}\in V $}。（$ \forall {v}_{i} $）$ {v}_{i}\in V $，（$ \forall {v}_{j} $）$ {v}_{j}\in V $，如果$ {v}_{i} $对$ {v}_{j} $产生一次通信行为，则从$ {v}_{i} $到$ {v}_{j} $构成了一条有向边$ 〈{v}_{i}, {v}_{j}〉 $。

影响力最大化问题是从网络$ G=(V, E) $中找到一个大小为$ k $的节点集合$ S $，最大化以这$ k $个节点作为种子节点开始影响力传播后影响力的最终传播范围（即激活的节点数最多）。影响力最大化问题可表示如下：

$ S\leftarrow \mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}f\left({S}^{*}\right)\left\{{S}^{*}|{S}^{*}\in V, \left|{S}^{*}\right|=k\right\} $

(1)

其中：$ {S}^{*} $表示节点集合；$ f\left({S}^{*}\right) $表示影响力的传播范围。

1.2 影响力传播模型

线性阈值（Linear Threshold，LT）模型^[18-19]可以用来模拟影响力的传播过程。在LT模型中，节点只能处于激活状态或者非激活状态。激活状态的节点通过有向边试图激活处于非激活状态的邻居节点。对于非激活状态的节点，当所有激活状态的邻居节点对其影响力之和大于该节点的激活阈值时，该非激活节点就转为激活状态。当网络中不再有节点被激活（即由非激活状态转为激活状态）时，影响力的传播过程收敛。

图 1给出了根据LT模型模拟影响力传播的过程，其中，灰色圆表示激活节点，白色圆表示非激活节点，有向边上数字表示箭尾节点对箭首节点的影响力。节点$ {v}_{1} $、$ {v}_{2} $、$ {v}_{5} $和$ {v}_{6} $为种子节点，在传播开始时处于激活状态；其他节点则处于非激活状态。整个传播过程经过3轮迭代收敛。

2 影响力最大化算法

本文针对局部性度量指标构造生成图，根据影响力传播的三度分隔原理构建局部影响力度量模型，依据局部影响力度量模型设计基于局部域影响力的种子节点选择算法。

2.1 权重感知的生成图构造

边影响权重根据自环和多边属性计算。边权重反映了节点间的亲密程度，影响力的传播过程又受邻居间关系疏密的影响。因此，边影响权重的计算过程中应考虑自环和多边现象。

自环指的是一种特殊的环结构，这种环状结构只包含一个节点。社交网络中用户可能发起只有自己参与的社交活动，从而在对应的社交网络图中形成只有该节点参与的自环。自环多的节点活跃度较高，在信息传播过程中会主动地影响其他节点。本文引入自环因子度量自环对节点能力的影响。自环因子计算如下：

$ {R}_{{v}_{i}}=\sum \psi \left({v}_{i}\right) $

(2)

其中：$ {R}_{{v}_{i}} $表示节点$ {v}_{i} $的自环因子；$ \psi （{v}_{i}）\mathrm{表}\mathrm{示}\mathrm{节}\mathrm{点}{v}_{i} $每个自环的权重。在无权网络中，$ \psi （{v}_{i}） $默认为1，此时节点自环因子等于节点的自环个数。

多边指的是社交网络图中两个节点间有多条边存在。在社交网络中，两个节点间的一次互动会在社交网络图中对应的节点间产生一条边。当两个节点间有多次互动时，它们之间就会有多条边。然而，随着边数的增加，图的存储和遍历成本也会增加。在不影响图的存储和计算成本的前提下，本文引入多边因子，用以度量节点间存在的多边现象对信息传播过程的影响。多边因子随着两个节点间边的增多而增大。多边因子计算如下：

$ {M}_{{v}_{i}{v}_{j}} = \sum\limits_{i\ne j}\varphi ({v}_{i}, {v}_{j}) $

(3)

其中：$ {M}_{{v}_{i}{v}_{j}} $表示节点$ {v}_{i} $和$ {v}_{j} $的多边因子；$ \varphi ({v}_{i}, {v}_{j}) $表示$ {v}_{i} $到$ {v}_{j} $一条边的权重。在无权网络中，$ \varphi ({v}_{i}, {v}_{j}) $默认为1，此时节点多边因子等于两节点之间的边数。

结合自环因子和多边因子，本文引入边影响权重，描述节点间的影响力。

定义1   给定一条边（$ {v}_{i}, {v}_{j} $），$ {v}_{i} $对$ {v}_{j} $的影响力即为该边的边影响权重。边影响权重计算如下：

$ {\tau }_{{v}_{i}{v}_{j}}={M}_{{v}_{i}{v}_{j}}/\sum\limits_{{v}_{k}\in {N}_\text{in}^{D}\left({v}_{j}\right)}({M}_{{v}_{k}{v}_{j}}+{R}_{{v}_{j}}) $

(4)

其中：$ {N}_{\mathrm{i}\mathrm{n}}^{D}\left({v}_{j}\right) $是由出边直接指向$ {v}_{j} $的节点构成的集合。

根据自环因子、多边因子和边影响权重构造生成图，并且生成图是有向带权图。

2.2 局部域影响力度量

影响力的全局性度量指标往往从拓扑结构的整体出发对节点的影响力进行全面准确的衡量，但是却存在计算复杂度高的问题。根据影响力传播遵循的三度分隔原理^[17]，即节点的影响力在相距不超过三跳的邻居节点间传播时随着距离的增大而不断衰减，当传播距离超过三跳时几近消失。本文根据三度分隔特性，利用节点的影响力在特定的局部范围内的传播过程来近似其在全局范围内的传播过程。为了度量节点在特定局部范围内的影响力，引入最短距离、局部邻居以及局部域的概念，并结合局部域拓扑结构建立影响力度量模型。

定义2   节点间最短路径的长度即为节点间的最短距离。假设（$ \forall {v}_{i} $）$ {v}_{i}\in V $，（$ \forall {v}_{j} $）$ {v}_{j}\in V $，若$ {v}_{i} $到$ {v}_{j} $的最短路径为$ p({v}_{i}, {v}_{j}) $且$ p\left({v}_{i}, {v}_{j}\right)=〈{v}_{i}, {p}_{1}, {p}_{2}, \cdots , {p}_{m}, {v}_{j}〉 $，则节点$ {v}_{i} $到$ {v}_{j} $的最短距离$ {l}_{{v}_{i}{v}_{j}} $为$ (m+1) $。

定义3   给定节点$ {v}_{i} $，若$ {v}_{j} $是$ {v}_{i} $的可达节点且到$ {v}_{i} $的距离不大于$ D $，则称$ {v}_{j} $是$ {v}_{i} $的局部邻居。

定义4   给定节点及其局部邻居构成的节点集合以及这些节点间的边构成的边集合共同组成此节点的局部域，记为$ {A}_{\mathrm{L}} $。以节点$ {v}_{i} $为中心的局部域记为$ {A}_{\mathrm{L}}\left({v}_{i}\right) $，表示如下：

$ {A}_{\mathrm{L}}\left({v}_{i}\right)=\left(\tilde{V}, \tilde{E}\right) $

(5)

其中：$ \tilde{V}=\left\{{v}_{i}|{v}_{i}\bigcup {N}_{\mathrm{L}}（{v}_{i}）\right\}，{N}_{\mathrm{L}}（{v}_{i}）\mathrm{表}\mathrm{示}\mathrm{节}\mathrm{点}{v}_{i}\mathrm{的}\mathrm{局}\mathrm{部}\mathrm{邻}\mathrm{居} $ $ \mathrm{集}；\tilde{E}= $$ \left\{〈{v}_{i}, {v}_{j}, {\tau }_{{v}_{i}{v}_{j}}〉|{v}_{i}\in \tilde{V}, {v}_{j}\in \tilde{V}\right\} $。

定义5   对于给定节点，其局部域影响力为以此节点为中心的局部域拓扑结构所决定的节点传播信息的能力，记为$ \mathrm{C}\mathrm{r} $。（$ \forall {v}_{i} $）$ {v}_{i}\in V $，$ \mathrm{C}\mathrm{r}\left({v}_{i}\right) $计算如下：

$ \mathrm{C}\mathrm{r}（{v}_{i}）=\sum\limits_{{v}_{j}\in {N}_\text{L}\left({v}_{i}\right)}{2}^{-({l}_{{v}_{i}{v}_{j}}-\left.1\right)}{\tau }_{{v}_{i}{v}_{j}} $

(6)

其中：$ {l}_{{v}_{i}{v}_{j}} $是节点$ {v}_{i} $到节点$ {v}_{j} $的最短距离；$ {\tau }_{{v}_{i}{v}_{j}} $是节点$ {v}_{i} $到节点$ {v}_{j} $的最短路径中最后一条边的边影响权重。

以8节点网络中节点$ {v}_{1} $为例说明局部域影响力的计算过程，如图 2所示，其中圆圈内字母及其数字下标表示节点，有向边上的数值代表两节点间的边影响权重。假设$ D $=3，节点$ {v}_{1} $的局部域由节点$ {v}_{1} $与其局部邻居节点{$ {v}_{2} $，$ {v}_{3} $，$ {v}_{4} $，$ {v}_{5} $}以及它们之间的边构成。

2.3 影响力重叠检测

节点之间可能存在影响力重叠现象，导致多个节点的共同影响力小于各节点影响力之和。为了保证影响力的传播范围最大，在选择种子节点时应考虑节点之间可能存在的影响力重叠现象。权衡影响力重叠检测成本和消除影响力重叠后的收益，本文允许影响力重叠，但是应避免影响力过度重叠，并利用式（7）判定给定节点间是否存在影响力重叠。

$ \mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{a}\mathrm{p}\left({v}_{i}, {v}_{j}\right)=\left\{\begin{array}{l}1, \frac{\left|{N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{i}\right)\bigcap {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{j}\right)\right|}{\left|{N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{i}\right)\bigcup {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{j}\right)\right|} > \eta \\ 0, \mathrm{其}\mathrm{他}\end{array}\right. $

(7)

其中：$ \eta $表示过度重叠判定阈值；$ {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{i}\right) $和$ {N}_{\mathrm{o}\mathrm{u}\mathrm{t}}^{D}\left({v}_{j}\right) $分别表示$ {v}_{i} $和$ {v}_{j} $的出边直接连接的节点构成的集合。在式（7）的基础上，本文定义了重叠比因子，判定一个集合中节点间影响力重叠的程度。

定义6   重叠比因子为给定集合中影响力过度重叠的节点在集合中所占的比例，记为$ \omega $。给定集合$ C\subseteq V $，该集合的重叠比因子计算如下：

$ {\omega }_{C} = \frac{1}{\left|C\right|}\sum\limits_{i\ne j}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{a}\mathrm{p}\left({v}_{i}, {v}_{j}\right) $

(8)

2.4 算法描述

首先根据$ \mathrm{C}\mathrm{r} $值构建候选种子节点列表，并将该列表中第一个节点作为种子加入种子集合。然后依次从候选种子节点列表中选择一个节点，并计算该节点加入种子集合后该种子集合的重叠比因子。若该重叠比因子小于预定义的重叠比阈值，则将此节点加入种子节点集合，否则不能将此节点加入种子集合。重复上述过程，直至选出足够数量的种子节点。算法1给出了基于局部域的影响力最大化算法的伪代码。

算法1   基于局部域的影响力最大化算法

输入  $ G{'}=(V{'}, E{'}) $，$ k $，$ \eta $，$ \theta $//$ \theta $为激活阈值

输出  $ S $

1.初始化：$ \mathrm{S}\leftarrow \mathrm{\varnothing } $

2.CrList ← node list with descending order of Cr values

3.S+ = $ \mathrm{C}\mathrm{r}\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}(0 $）

4.for $ \mathrm{i}\leftarrow 1 $ to（$ \left|\mathrm{C}\mathrm{r}\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}\right|-1 $）do

5.$ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}\leftarrow \mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $

6.ω_S ← 0

7.for every s in S do

8.if $ {\mathrm{l}}_{\mathrm{s}, \mathrm{C}\mathrm{r}\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}\left(\mathrm{i}\right)}\ge $θ then

9.$ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}\leftarrow \mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e} $

10.else

11.$ {\mathtt{ω }}_{\mathrm{S}} $+ = $ \mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{a}\mathrm{p}\left(\mathrm{s}, \mathrm{C}\mathrm{r}\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}\left(\mathrm{i}\right)\right)∕ $ k

12.if $ {\mathtt{ω }}_{\mathrm{S}}\ge \mathtt{η } $ then

13.$ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}\leftarrow \mathrm{f}\mathrm{a}\mathrm{l}\mathrm{s}\mathrm{e} $

14.break

15.end if

16.end if

17.end for

18.if $ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}==\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e} $ then

19.$ \mathrm{S} $+ = $ \mathrm{C}\mathrm{r}\mathrm{L}\mathrm{i}\mathrm{s}\mathrm{t}\left(\mathrm{i}\right) $

20.end if

21.if $ \left|\mathrm{S}\right|== $ k then

22.break

23.end if

24.end for

25.return

对列表中的每个候选种子节点按顺序挑选，在最坏情况下需要遍历所有候选种子节点。对于每个遍历到的候选种子节点，均要根据式（8）检测是否与某种子节点存在影响力过度重叠。给定种子节点数$ k $，判定某个候选种子节点是否与某个种子节点存在过度重叠的时间复杂度为$ O\left(kd\right) $，其中$ d $为节点平均出度。基于以上分析，从节点集合$ V $中选出$ k $个种子节点的时间复杂度在最坏情况下为$ O\left(\left|V\right|kd\right) $，也可表示为$ O\left(\left|E\right|k\right) $。除种子集合$ S $外，本文算法对于每个节点还存储了$ \mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g} $和$ {\omega }_{S} $两个变量，且最多为列表中所有节点均设置，因此算法的空间复杂度在最坏情况下为$ O\left(\left|V\right|\right) $。

3 实验与结果分析

实验选取5种对比算法，通过在6个不同规模的真实数据集上比较算法的影响力传播范围、算法运行时间等指标来验证本文算法的正确性和有效性。

3.1 数据集与实验环境

表 1给出了选用的数据集信息，其中，$ \left|V\right| $表示节点总数，$ \left|E\right| $表示边总数，d为节点平均出度。所有数据集均来自斯坦福大学的大型网络数据集（http://snap.stanford.edu/data/）。

实验选用MaxDegree算法、PageRank算法、ICGW算法、Closeness算法和IDD1算法5种对比算法。这些对比算法分别采用最大度策略^[13]、PageRank方法^[20]、约束贪婪方式下的影响力节点识别方法^[21]、Closeness方法^[8]和改进的度折扣启发式策略^[22]选择种子节点。所有算法均用Python实现，在相同的Windows平台上运行。该平台采用Intel Core i5 1.80 GHz处理器，配置8 GB内存空间。

实验采用的评价指标分别为影响力传播范围、算法运行时间和占用的内存空间大小。影响力传播范围用激活的节点数表示，该值越大越好，算法运行时间和内存空间占用则越小越好。

3.2 结果分析

在本文算法中，参数$ \eta $、$ \theta $和$ D $分别表示过度重叠判定阈值、线性阈值模型下的激活阈值和局部域范围。在本次实验中，取值分别为0.2、0.4和3。该部分给出的所有结果都是相关算法独立运行1 000次计算的平均结果。

图 3给出了各算法的影响力传播范围，其中k表示种子节点数。由图 3可知：本文算法在所有数据集上的种子节点的影响力平均传播范围最大，其次是IDD1算法和ICGW算法；本文算法相比于MaxDegree算法、PageRank算法和Closeness算法所选种子节点的影响力平均传播范围较小；本文算法在Cora数据集上表现最好，所选种子节点影响力平均传播范围分别是IDD1算法和ICGW算法的1.77倍和1.47倍；本文算法在Escorts-Dynamic数据集上表现最差，但影响力传播范围仍是IDD1算法和ICGW算法的1.04倍和1.03倍。

在种子节点数相同的情况下，本文算法的传播结果始终优于IDD1算法和ICGW算法。这是由于本文算法具备影响力重叠控制能力，因此在选择相同的种子时，它对节点的组合影响力更加敏感。在所有数据集上，本文算法的影响力传播范围在种子节点数从10到50阶段几乎都呈线性增长，这表明了本文算法识别高影响力节点群体的能力更强。

减少种子节点选择所消耗的时间是本文算法设计的另一个重要目标。图 4给出了在6个数据集上各种算法选取$ k $个种子节点所用的平均运行时间。总体来看，MaxDegree算法平均运行时间最短，其次是本文算法、IDD1算法、PageRank算法和ICGW算法，Closeness算法平均运行时间最长。由于IDD1算法和ICGW算法的影响力传播范围和本文算法最为接近，而其他3种算法的影响力传播范围则远小于本文算法，失去了比较意义，因此在评价算法的时间和空间性能时只与IDD1算法和ICGW算法比较。

由图 4可知：本文算法在P2p-Gnutella04数据集上表现最好，运行时间分别是IDD1算法和ICGW算法的7%和8%；本文算法在Cora数据集上表现最差，但运行时间仍仅是ICGW算法的17%；本文算法在Wiki-Vote数据集和Cora数据集上的运行时间多于IDD1算法，但在其他数据集上的运行时间都少于IDD1算法。因此，从所有数据集来看，本文算法要略优于IDD1算法。

通过实验评估本文算法的空间复杂度。算法在执行过程中占用的内存空间越多，其空间复杂度越高，反之亦然。在实验过程中，随机选择$ k= $50的运行过程，比较各算法的内存占用情况。表 2给出了在$ k= $50时各算法在不同数据集上运行时占用的内存空间。由表 2可知：在所有数据集上运行时，本文算法所占用的内存空间均小于ICGW算法；除了Fb-Forum数据集和P2p-Gnutella04数据集之外，本文算法的内存空间占用都低于IDD1算法。从整体来看，本文算法的内存空间占用情况要优于IDD1算法。

4 结束语

针对度量用户影响力的全局性和局部性度量指标各自存在的局限性，本文利用节点在局部域内的影响力近似其在全局范围内的影响力，提出一种基于局部域的影响力最大化算法。构建以节点为中心的局部域影响力度量模型，依据影响力度量模型筛选候选种子节点集合。利用重叠比因子刻画候选种子节点与种子节点集合间的重叠程度，并根据重叠比因子决定是否将此候选种子节点选作种子节点。实验结果验证了该算法的正确性与有效性。下一步可将本文算法扩展应用于动态社交网络，利用其能高效准确选取高影响力种子节点的优势，设计并实现高影响力节点集合的增量式更新方法。