计算机科学 ›› 2019, Vol. 46 ›› Issue (9): 59-65.doi: 10.11896/j.issn.1002-137X.2019.09.007
孙永樾, 李红燕, 张金波
SUN Yong-yue, LI Hong-yan, ZHANG Jin-bo
摘要： 在市场营销、政治选举等领域,说服个体接受新产品或新思想需要耗费一定的成本。将影响成本最小化问题定义为如何选择不同个体,使影响最终扩散到社交网络中给定数量的个体,且耗费的成本最小。运用现有方法解决该问题,解的质量和时间效率都面临一定的瓶颈。为了解决该问题,提出了一种高效的算法——RAISE算法。在理论上,当期望达到的影响与网络规模可比拟时,该算法具备常数近似比和线性时间复杂度。实践表明,该算法在解的质量和时间效率两方面都显著优于现有方法。
中图分类号:
| [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] | 邵子灏, 杨世宇, 马国杰. 室内信息服务的基础——低成本定位技术研究综述 Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques 计算机科学, 2022, 49(9): 228-235. https://doi.org/10.11896/jsjkx.210900260 |
| [2] | 严磊, 张功萱, 王添, 寇小勇, 王国洪. 混合云下具有交付期约束的众包任务调度算法 Scheduling Algorithm for Bag-of-Tasks with Due Date Constraints on Hybrid Clouds 计算机科学, 2022, 49(5): 244-249. https://doi.org/10.11896/jsjkx.210300120 |
| [3] | 左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法 Budget-aware Influence Maximization in Social Networks 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228 |
| [4] | 袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法 Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game 计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079 |
| [5] | 张龙信, 周立前, 文鸿, 肖满生, 邓晓军. 基于异构云计算的成本约束下的工作流能量高效调度算法 Energy Efficient Scheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems 计算机科学, 2020, 47(8): 112-118. https://doi.org/10.11896/jsjkx.200300038 |
| [6] | 刘静, 方贤文. 基于成本对齐的业务流程变化挖掘方法 Mining Method of Business Process Change Based on Cost Alignment 计算机科学, 2020, 47(7): 78-83. https://doi.org/10.11896/jsjkx.190600140 |
| [7] | 张德干, 范洪瑞, 龚倡乐, 高瑾馨, 张婷, 赵彭真, 陈晨. 一种基于张量的车辆交通数据缺失估计新方法 New Method of Data Missing Estimation for Vehicle Traffic Based on Tensor 计算机科学, 2020, 47(6A): 505-511. https://doi.org/10.11896/JsJkx.190700045 |
| [8] | 袁得嵛, 高见, 叶萌熙, 王小娟. 基于拓扑扩展的在线社交网络恶意信息源定位算法 Malicious Information Source Locating Algorithm Based on Topological Extension in Online Social Network 计算机科学, 2019, 46(5): 129-134. https://doi.org/10.11896/j.issn.1002-137X.2019.05.020 |
| [9] | 黄建一, 李建江, 王铮, 方明哲. 基于上下文相似度矩阵的Single-Pass短文本聚类 Single-Pass Short Text Clustering Based on Context Similarity Matrix 计算机科学, 2019, 46(4): 50-56. https://doi.org/10.11896/j.issn.1002-137X.2019.04.008 |
| [10] | 殷佳, 管昕洁, 白光伟. 基于移动边缘计算的任务迁移和协作式负载均衡机制 Task Offloading and Cooperative Load Balancing Mechanism Based on Mobile Edge Computing 计算机科学, 2019, 46(12): 126-131. https://doi.org/10.11896/jsjkx.181202453 |
| [11] | 吴修国, 刘翠. 云存储系统中最小开销的数据副本布局转换策略 Data Replicas Distribution Transition Strategy in Cloud Storage System 计算机科学, 2019, 46(10): 202-208. https://doi.org/10.11896/jsjkx.180901623 |
| [12] | 赵小敏, 曹光斌, 费梦钰, 朱李楠. 基于加权类比的软件成本估算方法 Software Cost Estimation Method Based on Weighted Analogy 计算机科学, 2018, 45(11A): 501-504. |
| [13] | 赵小敏, 费梦钰, 曹光斌, 朱李楠. 软件成本评估方法综述 Review for Software Cost Evaluation Methods 计算机科学, 2018, 45(11A): 76-83. |
| [14] | 王勇, 李逸, 王丽丽, 朱晓燕. 基于类推和灰色模型的软件阶段成本预测 Software Stage Effort Prediction Based on Analogy and Grey Model 计算机科学, 2018, 45(11A): 480-487. |
| [15] | 邢颖,郭基凤,缑西梅. 众包模式下基于交易成本理论的并行管理模型研究 Research on Parallel Management Model Based on Transaction Cost Theory for Crowd-sourcing 计算机科学, 2017, 44(4): 161-164. https://doi.org/10.11896/j.issn.1002-137X.2017.04.035 |
|
||
首页