基于反向影响采样的积极影响力最大化

doi:10.11772/j.issn.1001-9081.2021071185

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (8): 2609-2616.DOI: 10.11772/j.issn.1001-9081.2021071185

所属专题：前沿与综合应用

基于反向影响采样的积极影响力最大化

杨书新(), 许景峰

江西理工大学信息工程学院，江西赣州 341000

收稿日期:2021-07-08 修回日期:2021-09-13 接受日期:2021-09-22 发布日期:2021-09-30 出版日期:2022-08-10
通讯作者: 杨书新
作者简介:杨书新（1978—），男，江西九江人，副教授，博士，CCF会员，主要研究方向：社交网络分析、生物信息学；
许景峰（1996—），男，江西赣州人，硕士研究生，主要研究方向：社交网络分析、数据挖掘。
基金资助:
江西省教育厅科学技术研究项目(GJJ170518)

Positive influence maximization based on reverse influence sampling

Shuxin YANG(), Jingfeng XU

School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000，China

Received:2021-07-08 Revised:2021-09-13 Accepted:2021-09-22 Online:2021-09-30 Published:2022-08-10
Contact: Shuxin YANG
About author:YANG Shuxin， born in 1978， Ph. D.， associate professor. His research interests include social network analysis， bioinformatics.
XU Jingfeng， born in 1996， M. S. candidate. His research interests include social network analysis， data mining.
Supported by:
Scientific and Technology Research Project of Education Department of Jiangxi Province(GJJ170518)

摘要/Abstract

摘要：

影响力最大化问题现有的工作主要集中在无符号网络上，忽略了网络中个体之间存在的敌对关系。针对符号网络中的积极影响力最大化问题，在极性相关的独立级联（IC-P）模型的基础上提出一种符号网络中基于反向影响采样（RIS-S）的算法以最大化积极影响力。首先，在生成反向可达集的阶段考虑了节点的极性关系，以适用于符号网络；其次，为了提高反向可达集的有效性，限制了采样的遍历深度。在三个真实的符号网络数据集上比较了RIS-S、IMM（Influence Maximization via Martingales）、POD（Positive Out-Degree）和Effective Degree等算法的积极影响力范围和运行时间，以验证所提算法的有效性。实验结果表明，RIS-S算法所选的种子更加准确，能获得更广的积极影响力范围，并且该算法的运行时间比同类型算法IMM更短，可以认为RIS-S算法能够解决符号网络中的积极影响力最大化问题。

关键词: 影响力最大化, 符号网络, 独立级联模型, 反向影响采样算法, 病毒式营销

Abstract:

Existing works on influence maximization mainly focus on unsigned network and neglect the hostile relationship between the individuals in the network. Aiming at the positive influence maximization problem in signed network， based on Polarity-related Independent Cascade （IC-P） model， a Reverse Influence Sampling in Signed network （RIS-S） algorithm was proposed to maximize positive influence. Firstly， in order to apply to the signed network， the polarity relationships of nodes in the stage of generating reverse reachable sets were considered. Secondly， to improve the effectiveness of reverse reachable sets， the traversal depth of sampling was limited. Finally， the positive influence ranges and running times of RIS-S， Influence Maximization via Martingales （IMM）， Positive Out-Degree （POD） and Effective Degree algorithm were compared on three real signed network data sets to verify the effectiveness of the proposed algorithm. Experimental results show that RIS-S algorithm can obtain wider positive influence range by selecting more accurate seeds， and the proposed algorithm has the running time less than the same type algorithm IMM.It can be thought that RIS-S algorithm can solve the problem of positive influence maximization in signed network.

Key words: influence maximization, signed network, independent cascade model, Reverse Influence Sampling (RIS) algorithm, viral marketing

中图分类号:

TP393.02

杨书新, 许景峰. 基于反向影响采样的积极影响力最大化[J]. 计算机应用, 2022, 42(8): 2609-2616.

Shuxin YANG, Jingfeng XU. Positive influence maximization based on reverse influence sampling[J]. Journal of Computer Applications, 2022, 42(8): 2609-2616.

图/表 12

图1 符号网络

Fig. 1 Signed network

表1 常用符号表示

Tab. 1 Representation of frequently used symbols

符号	描述	符号	描述
G_s	符号网络图	I⁺	积极影响力范围
V	节点集合	RRS	反向可达集
E	有向边集合	depth	采样深度
P	影响概率	seed	种子集合
S	节点的极性关系	ε	近似比参数
C（u）	节点u的状态	l	错误概率参数
g	采样图	Pr	正节点占比率
k	种子集的节点个数

图2 IC-P模型传播示例

Fig. 2 Propagation examples of IC-P model

图3 采样图及反向可达集示例

Fig. 3 Examples of sampling graph and reverse reachable set

表2 实验数据集相关参数

Tab. 2 Relevant parameters of experimental datasets

数据集	\|V\|	\|E\|	d	E^-/E⁺
Bitcoinotc	5 881	35 592	4	0.100
Slashdot	77 350	516 575	11	0.232
Epinions	131 828	841 372	14	0.147

图4 Bitcoinotc数据集上的积极影响力范围

Fig. 4 Positive influence range on Bitcoinotc dataset

图5 Slashdot数据集上的积极影响力范围

Fig. 5 Positive influence range on Slashdot dataset

图6 Epinions数据集上的积极影响力范围

Fig. 6 Positive influence range on Epinions dataset

图7 Bitcoinotc数据集上的运行时间

Fig. 7 Running time on Bitcoinotc dataset

图8 Slashdot数据集上的运行时间

Fig. 8 Running time on Slashdot dataset

图9 Epinions数据集上的运行时间

Fig. 9 Running time on Epinions dataset

表3 k=50正节点占比率对比

Tab. 3 Comparison of positive ratio at k=50

算法	Bitcoinotc	Slashdot	Epinions
Random	0.69	0.52	0.45
IMM	0.74	0.64	0.57
Effective Degree	0.75	0.72	0.62
POD	0.76	0.73	0.63
RIS-S	0.77	0.77	0.69

参考文献 21

1	DOMINGOS P， RICHARDSON M. Mining the network value of customers ［C］// Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2001： 57-66. 10.1145/502512.502525
2	程苏琦，沈华伟，张国清，等.符号网络研究综述［J］.软件学报， 2014， 25（1）： 1-15.
	CHENG S Q， SHEN H W， ZHANG G Q， et al. Survey of signed network research［J］. Journal of Software， 2014， 25（1）： 1-15.
3	KEMPE D， KLEINBERG J， TARDOS É. Maximizing the spread of influence through a social network ［C］// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 137-146. 10.1145/956750.956769
4	LESKOVEC J， KRAUSE A， GUESTRIN C， et al. Cost-effective outbreak detection in networks ［C］// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2007： 420-429. 10.1145/1281192.1281239
5	GOYAL A， LU W， LAKSHMANAN L V S. CELF++： optimizing the greedy algorithm for influence maximization in social networks ［C］// Proceedings of the 20th International Conference Companion on World Wide Web. New York： ACM， 2011： 47-48. 10.1145/1963192.1963217
6	CHEN W， WANG Y J， YANG S Y. Efficient influence maximization in social networks ［C］// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 199-208. 10.1145/1557019.1557047
7	BORGS C， BRAUTBAR M， CHAYES J， et al. Maximizing social influence in nearly optimal time ［C］// Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia， PA： Society for Industrial and Applied Mathematics， 2014： 946-957. 10.1137/1.9781611973402.70
8	TANG Y Z， XIAO X K， SHI Y C. Influence maximization： near-optimal time complexity meets practical efficiency ［C］// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2014： 75-86. 10.1145/2588555.2593670
9	TANG Y Z， SHI Y C， XIAO X K. Influence maximization in near-linear time： a martingale approach ［C］// Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2015： 1539-1554. 10.1145/2723372.2723734
10	LI D， XU Z M， CHAKRABORTY N， et al. Polarity related influence maximization in signed social networks［J］. PLoS ONE， 2014， 9（7）： No.e102199. 10.1371/journal.pone.0102199
11	LI D， WANG C H， ZHANG S P， et al. Positive influence maximization in signed social networks based on simulated annealing［J］. Neurocomputing， 2017， 260： 69-78. 10.1016/j.neucom.2017.03.003
12	WANG H H， YANG Q， FANG L， et al. Maximizing positive influence in signed social networks ［C］// Proceedings of the 2015 International Conference on Cloud Computing and Security， LNCS 9483. Cham： Springer， 2015： 356-367.
13	HOSSEINI-POZVEH M， ZAMANIFAR K， NAGHSH-NILCHI A R， et al. Maximizing the spread of positive influence in signed social networks［J］. Intelligent Data Analysis， 2016， 20（1）： 199-218. 10.3233/ida-150801
14	JU W J， CHEN L， LI B， et al. A new algorithm for positive influence maximization in signed networks［J］. Information Sciences， 2020， 512： 1571-1591. 10.1016/j.ins.2019.10.061
15	QIU L Q， ZHANG S， YU J F. Positive influence maximization in the signed social networks considering polarity relationship and propagation probability［J］. International Journal of Software Engineering and Knowledge Engineering， 2021， 31（2）： 249-267. 10.1142/s0218194021500078
16	NGUYEN H T， THAI M T， DINH T N. Stop-and-stare： optimal sampling algorithms for viral marketing in billion-scale networks ［C］// Proceedings of the 2016 International Conference on Management of Data. New York： ACM， 2016： 695-710. 10.1145/2882903.2915207
17	杨书新，梁文，朱凯丽.基于三级邻居的复杂网络节点影响力度量方法［J］.电子与信息学报， 2020， 42（5）： 1140-1148. 10.11999/JEIT190440
	YANG S X， LIANG W， ZHU K L. Measurement of node influence based on three-level neighbor in complex networks［J］. Journal of Electronics and Information Technology， 2020， 42（5）： 1140-1148. 10.11999/JEIT190440
18	ŞIMŞEK A. A new greedy algorithm for influence maximization on signed social networks［J］. Gazi Journal of Engineering Sciences， 2019， 5（3）： 250-257. 10.30855/gmbd.2019.03.06
19	LIU W， CHEN X， JEON B， et al. Influence maximization on signed networks under independent cascade model［J］. Applied Intelligence， 2019， 49（3）： 912-928. 10.1007/s10489-018-1303-2
20	SRIVASTAVA A， CHELMIS C， PRASANNA V K. Social influence computation and maximization in signed networks with competing cascades ［C］// Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York： ACM， 2015： 41-48. 10.1145/2808797.2809304
21	GARIMELLA K， GIONIS A， PAROTSIDIS N， et al. Balancing information exposure in social networks ［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2017： 4666-4674.

[1]	杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1155-1161.
[2]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[3]	李美子, 米一菲, 张倩, 张波. 社交网络中基于K核分解的意见领袖识别算法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 26-35.
[4]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.
[5]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[6]	盛俊, 顾沈胜, 陈崚. 基于隐空间映射的带符号网络上的顶点分类[J]. 计算机应用, 2019, 39(5): 1411-1415.
[7]	孙子力, 彭舰, 仝博. 社会网络中基于社群衰减的影响力最大化算法[J]. 计算机应用, 2019, 39(3): 834-838.
[8]	李阅志, 祝园园, 钟鸣. 基于k-核过滤的社交网络影响最大化算法[J]. 计算机应用, 2018, 38(2): 464-470.
[9]	李敏佳, 许国艳, 朱帅, 张网娟. 基于结构洞和度折扣的影响力最大化算法[J]. 计算机应用, 2018, 38(12): 3419-3424.
[10]	赵晓晖, 刘方爱. 基于文化算法的符号网络全局不平衡度计算[J]. 计算机应用, 2016, 36(12): 3341-3346.
[11]	吴凯季新生郭进时刘彩霞. 基于微博网络的影响力最大化算法[J]. 计算机应用, 2013, 33(08): 2091-2094.
[12]	孔令旗杨梦龙. 符号网络聚类算法FEC的改进[J]. 计算机应用, 2011, 31(05): 1395-1399.

基于反向影响采样的积极影响力最大化

Positive influence maximization based on reverse influence sampling

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 21

相关文章 12

编辑推荐

Metrics