- 必威体育下载

姓名
邮箱
手机号码
标题
留言内容
验证码

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.

Keywords:

Authors and contacts

Corresponding author:Li Xin,287998116@qq.com

FullText HTML: translate this paragraph

References

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]

Cited By

DownLoad: Full-Size Img PowerPoint

辅助算法二	联合概率算法
输入	时间t, 节点u以及对于u的序号集W
输出	联合概率${{{f}}_{{t}}}\left( {{{{u}}_{{W}}}} \right)$
1.	ifW只含一个元素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)$

DownLoad: CSV

递推算法	求种子节点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}}}$

DownLoad: CSV

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]

[1]	Li Jiang, Liu Ying, Wang Wei, Zhou Tao.Identifying influential nodes in spreading process in higher-order networks. Acta Physica Sinica, 2024, 73(4): 048901.doi:10.7498/aps.73.20231416
[2]	Yang Li, Song Yu-Rong, Li Yin-Wei.Network structure optimization algorithm for information propagation considering edge clustering and diffusion characteristics. Acta Physica Sinica, 2018, 67(19): 190502.doi:10.7498/aps.67.20180395
[3]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Hou Lü-Lin.An improved evaluating method of node spreading influence in complex network based on information spreading probability. Acta Physica Sinica, 2017, 66(20): 208901.doi:10.7498/aps.66.208901
[4]	Xiao Yun-Peng, Li Song-Yang, Liu Yan-Bing.An information diffusion dynamic model based on social influence and mean-field theory. Acta Physica Sinica, 2017, 66(3): 030501.doi:10.7498/aps.66.030501
[5]	Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie.An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901.doi:10.7498/aps.65.168901
[6]	Wu Yue, Du Ya-Jun, Chen Xiao-Liang, Li Xian-Yong.Newly exposed conflicting news based network opinion reversal. Acta Physica Sinica, 2016, 65(3): 030502.doi:10.7498/aps.65.030502
[7]	Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya.Evaluating influential spreaders in complex networks by extension of degree. Acta Physica Sinica, 2015, 64(8): 088901.doi:10.7498/aps.64.088901
[8]	Wang Jin-Long, Liu Fang-Ai, Zhu Zhen-Fang.An information spreading model based on relative weight in social network. Acta Physica Sinica, 2015, 64(5): 050501.doi:10.7498/aps.64.050501
[9]	Wang Xiao-Juan, Song Mei, Guo Shi-Ze, Yang Zi-Long.Information spreading in correlated microblog reposting network based on directed percolation theory. Acta Physica Sinica, 2015, 64(4): 044502.doi:10.7498/aps.64.044502
[10]	Hu Qing-Cheng, Zhang Yong, Xu Xin-Hui, Xing Chun-Xiao, Chen Chi, Chen Xin-Hua.A new approach for influence maximization in complex networks. Acta Physica Sinica, 2015, 64(19): 190101.doi:10.7498/aps.64.190101
[11]	Liu Shu-Xin, Ji Xin-Sheng, Liu Cai-Xia, Guo Hong.A complex network evolution model for network growth promoted by information transmission. Acta Physica Sinica, 2014, 63(15): 158902.doi:10.7498/aps.63.158902
[12]	Huang Fei-Hu, Peng Jian, Ning Li-Miao.Opinion evolution model of social network based on information entropy. Acta Physica Sinica, 2014, 63(16): 160501.doi:10.7498/aps.63.160501
[13]	Wang Chao, Liu Cheng-Yuan, Hu Yuan-Ping, Liu Zhi-Hong, Ma Jian-Feng.Stability of information spreading over social network. Acta Physica Sinica, 2014, 63(18): 180501.doi:10.7498/aps.63.180501
[14]	Hu Qing-Cheng, Yin Yan-Shen, Ma Peng-Fei, Gao Yang, Zhang Yong, Xing Chun-Xiao.A new approach to identify influential spreaders in complex networks. Acta Physica Sinica, 2013, 62(14): 140101.doi:10.7498/aps.62.140101
[15]	Li Yong-Jun, Liu Zun, Yu Hui.Advisor-advisee relationship identification based on maximum entropy model. Acta Physica Sinica, 2013, 62(16): 168902.doi:10.7498/aps.62.168902
[16]	Zhao Jia, Yu Li, Li Jing-Ru.Node influence calculation mechanism based on Bayesian and semiring algebraic model in social networks. Acta Physica Sinica, 2013, 62(13): 130201.doi:10.7498/aps.62.130201
[17]	Yuan Wei-Guo, Liu Yun, Cheng Jun-Jun, Xiong Fei.Empirical analysis of microblog centrality and spread influence based on Bi-directional connection. Acta Physica Sinica, 2013, 62(3): 038901.doi:10.7498/aps.62.038901
[18]	Xiong Xi, Hu Yong.Research on the dynamics of opinion spread based on social network services. Acta Physica Sinica, 2012, 61(15): 150509.doi:10.7498/aps.61.150509
[19]	Zhang Yan-Chao, Liu Yun, Zhang Hai-Feng, Cheng Hui, Xiong Fei.The research of information dissemination model on online social network. Acta Physica Sinica, 2011, 60(5): 050501.doi:10.7498/aps.60.050501
[20]	Li Ming-Jie, Wu Ye, Liu Wei-Qing, Xiao Jing-Hua.Short message spreading in complex networks and longevity of short message. Acta Physica Sinica, 2009, 58(8): 5251-5258.doi:10.7498/aps.58.5251

Catalog

Vol. 69, Issue 2 - 2020-01-20

Metrics

Abstract views:6763
PDF Downloads:95
Cited By:0

Search

Article