有限步传播范围期望指标判别节点传播影响力

李鑫; 赵城利; 刘阳洋

doi:10.7498/aps.69.20191313

有限步传播范围期望指标判别节点传播影响力

国防科技大学文理学院, 长沙　410073

作者简介: 287998116@qq.com .

通讯作者: E-mail: 287998116@qq.com;

中图分类号: 89.70.Cf, 89.75.Fb

Distinguishing node propagation influence by expected index of finite step propagation range

College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China

Corresponding author: E-mail: 287998116@qq.com;

MSC: 89.70.Cf, 89.75.Fb

摘要: 在线社交网络逐渐成为人们不可或缺的重要工具, 识别网络中具有高影响力的节点作为初始传播源, 在社会感知与谣言控制等方面具有重要意义. 本文基于独立级联模型, 给出了一个描述有限步传播范围期望的指标—传播度, 并设计了一种高效的递推算法. 该指标在局部拓扑结构信息的基础上融合了传播概率对影响力进行刻画, 能够较好地反映单个节点的传播影响力. 对于多传播源影响力极大化问题, 本文提出了一种基于传播度的启发式算法—传播度折扣算法, 使得多个传播源的联合影响力最大. 最后, 将上述方法应用到三个真实网络中, 与经典指标和方法相比, 该方法不需要知道网络的全局结构信息, 而是充分了利用网络的局部结构信息, 可以较快地筛选出高传播影响力的传播源.
- 社交网络 /
- 影响力度量 /
- 影响力极大化 /
- 信息传播
Abstract: On-line social networks have gradually become an indispensable tool for people. Identifying nodes with high influence in the network as an initial source of communication is of great significance in social perception and rumor control. According to the independent cascade model, in this paper we present an index describing the finite step propagation range expectation as the degree of propagation, and design an efficient recursive algorithm. Based on the local topology information, the index combines the propagation probability to characterize the influence, which can better reflect the propagation influence of a single node. For a single propagation source influence ordering problem, the node degree of propagation and propagation capability are better consistent with each other. And the propagation degree can well describe the propagation influence of nodes under different networks and propagation probabilities. For maximizing the multi-propagation source influence, in this paper we propose a propagation-based heuristic algorithm which is called propagation discount algorithm. This algorithm makes the joint influence of multiple propagation sources maximized. Finally, in this paper we apply the above method to three real networks, showing better effects than the classic indicators and methods. The algorithm has three advantages. First, the expected value of the final propagation range of each node in the small network can be accurately calculated. Second, the degree of propagation fully considers the local topology of the node and belongs to a locality indicator. Third, the indicator combines the effect of propagation probability and yields good outcomes under different networks and propagation probabilities.
- social network /
- influence measurement /
- influence maximization /
- information dissemination .

图 1 一个简单网络例子　(a)网络图; (b)图(a)对应的传播树

Figure 1. A simple network example: (a) The network diagram; (b) the corresponding propagation tree of (a).

下载: 全尺寸图片幻灯片

图 2 (a)不同仿真次数下的近似传播期望值和传播度随时间的变化; (b)不同仿真次数的近似传播期望值与传播度的方差变化

Figure 2. (a) Approximate propagation expectation and the degree of propagation over time for different simulation times; (b) variance of the approximate propagation expectation and the degree of propagation of different simulation times.

下载: 全尺寸图片幻灯片

图 3 图1中的网络各节点4阶传播度(归一化)随传播概率变化

Figure 3. Changes of the 4th degree of propagation (normali-zed) of network node in Fig. 1 with the propagation pro-bability.

下载: 全尺寸图片幻灯片

图 4 基于传播度的节点影响力极大化算法流程图

Figure 4. Flow chart of node influence maximization algorithm based on propagation degree.

下载: 全尺寸图片幻灯片

图 5 (a)−(c) 分别反映了Deezer网络随机挑选若干节点的传播能力与度, 二阶传播度, 三阶传播度的关系, 其中β = 0.06; (d)−(f) 分别反映了Deezer网络随机挑选若干节点全局传播概率(参见文献[12])与度, 二阶传播度, 三阶传播度的对应情况, 其中β = 0.12(这里通过仿真实验不难发现该网络的渗流阈值介于0.06和0.12之间)

Figure 5. (a)−(c): Respectively reflects the relationship between the propagation capacity and degree, second-order propagation, and third-order propagation of several nodes randomly selected by the Deezer network, where β = 0.06; (d)−(f): Respectively reflects the global propagation probability of randomly selected nodes by the Deezer network (see reference[12]) Correspondence with degrees, second-order propagation, and third-order propagation, where β = 0.12 (here, it is not difficult to find through the simulation experiments that the percolation threshold of the network is between 0.06 and 0.12)

下载: 全尺寸图片幻灯片

图 6 不同传播概率下度, 二阶、三阶传播度与仿真传播能力的kendall’s tau系数

Figure 6. Kendall’s tau coefficient for different propagation probabilities, second-order, third-order propagation and simulation propagation ability.

下载: 全尺寸图片幻灯片

图 7 (a)在Email-Enron网络中, 传播概率为0.02的情况下二阶传播度和全局传播概率p的关系; (b)各指标在不同概率下与传播能力的kendall’s tau系数

Figure 7. (a) The relationship between the second-order propagation degree and the global propagation probability p in the case of the Email-Enron network with a propagation probability of 0.02; (b) the kendall's tau coefficient of each indicator with different propagation rates and propagation capabilities.

下载: 全尺寸图片幻灯片

图 8 (a)在Facebook网络中, 传播概率为0.09的情况下二阶传播度和全局传播概率p的关系; (b)各指标在不同概率下与传播能力的kendall’s tau系数

Figure 8. (a) The relationship between the second-order propagation degree and the global propagation probability p in the case of a Facebook network with a propagation probability of 0.09; (b) the kendall's tau coefficient of each indicator with different propagation rates and propagation capabilities.

下载: 全尺寸图片幻灯片

图 9 在Deezer网络中(a)不同算法下传播范围随所选种子节点数量的变化和(b)不同算法下全局传播概率随种子节点数量的变化, 其中候选节点为度为6, 7, 8的9792个节点

Figure 9. In the Deezer network, (a) the variation of the propagation range with the number of selected seed nodes under different algorithms; (b) the variation of the global propagation probability with the number of seed nodes under different algorithms. The candidate nodes are 9792 nodes with a degree of 6, 7 and 8.

下载: 全尺寸图片幻灯片

图 10 (a), (b)和(c), (d)分别比较了Email-Enron, Facebook网络在不同算法下所选种子节点的传播性能

Figure 10. (a), (b), and (c), (d), respectively, compare the propagation performance of Email-Enron, the selected seed node of the Facebook network under different algorithms.

下载: 全尺寸图片幻灯片

表 1 联合概率算法

Table 1. Joint probability algorithm

辅助算法二	联合概率算法
输入	时间t, 节点u以及对于u的序号集W
输出	联合概率${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right)$
1.	if W只含一个元素 then
2.	找到该节点的双亲节点${{{v}}_{\left( {{i}} \right)}}$
3.	${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right) = {{{f}}_{{{t}} - {{1}}}}\left( {{{{v}}_{\left( {{i}} \right)}}} \right) \times {{\beta }} \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$
4.	else
5.	找到传播树种${{{P}}_{{t}}}$代序号集为W的u节点, 记其双亲节点为${{{v}}_{{1}}}, {{{v}}_{{2}}}, \cdots , {{{v}}_{{l}}}$, 出现次数为$ m_1, $$ m_2, \cdots , m_l$, 这些路径对于双亲节点的序号集分别为${{{X}}_{{1}}}, {{{X}}_{{2}}}, \cdots , {{{X}}_{{l}}}$, 对于节点u的序号集分别为${{{Y}}_{{1}}}, {{{Y}}_{{2}}}, \cdots {{{Y}}_{{l}}}$.
6.	for ${{j}} = 0 \to {{l}}$ do
7.	${{{f}}_{{t}}}\left( {{{{u}}_{{{{Y}}_{{j}}}}}} \right) = {{F}}\left( {{{t}} - {{1}}, {{{v}}_{{j}}}, {{{X}}_{{j}}}} \right) \times {{\beta }}$
8.	end for
9.	${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right) = \left[ {{{1}} - \mathop \prod \nolimits_{{{j}} = {{1}}}^{{l}} \left( {{{1}} - {{{f}}_{{t}}}\left( {{{{u}}_{{{{Y}}_{{j}}}}}} \right)} \right)} \right] \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$
10.	end if
11.	return ${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right)$

下载: 导出CSV

表 2 种子节点s阶传播度的算法流程伪代码

Table 2. Pseudocode of the algorithm flow for s order progpagation of the seed node.

递推算法	求种子节点s阶传播度
输入	seed, ${{\beta }}$, s
输出	${{{d}}_{{s}}}$
1.	${\rm Tree }_{s} = {\rm FTree }(\rm seed)$ %获取节点${{seed}}$的s阶传播树
2.	赋初值${ { {p} }_{ {0} } }\left( { { {\rm seed} } } \right) = { { {f} }_{ {0} } }\left( { { {\rm seed} } } \right) = { {1} }$, 其他情况${{{p}}_{{t}}}\left( {{u}} \right) = {{{f}}_{{t}}}\left( {{u}} \right) = {{0}}$
3.	for ${{t}} = {{1}} \to {{s}}$ do
4.	for ${{{u}}_{{y}}} \in {{{P}}_{{t}}}$ do %遍历传播树中${{{P}}_{{t}}}$代的个体
5.	获得${{{u}}_{{y}}}$的双亲节点${{{v}}_{{x}}}$ %表示节点u所在传播树层中第x个u节点
6.	${{{f}}_{{t}}}\left( {{{{u}}_{{y}}}} \right) = {{{f}}_{{{t}} - {{1}}}}\left( {{{{v}}_{{x}}}} \right) \times {{\beta }} \times \left( {{{1}} - {{{p}}_{{{t}} - {{1}}}}\left( {{u}} \right)} \right)$
7.	end for
8.	for ${{u}} \in {{{P}}_{{t}}}$ do
9.	获得u的序号集W %指${{{P}}_{{t}}}$代节点u出现次序构成的集合
10.	计算联合概率${{{f}}_{{t}}}\left( {{u}} \right) = {{F}}\left( {{{t}}, {{u}}, {{W}}} \right)$
11.	end for
12.	for $u \in {\rm Tree}_{s}$ do
13.	${{{p}}_{{t}}}\left( {{u}} \right) = {{{p}}_{{{t}} - 1}}\left( {{u}} \right) + {{{f}}_{{t}}}\left( {{u}} \right)$
14.	end for
15.	end for
16.	${ { {d} }_{ {s} } }\left( { { \rm{seed} } } \right) = \mathop \sum \nolimits_{ {u} } { { {p} }_{ {s} } }\left( { {u} } \right)$
17.	return ${{{d}}_{{s}}}$

下载: 导出CSV

[1]	Fershtman M 1997 Soc. Networks 19 193
[2]	Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[3]	Freeman L C 1977 Sociometry 40 35 doi: 10.2307/3033543
[4]	Bavelas A 1950 J. Acoust. Soc. Am. 22 725 doi: 10.1121/1.1906679
[5]	Dabbousi B O, Rodriguez-Viejo J, Mikulec F V, Heine J R, Mattoussi H, Ober R, Jensen K F, Bawendi M G 1997 J. Phys. Chem. B 101 9463
[6]	闵磊, 刘智, 唐向阳 2015 物理学报 64 088901 Min L, Liu Z, Tang X Y 2015 Acta Phys. Sin. 64 088901
[7]	Domingos P, Richardson M 2001 Proceedings of KDD'01 ACM SIG KDD International Conference on Knowledge Discovery and Data Mining San Francisco, CA, USA, August 26−29, 2001 p57
[8]	Kempe D, Kleinberg J, Tardos E 2003 Proc. 9th ACM SIGKDD Intl. Conf. On Knowledge Discovery and Data Mining New Washington, DC, USA, August 24−27, 2003 p137
[9]	Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N 2007 Proc. 13 th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining USA, August 24−27, 2007 p420
[10]	Chen W, Wang Y, Yang S 2009 Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge discovery and data mining Paris, France, June 28−July 1, 2009 p199
[11]	Sheikhahmadi A, Nematbakhsh M A, Shokrollahi A 2015 Physica A 436 833
[12]	Kimura M, Saito K 2006 Knowledge-Based Intelligent Information and Engineering Systems: 10th international conference Bournemouth, UK, October 9−11, 2006 p259
[13]	Chen W, Wang C, Wang Y 2010 Proc. 16th ACM SIGKDD Intl. Conf. on Knowledge discovery and data mining WashingtonDC, USA, July 25−28, 2010 p1029
[14]	Wang Y, Cong G, Song G 2010 Proc. 16th ACM SIGKDD Intl. Conf. on Knowledge discovery and mining Washington DC, USA, July 25−28, 2010 p1039
[15]	Li D, Xu Z M, Chakraborty N 2014 PloS One 9 e102199 doi: 10.1371/journal.pone.0102199
[16]	Hu Y Q, Ji S G, Jin Y L, Feng L, Stanley H E, Havlin S 2018 PNAS 115 7468 doi: 10.1073/pnas.1710547115
[17]	Lancichinetti A, Fortunato S 2009 Phys. Rev. E 80 056117
[18]	Leskovec J, Lang K, Dasgupta A, Mahoney M W 2009 Internet Mathematics 6 29 doi: 10.1080/15427951.2009.10129177
[19]	Lapata M 2006 Comput. Linguist. 32 471 doi: 10.1162/coli.2006.32.4.471
[20]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888 doi: 10.1038/nphys1746

图( 10) 表( 2)

计量

文章访问数: 87
HTML全文浏览数: 87
PDF下载数: 0
施引文献: 0

全文HTML

1. 引　言

随着网络科学的快速发展, 节点的传播影响力越来越受到人们的关注. 在信息的传播过程中, 具有高传播影响力的节点可以加速信息的传播, 这对于宣传产品, 推送广告等方面具有重要的作用. 因此, 该领域的一个核心问题就是如何选择网络中的若干节点作为传播源, 使其传播影响力极大化, 又具体可分为单个传播源影响力排序问题和多个传播源影响力极大化问题(需要考虑不同传播源之间影响力的重叠).

对于网络中节点影响力排序问题, 最简单高效的方法是度中心性^[1], 它反映节点的邻居数, 例如微博中拥有粉丝数多的大V用户就具有很高的传播影响力. 后来, Chen等^[2]又给出了一个局部中心性指标, 该指标考虑了二阶邻居数, 但这两个指标在反映节点传播影响力时没有考虑传播概率的影响, 也无法充分反映节点的局部拓扑结构. 对于全局性的指标有介数中心性^[3]、接近度中心性^[4]、K核^[5]、特征向量中心性^[6]等. 而对于多源影响力极大化(influence maximization)问题, 最初由Domingos和Richardson^[7]提出, 后被Kempe等^[8]证明该问题是NP-Hard难问题. 一种最简单的选取策略就是选出某指标值最大的若干节点作为传播源, 但这种算法选出的各传播者之间可能会有较大影响力重叠. 因此, Leskovec等^[9]采用贪心算法来寻求初始传播集, 但这种算法的复杂度较大不适用于大型网络. Chen等^[10]提出两种改进的贪心算法新贪心算法和最大贪心算法, 这两种改进算法均比贪心算法的算法复杂度要低, 但在大型网络中仍具有较高算法复杂度. 后来, 一些特殊的启发式算法被提出, 度折扣算法^[11]就是其中一种高效的启发式算法, 它是对探索式算法的一种优化策略的改进, 具有较高的实用价值, 其基本思想为当节点的邻居节点已被选为传播源时, 会对该节点的度指标产生折扣效应, 从而达到了去重叠的目的. 再后来, Kimura等^[12]利用分解极大连通子图来寻找最优传播源, 基于此, 又提出了利用最大影响路径的方法^[13], 这种方法虽然大大降低了了算法复杂度, 但限制了只能在最短路径上传播. Wang等^[14]提出了一种结合动态规划的算法选择最优传播源, 提升了算法效率, Li等^[15]考虑积极消极影响力, 提出了一种新的模型, 尽管这些算法效率都很高, 但很容易陷入局部最优的情况, 效果不及贪心算法.

在线社交网络具有规模庞大, 结构复杂的特点, 运用节点的局部信息指标描述节点的传播影响力更具现实意义. 但目前的局部性指标均不能够很好的刻画节点的局部拓扑结构, 因此本文基于独立级联模型, 提出一种描述节点有限步传播范围期望的指标—传播度. 对于网络中的任一节点作为传播源, 我们充分分析信息在局部网络中的传播路径, 设计了一种精确的递推算法计算有限步后传播范围的期望值, 之后通过真实网络数据集仿真验证了该指标与节点传播影响力具有更高一致性. 另一方面, 在考虑多传播源影响力极大化问题时, 选择的各传播源影响力会发生重叠, 因此基于传播度提出了一种启发式算法—传播度折扣算法, 同样通过真实网络数据集仿真验证了该算法相较于经典方法具有更好的效果.

本文的主要贡献在以下几个方面:

1)提出了描述网络节点传播能力的指标—传播度, 用于描述节点在有限步后能够传播到网络节点范围的期望值. 并设计了计算该指标的迭代算法, 可以高效的计算节点的任意阶(步数)的传播度.

2)相较于传统指标, 传播度指标考虑了传播概率对节点传播的影响. 对于小型网络, 可以直接利用该算法计算节点的最终传播期望; 对于大型网络, 可利用低阶传播度刻画节点的传播影响力, 充分利用了节点的局部拓扑结构信息.

3)对于多传播源问题, 基于传播度指标提出了一种传播度折扣的算法, 能有有效地去除不同初始传播源间的影响力重叠, 相较于原有的度折扣算法有更好的选择效果.

5. 总　结

在充分考虑节点局部拓扑结构信息的基础上, 提出了有限步传播范围期望的指标—传播度, 并设计了高效精确的递推计算方法. 在此基础上, 将该指标用于单源影响力排序问题, 实验证明, 该指标与节点的传播能力具有更高的一致性. 另外, 对于多源影响力极大化问题, 本文基于传播度的概念, 设计了一种启发式算法—传播度折扣算法, 相较于经典的算法, 具有更好的筛选效果.

给出了一种精确计算有限步传播范围期望的递推算法, 事实上, 当传播到达一定步数后, 即当传播步数较大时, 节点被传播的概率往往很小, 因此, 如何设置局部的递推终止条件, 引入较小的误差, 可以进一步优化算法, 计算更高阶的传播度, 这一问题有待进一步研究.

参考文献 (20)

有限步传播范围期望指标判别节点传播影响力

作者简介: 287998116@qq.com .

通讯作者: E-mail: 287998116@qq.com;

Distinguishing node propagation influence by expected index of finite step propagation range

Corresponding author: E-mail: 287998116@qq.com;

计量

有限步传播范围期望指标判别节点传播影响力

通讯作者: E-mail: 287998116@qq.com;

作者简介: 287998116@qq.com
国防科技大学文理学院, 长沙　410073

English Abstract

Distinguishing node propagation influence by expected index of finite step propagation range

Corresponding author: E-mail: 287998116@qq.com;

全文HTML

2.1. 辅助算法一

2.2. 传播度的计算公式及辅助算法二

2.2.1. 传播度的计算公式

2.2.2. 辅助算法二

2.3. 传播度递推求解

2.4. 仿真验证

3.1. 单个节点的影响力排序

3.2. 传播度折扣解决多源影响力极大化问题

3.3. 模型总述

4.1. 数据集

4.2. 单源影响力排序效果

4.3. 多源影响力极大化效果

目录

有限步传播范围期望指标判别节点传播影响力

作者简介: 287998116@qq.com .

通讯作者: E-mail: 287998116@qq.com;

Distinguishing node propagation influence by expected index of finite step propagation range

Corresponding author: E-mail: 287998116@qq.com;

计量

出版历程

有限步传播范围期望指标判别节点传播影响力

通讯作者: E-mail: 287998116@qq.com;

作者简介: 287998116@qq.com 国防科技大学文理学院, 长沙 410073

English Abstract

Distinguishing node propagation influence by expected index of finite step propagation range

Corresponding author: E-mail: 287998116@qq.com;

全文HTML

2.1. 辅助算法一

2.2. 传播度的计算公式及辅助算法二

2.2.1. 传播度的计算公式

2.2.2. 辅助算法二

2.3. 传播度递推求解

2.4. 仿真验证

3.1. 单个节点的影响力排序

3.2. 传播度折扣解决多源影响力极大化问题

3.3. 模型总述

4.1. 数据集

4.2. 单源影响力排序效果

4.3. 多源影响力极大化效果

目录

作者简介: 287998116@qq.com
国防科技大学文理学院, 长沙　410073