Computer Science ›› 2019, Vol. 46 ›› Issue (9): 59-65.doi: 10.11896/j.issn.1002-137X.2019.09.007

• NDBC 2018 • Previous Articles     Next Articles

RAISE:Efficient Influence Cost Minimizing Algorithm in Social Network

SUN Yong-yue, LI Hong-yan, ZHANG Jin-bo   

  1. (School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China);
    (Key Laboratory of Machine Perception(Ministry of Education),Peking University,Beijing 100871,China)
  • Received:2018-07-02 Online:2019-09-15 Published:2019-09-02

Abstract: In many scenarios,such as viral marketing and political campaign,persuading individuals to accept new pro-ducts or ideas requires a certain cost.Influence cost minimization problem is defined as choosing an influential set of individuals so that the influence can be spread to given number of individuals while the total cost is minimized.The solution quality and time efficiency are faced with bottlenecks when solving this problem with existing methods.To tackle the issue,this paper proposed an efficient algorithm,RAISE.In theory,when the expected influence is comparable to the network size,the proposed algorithm has constant approximation ratio and linear time complexity.In practice,the proposed algorithm is significantly superior to the existing methods in terms of solution quality and time efficiency.

Key words: Cost, Influence cost minimization, Online social network, Random sampling

CLC Number: 

  • TP393
[1]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.New York:ACM,2001:57-66.
[2]BUDAK C,AGRAWAL D,ABBADI A.Limiting the Spread of Misinformation in Social Networks[C]//Proceedings of the 20th International Conference on World Wide Web.New York:ACM,2011:665-674.
[3]LI Y,BAO Z,LI G,et al.Real Time Personalized Search on Social Networks[C]//2015 IEEE 31st International Conference on Data Engineering (ICDE).New York:IEEE Press,2015:639-650.
[4]CHEN N.On the Approximability of Influence in Social Networks[J].Siam Journal on Discrete Mathematics,2009,23(3):1400-1415.
[5]LONG C,WONG R.Minimizing Seed Set for Viral Marketing[C]//IEEE International Conference on Data Mining.New York:IEEE Press,2011:427-436.
[6]ZHANG P,CHEN W,SUN X,et al.Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Net-work[C]//Proceedings of 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.New York:ACM,2014:1306-1315.
[7]KEMPE D,KLEINBERG J,TARDOS E.Maximizing theSpread of Influence through a Social Network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining.New York:ACM,2003:137-146.
[8]GOLDBERG S,LIU Z.The Diffusion of Networking Technologies[C]//Twenty-fourth Acm-siam Symposium on Discrete Algorithms.New York:SIAM,2013:1577-1594.
[9]BARABASI A,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.
[10]TANG Y,XIAO X,SHI Y.Influence Maximization:Near-optimal Time Complexity Meets Practical Efficiency[C]//Procee-dings of the 2014 ACM SIGMOD International Conference on Management of Data.New York:ACM,2014:75-86.
[11]MOTWANI R,RAGHAVAN P.Randomized Algorithms[M].Cambridge:Cambridge University Press,1995:67-73.
[12]CHA M,MISLOVE A,GUMMADI K.A Measurement-drivenAnalysis of Information Propagation in the Flickr Social Network[C]//Proceedings of the 18th International Conference on World Wide Web.New York:ACM,2009:721-730.
[13]DINH T,NGUYEN D,THAI M.Cheap,Easy,and Massively Effective Viral Marketing in Social Networks:Truth or Fiction?[C]//Proceedings of the 23rd ACM conference on Hypertext and social media.New York:ACM,2012:165-174.
[14]SLAVIK P.Improved Performance of the Greedy Algorithm for Partial Cover[J].Information Processing Letters,1997,64(5):251-254.
[15]TANG Y,SHI Y,XIAO X.Influence Maximization in Near-line-ar Time:A Martingale Approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.New York:ACM,2015:1539-1554.
[1] SHAO Zi-hao, YANG Shi-yu, MA Guo-jie. Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques [J]. Computer Science, 2022, 49(9): 228-235.
[2] LI Jing-tai, WANG Xiao-dan. XGBoost for Imbalanced Data Based on Cost-sensitive Activation Function [J]. Computer Science, 2022, 49(5): 135-143.
[3] YAN Lei, ZHANG Gong-xuan, WANG Tian, KOU Xiao-yong, WANG Guo-hong. Scheduling Algorithm for Bag-of-Tasks with Due Date Constraints on Hybrid Clouds [J]. Computer Science, 2022, 49(5): 244-249.
[4] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[5] WANG Zi-yin, LI Lei-jun, MI Ju-sheng, LI Mei-zheng, XIE Bin. Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost [J]. Computer Science, 2022, 49(4): 161-167.
[6] HUANG Ying-qi, CHEN Hong-mei. Cost-sensitive Convolutional Neural Network Based Hybrid Method for Imbalanced Data Classification [J]. Computer Science, 2021, 48(9): 77-85.
[7] YUAN De-yu, CHEN Shi-cong, GAO Jian, WANG Xiao-juan. Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game [J]. Computer Science, 2021, 48(3): 313-319.
[8] LUAN Ling, PAN Lian-wu, YAN Lei, WU Xiao-lin. Research on Intelligent Control Technology of Accurate Cost for Unit Confirmation in All Links of Power Transmission and Transformation Project Based on Edge Computing [J]. Computer Science, 2021, 48(11A): 688-692.
[9] LU Shu-xia, ZHANG Zhen-lian. Imbalanced Data Classification of AdaBoostv Algorithm Based on Optimum Margin [J]. Computer Science, 2021, 48(11): 184-191.
[10] LIU Jing, FANG Xian-wen. Mining Method of Business Process Change Based on Cost Alignment [J]. Computer Science, 2020, 47(7): 78-83.
[11] ZHANG De-gan, FAN Hong-rui, GONG Chang-le, GAO Jin-xin, ZHANG Ting, ZHAO Peng-zhen and CHEN Chen. New Method of Data Missing Estimation for Vehicle Traffic Based on Tensor [J]. Computer Science, 2020, 47(6A): 505-511.
[12] WU Chong-ming, WANG Xiao-dan, XUE Ai-Jun and LAI Jie. Multiclass Cost-sensitive Classification Based on Error Correcting Output Codes [J]. Computer Science, 2020, 47(6A): 89-94.
[13] XIANG Wei, WANG Xin-wei. Imbalance Data Classification Based on Model of Multi-class Neighbourhood Three-way Decision [J]. Computer Science, 2020, 47(5): 103-109.
[14] FANG Xu-yuan, TIAN Hong-xin, SUN De-chun, DU Wen-cong, QI Ting. Utility Function Heterogeneous Network Access Algorithm Based on Green Energy Perception [J]. Computer Science, 2019, 46(8): 127-132.
[15] ZHANG Lei, HU Bo-wen, ZHANG Ning, WANG Mao-sen. Global Residual Recursive Network for Image Super-resolution [J]. Computer Science, 2019, 46(6A): 230-233.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!