带符号在线社交网络中净正面交互信息量最大化问题研究

doi:10.16381/j.cnki.issn1003-207x.2022.0173

摘要/Abstract

摘要：

在线社交网络已经融入了人们的生活，网络已经成为了传播信息的理想平台，然而商家的推荐信息的传播效果却不佳。因此，研究信息发布策略，让正面信息得到更好的宣传具有重大意义。本文通过最大化用户之间净正面交互信息量，研究带符号在线社交网络中节点选择策略。给定带符号在线社交网络 $G = (V, E, X, P, C)$ ，任意一条边 $e ∈ E$ 上有其传播符号 $x ∈ X$ 、传播概率 $p ∈ P$ ，和信息量交互强度 $c ∈ C$ 。在线社交网络中净正面信息量最大化问题就是从节点集 $V$ 中选取包含 $k$ 个节点的种子集 $S$ 与其赋值函数 $F : S → {+, -}$ ，使得传播结束时网络中的正面信息量减去负面信息量的差值最大。首先，证明了该问题是NP-困难的，其目标函数的计算是#P-困难的。其次，证明了由于信息的组合效应，导致该问题既不是次模的也不是超模的。然后，根据传播特性提出了传播路径的构造方法和路径收益的近似计算方法，从而将问题构造为单调次模的正面信息量函数的求解。再次，设计了一种高效的最大覆盖贪婪算法来解决带符号网络中净正面信息量最大化问题。最后，在真实网络中进行实验，验证了所提出的算法优于其他方法，发现了传播人数与传播效果并不对等这一现象。

关键词: 带符号在线社交网络, 正面信息交互量, 影响力最大化

Abstract:

Online social networks have been integrated into people’s lives， and the Internet has become an ideal platform for disseminating information. Internet Word of Mouth Marketing （IWOM） is becoming increasingly attractive to companies. However， the dissemination of some promotional information can generate a large number of negative comments， damaging reputation and long-term profits. Therefore， it is of great significance to study information dissemination strategies so that beneficial information can be better promoted. The node selection strategy is investigated to maximize the amount of net positive information diffusion among individuals in signed online social networks. Given a signed online social network $G = (V, E, X, P, C)$ ， each edge $e ∈ E$ has an edge symbol $x ∈ X$ and a propagation probability $p ∈ P$ . $C$ is the intensity of information interaction between individuals. The information propagation model is defined as the Signed Independent Cascade （SIC） model in signed networks. The problem of net positive information maximizing is to select a seed set containing $k$ nodes from the node-set $V$ and its assignment function $F : S → {+, -}$ so that the amount of positive information minus the amount of negative information is maximum at the end of the spread. The problem is shown to be NP-hard and its objective function computation is #P-hard. Second， it is demonstrated that the problem is neither submodular nor supermodular due to the combined effect of information. Then， according to the propagation characteristics， the propagation path and its approximate calculation method are proposed. The problem is further constructed to solve a positive monotone submodular function. Third， an efficient maximum coverage greedy algorithm is designed to maximize the amount of net positive information. Finally， experiments conducted on real networks to verify that the proposed algorithm is superior to other methods and show that information diffusion is not equal to the dissemination effect.

Key words: signed online social networks, positive information, influence maximization

中图分类号:

G203

戴佳伶, 朱建明, 王国庆, 黄钧. 带符号在线社交网络中净正面交互信息量最大化问题研究[J]. 中国管理科学, 2025, 33(3): 139-150.

Jialing Dai, Jianming Zhu, Guoqing Wang, Jun Huang. Net Positive Information Diffusion Activity Maximizing in Signed Online Social Networks[J]. Chinese Journal of Management Science, 2025, 33(3): 139-150.

图/表 6

图 1

图 2

图 3

表 1

图 4

图 5

参考文献 35

1	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 2015， Paris， France， August 25-28， ACM， 2015： 41-48.
2	Gopinath S， Thomas J S， Krishnamurthi L. Investigating the relationship between the content of online word of mouth， advertising， and brand performance［J］. Marketing Science， 2014， 33（2）： 241-258.
3	Sweeney J C， Soutar G N， Mazzarol T. Word of mouth： Measuring the power of individual messages［J］. European Journal of Marketing， 2012，46（1/2）：237-357.
4	Ye Q， Law R， Gu B， et al. The influence of user-generated content on traveler behavior： An empirical investigation on the effects of e-word-of-mouth to hotel online bookings［J］. Computers in Human behavior， 2011， 27（2）： 634-639.
5	闫强，孟跃. 在线评论的感知有用性影响因素——基于在线影评的实证研究［J］. 中国管理科学， 2013，21（S1）： 126-131.
	Yan Q， Meng Y. Factors affecting the perceived usefulness of online reviews：An empirical study based on online film reviews［J］. Chinese Journal of Management Science， 2013，21（S1）： 126-131.
6	Kempe D， Kleinberg J， Tardos É. Maximizing the spread of influence through a social network［C］//Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining， Washington， USA， August 24-27， ACM， 2003： 137-146.
7	Borgs C， Brautbar M， Chayes J， et al. Maximizing social influence in nearly optimal time［C］//Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms， Portland， Oregon， January 5-7 ， Society for Industrial and Applied Mathematics， 2014： 946-957.
8	Baumeister R F， Bratslavsky E， Finkenauer C， et al. Bad is stronger than good［J］. Review of General Psychology， 2001， 5（4）： 323-370.
9	Rozin P， Royzman E B. Negativity bias， negativity dominance， and contagion［J］. Personality and Social Psychology Review， 2001， 5（4）： 296-320.
10	Taylor S E. Asymmetrical effects of positive and negative events： The mobilization-minimization hypothesis［J］. Psychological Bulletin， 1991， 110（1）： 67-85.
11	Dai J L， Zhu J M， Wang G Q. Opinion influence maximization problem in online social networks based on group polarization effect［J］. Information Sciences， 2022， 609： 195-214.
12	Wang Z F， Yu Y， Jian P， et al. Activity maximization by effective information diffusion in social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（11）： 2374-2387.
13	倪培昆，朱建明，王国庆. 在线社交网络虚假信息交互量最小化的边阻断策略研究［J］. 中国管理科学， 2021， 29（9）： 188-200.
	Ni P K， Zhu J M， Wang G Q. Disinformation diffusion activity minimization by edge blocking in online social networks［J］. Chinese Journal of Management Science， 2021， 29（9）： 188-200.
14	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， San Jose， USA， August 12-15， ACM， 2007： 420-429.
15	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， Hyderabad， India， March 28-April 1， ACM， 2011： 47-48.
16	Zhu J M， Ni P K， Wang G Q， et al. Misinformation influence minimization problem based on group disbanded in social networks［J］. Information Sciences， 2021， 572： 1-15.
17	Domingos P， Richardson M. Mining the network value of customers［C］//Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining， San Francisco， California， August 26-29， ACM， 2001： 57-66.
18	Zhang H Y， Dinh T N， Thai M T. Maximizing the spread of positive influence in online social networks［C］//Proceedings of 2013 IEEE 33rd International Conference on Distributed Computing Systems， Philadelphia， USA， July 8-11， IEEE， 2013： 317-326.
19	Zhu J M， Ni P K， Tong G， et al. Influence maximization problem with echo chamber effect in social network［J］. IEEE Transactions on Computational Social Systems， 2021， 8（5）： 1163-1171.
20	Chen W， Collins A， Cummings R， et al. Influence maximization in social networks when negative opinions may emerge and propagate［C］//Proceedings of the 2011 siam international conference on data mining， Mesa， USA， April 28-30 ， SIAM， 2011： 379-390.
21	Nazemian A， Taghiyareh F. Influence maximization in independent cascade model with positive and negative word of mouth［C］//Proceedings of the 6th International Symposium on Telecommunications （IST）， Tehran， Iran， November 6-8， IEEE， 2012： 854-860.
22	Li D， Xu Z M， Chakraborty N， et al. Polarity related influence maximization in signed social networks［J］. PLoS ONE， 2014， 9（7）： e102199.
23	Bhagat S， Goyal A， Lakshmanan L V S. Maximizing product adoption in social networks［C］//Proceedings of the fifth ACM international conference on Web search and data mining， Seattle， USA， February 8-12， ACM， 2012： 603-612.
24	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.
25	Sheng J， Chen L， Chen Y X， et al. Positive influence maximization in signed social networks under independent cascade model［J］. Soft Computing， 2020， 24（19）： 14287-14303.
26	Li S S， Zhu Y Q， Li D Y， et al. Influence maximization in social networks with user attitude modification［C］//Proceedings of 2014 IEEE International Conference on Communications， Sydney， Australia， June 10-14， IEEE， 2014： 3913-3918.
27	Heider F. Attitudes and cognitive organization［J］. The Journal of Psychology Interdisciplinary and Applied， 1946， 21（1）： 107-112.
28	Kumar S， Spezzano F， Subrahmanian V S， et al. Edge weight prediction in weighted signed networks［C］//Proceedings of 2016 IEEE 16th International Conference on Data Mining， Barcelona， Spain， December 12-15， IEEE， 2016： 221-230.
29	Richardson M， Agrawal R， Domingos P. Trust management for the semantic web［C］//Proceedings of the 2nd international semantic web conference， Sanibel Island， USA， October 20-23， Springer， 2003： 351-368.
30	Leskovec J， Huttenlocher D， Kleinberg J. Signed networks in social media［C］//Proceedings of the SIGCHI conference on human factors in computing systems， Atlanta， USA， April 10-15， ACM， 2010： 1361-1370.
31	Chen W， Lakshmanan L， Ca Stillo C. Information and influence propagation in social networks［J］. Synthesis Lectures on Data Management， 2013， 5（4）： 1-177.
32	Brin S， Page L. The anatomy of a large-scale hypertextual web search engine［J］. Computer networks and ISDN systems， 1998， 30（1-7）： 107-117.
33	Cheng S Q， Shen H W， Huang J M， et al. Imrank： Influence maximization via finding self-consistent ranking［C］//Proceedings of the 37th international ACM SIGIR conference on research and development in information retrieval， Gold Coast， Australia， July 6-11， ACM， 2014： 475-484.
34	Wu H C， Shang J X， Zhou S B， et al. Laim： A linear time iterative approach for efficient influence maximization in large-scale networks［J］. IEEE Access， 2018 （6）： 44221-44234.
35	Valiant L G. The complexity of enumeration and reliability problems［J］. SIAM Journal on Computing， 1979， 8（3）： 410-421.

网络	#节点	#边	MOD	POS	NEG
Bitcion	3783	24186	398	22650	15365
Epinions	25148	105061	291	74060	31001
Slashdot	77350	516575	2532	396378	120197