Positive influence maximization based on reverse influence sampling

doi:10.11772/j.issn.1001-9081.2021071185

Abstract

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

摘要：

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

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

CLC Number:

TP393.02

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

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

Figures/Tables 12

Fig. 1 Signed network

Tab. 1 Representation of frequently used symbols

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

Fig. 2 Propagation examples of IC-P model

Fig. 3 Examples of sampling graph and reverse reachable set

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

Fig. 4 Positive influence range on Bitcoinotc dataset

Fig. 5 Positive influence range on Slashdot dataset

Fig. 6 Positive influence range on Epinions dataset

Fig. 7 Running time on Bitcoinotc dataset

Fig. 8 Running time on Slashdot dataset

Fig. 9 Running time on Epinions dataset

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

References 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]	Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG. Influence maximization algorithm based on node coverage and structural hole [J]. Journal of Computer Applications, 2022, 42(4): 1155-1161.
[2]	Qingqing WU, Lihua ZHOU, Xuanyi CUN, Guowang DU, Yiting JIANG. Influence maximization algorithm based on directed acyclic graph in heterogeneous information networks [J]. Journal of Computer Applications, 2022, 42(3): 895-903.
[3]	Meizi LI, Yifei MI, Qian ZHANG, Bo ZHANG. Opinion leader recognition algorithm based on K-core decomposition in social networks [J]. Journal of Computer Applications, 2022, 42(1): 26-35.
[4]	ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation [J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.
[5]	YANG Shuxin, LIANG Wen, ZHU Kaili. Reverse influence maximization algorithm in social networks [J]. Journal of Computer Applications, 2020, 40(7): 1944-1949.
[6]	ZHANG Xianli, TANG Jianxin, CAO Laicheng. Influence maximization algorithm based on reverse PageRank [J]. Journal of Computer Applications, 2020, 40(1): 96-102.
[7]	SHENG Jun, GU Shensheng, CHEN Ling. Node classification in signed networks based on latent space projection [J]. Journal of Computer Applications, 2019, 39(5): 1411-1415.
[8]	SUN Zili, PENG Jian, TONG Bo. Influence maximization algorithm on internal decay based on community structure in social network [J]. Journal of Computer Applications, 2019, 39(3): 834-838.
[9]	LI Yuezhi, ZHU Yuanyuan, ZHONG Ming. k-core filtered influence maximization algorithms in social networks [J]. Journal of Computer Applications, 2018, 38(2): 464-470.
[10]	LI Minjia, XU Guoyan, ZHU Shuai, ZHANG Wangjuan. Influence maximization algorithm based on structure hole and degree discount [J]. Journal of Computer Applications, 2018, 38(12): 3419-3424.
[11]	LIU Yuanying, GUO Jingfeng, WEI Lidong, HU Xinzhuan. Fast influence maximization algorithm in social network under budget control [J]. Journal of Computer Applications, 2017, 37(2): 367-372.
[12]	ZHAO Xiaohui, LIU Fang'ai. Computing global unbalanced degree of signed networks based on culture algorithm [J]. Journal of Computer Applications, 2016, 36(12): 3341-3346.
[13]	WU Kai JI Xinsheng GUO Jinshi LIU Caixia. Influence maximization algorithm for micro-blog network [J]. Journal of Computer Applications, 2013, 33(08): 2091-2094.
[14]	KONG Ling-qi YANG Meng-long. Improvement of clustering algorithm FEC for signed networks [J]. Journal of Computer Applications, 2011, 31(05): 1395-1399.