面向不確定性影響源的社會網(wǎng)絡(luò)影響力傳播抑制方法
doi: 10.11999/JEIT161360
基金項目:
國家自然科學(xué)基金(61562091, 61472345), 云南省應(yīng)用基礎(chǔ)研究計劃，(2014FA023, 2016FB110), 云南大學(xué)中青年骨干教師培養(yǎng)計劃項目, 云南大學(xué)青年英才培育計劃(XT412003), 云南省軟件工程重點實驗室開放項目(2012SE303, 2012SE205)
Uncertain Influence Sources Oriented Influence Blocking Maximization in Social Networks
Funds:
The National Natural Science Foundation of China (61562091, 61472345), The Natural Science Foundation of Yunnan Province (2014FA023, 2016FB110), The Foundation of Backbone Teacher Development of Yunnan University, The Program for Excellent Young Talents of Yunnan University (XT412003), The Open Foundation of Key Laboratory of Software Engineering of Yunnan Province (2012SE303, 2012SE205)
-
摘要: 社會網(wǎng)絡(luò)中影響力傳播的有效抑制是社會網(wǎng)絡(luò)影響力傳播機制研究所關(guān)注的問題之一。該文針對未知影響傳播源，或傳播源信息具有不確定性的情況，提出面向不確定性影響源的影響力傳播抑制問題。首先，為有效提高抑制算法的執(zhí)行效率，討論競爭線性閾值傳播模型下影響源傳播能力的近似估計方法，進而提出有限影響源情況下，期望抑制效果最大化的抑制種子集挖掘算法。其次，對于大尺寸不確定性影響源的情況，考慮算法運行效率和抑制效果之間的有效折中，提出基于抽樣平均近似的期望抑制效果最大化的抑制種子集挖掘算法。最后，在真實的社會網(wǎng)絡(luò)數(shù)據(jù)集上，通過實驗測試驗證了所提出方法的有效性。
-
關(guān)鍵詞:
- 社會網(wǎng)絡(luò) /
- 不確定性影響源 /
- 影響力傳播抑制 /
- 競爭線性閾值模型 /
- 抽樣平均近似
Abstract: Influence blocking maximization is currently a focused issue in the research area of social networks. This paper considers the issue of influence blocking maximization with uncertain negative influence sources. First, in order to increase efficiency of blocking seeds mining algorithms, the approximate estimation method of influence propagation of negative seeds under the competitive linear threshold model is discussed. Based on the estimation, a blocking seeds mining algorithm for finite uncertain negatively influence sources is proposed to maximize expected influence blocking utility. Second, for the case of huge amount of negatively influence sources with uncertainty, a blocking seeds mining algorithm based on the sampling average approximation approach is proposed to balance the tradeoffs between scalability and effectiveness of the influence blocking maximization. Finally, experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms. -
WU Xingdong, LI Yi, and LI Lei. Influence analysis of online social networks[J]. Chinese Journal of Computers, 2014, 37(4): 735-752. doi : 10.3724/SP.J.1016.2014.00735. 吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析[J]. 計算機學(xué)報, 2014, 37(4): 735-752. doi: 10.3724/SP.J.1016.2014.00735. 劉業(yè)政, 李玲菲, 姜元春. 社會化營銷績效最大化問題及其擴展研究綜述[J]. 電子與信息學(xué)報, 2016, 38(9): 2130-2140. doi: 10.11999/JEIT160517. LIU Yezheng, LI Lingfei, and JIANG Yuanchun. Review of social marketing performance maximization problem and its extension[J]. Journal of Electronics Information Technology, 2016, 38(9): 2130-2140. doi: 10.11999/JEIT 160517. KEMPE D, KLEINBERG J, and 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, New York, 2003: 137-146. doi: 10.1145/956750.956769. 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, 2007: 420-429. doi: 10.1145/1281192.1281239. CHEN Wei, WANG Chi, and WANG Yajun. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2010: 1029-1038. doi: 10.1145 /1835804.1835934. LU Wei, CHEN Wei, and LAKSHMANAN L V S. From competition to complementarity: Comparative influence diffusion and maximization[J]. Proceedings of the VLDB Endowment, 2015, 9(2): 60-71. doi: 10.14778/2850578. 2850581. SONG Guojie, ZHOU Xiabing, WANG Yu, et al. Influence maximization on large-scale mobile social network: A divide- and-conquer method[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(5): 1379-1392. doi: 10.1109/ TPDS.2014.2320515. 許宇光, 潘驚治, 謝惠揚. 基于最小點覆蓋和反饋點集的社交網(wǎng)絡(luò)影響最大化算法[J]. 電子與信息學(xué)報, 2016, 38(4): 795-802. doi: 10.11999/JEIT160019. XU Yuguang, PAN Jingzhi, and XIE Huiyang. Minimum vertex covering and feedback vertex set-based algorithm for influence maximization in social network[J]. Journal of Electronics Information Technology, 2016, 38(4): 795-802. doi: 10.11999/JEIT160019. HE Xinran, SONG Guojie, CHEN Wei, et al. Influence blocking maximization in social networks under the competitive linear threshold model[C]. 9th VLDB Workshop on Secure Data Management, Istanbul, 2012: 463-474. doi: 10.1137/1.9781611972825.40. NGUYEN N P, YAN G, THAI M T, et al. Containment of misinformation spread in online social networks[C] Proceedings of the 3rd Annual ACM Web Science Conference, Evanston, Illinois, 2012: 213-222. doi: 10.1145/2380718. 2380746. BUDAK C, AGRAWAL D, and EL ABBADI A. Limiting the spread of misinformation in social networks[C] Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India, 2011: 665-674. doi: 10.1145/ 1963405.1963499. TSAI J, NGUYEN T H, WELLER N, et al. Game-theoretic target selection in contagion-based domains[J]. The Computer Journal, 2014, 57(6): 893-905. doi: 10.1093/ comjnl/bxt094. WU Hong, LIU Weiyi, YUE Kun, et al. Maximizing the spread of competitive influence in a social network oriented to viral marketing[C]. Proceedings of the 16th International Conference Web-Age Information Management, Qingdao, China, 2015: 516-519. doi: 10.1007/978-3-319-21042-1_53. LIU Weiyi, YUE Kun, WU Hong, et al. Containment of competitive influence spread in social networks[J]. Knowledge-Based Systems, 2016, 109: 266-275. doi: 10.1016/ j.knosys.2016.07.008. 李勁, 岳昆, 張德海, 等. 社會網(wǎng)絡(luò)中影響力傳播的魯棒抑制方法[J]. 計算機研究與發(fā)展, 2016, 53(3): 601-610. doi: 10.7544/issn1000-1239.2016.20148341. LI Jin, YUE Kun, ZHANG Dehai, et al. Robust influence blocking maximization in social networks[J]. Journal of Computer Research and Development, 2016, 53(3): 601-610. doi: 10.7544/issn1000-1239.2016.20148341. KLEYWEGT A, SHAPRIO A, and HOMEM-DE-MELLO T. The sample average approximation method for stochastic discrete optimization[J]. SIAM Journal on Optimization, 2002, 12(2): 479-502. doi: 10.1137/S1052623499363220. FUJISHIGE S. Submodular Functions and Optimization[M]. Amsterdam, Elsevier Science Press, 2005, Chapter 3. SHAPRIO A, DENTCHEVA D, and RUSZCZYNSKI A. Lectures on Stochastic Programming: Modeling and Theory [M]. SIAM: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, SIAM Press, 2014, Chapter 1. -
計量
- 文章訪問數(shù): 1858
- HTML全文瀏覽量: 257
- PDF下載量: 301
- 被引次數(shù): 0
下載:
