非退市条件下更新产品扩散的投放时间与种子优化研究

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

摘要/Abstract

摘要： 近年来，在更新产品与旧产品存在竞争关系的市场环境下，更新产品的延期投放成为许多企业的产品运营策略。现有竞争扩散研究重点关注外部竞争下一种产品的扩散最大化问题，尚没有考虑内部竞争下(如旧产品与更新产品的竞争)全部产品的扩散最大化问题。本文研究非退市条件下更新产品投放时机和种子优化问题：在一个已存在旧产品的社会网络G(N,E)中，产品以竞争扩散模型的P形式传播其影响力，更新产品投放时，新旧产品同时扩散，如何选择投放阶段t和p个更新产品的种子使得新旧产品利润之和最大化。本文提出了一种基于竞争的确定阈值模型，并构建了该问题的整数规划模型，设计了求解大规模问题的多阶段贪婪算法。计算实验显示，该算法具有较高求解效率，比传统贪婪算法提高了88%；该算法具有较高求解质量，比随机算法提高了651%，比度数下降算法提高了9.5%。同时，发现更新产品种子数量多、计划阶段限制大、单位利润大时，延期投放使得产品利润更高。

关键词: 社会网络分析；影响力最大化问题；更新产品；投放时机

Abstract: In recent years, in a market environment where there is a competitive relationship between updated products and old products, a delayed launch of updated products has become the product operation strategy of many enterprises. Current competitive diffusion studies focus on the problems of diffusion maximization of one product under external competition, but have not considered the problems of diffusion maximization of all products under internal competition (such as competition between old products and updated products). The optimization of launching time and seed selection for updated products under a non-delisting strategy is considered: in a social network G(N，E) with existing old products, products spread their influence in the form of diffusion model P, and the old products will keep on spreading when updated products are launched, and an optimal choosing on the stage t and the p seeds will be found for launching updated products to maximize the sum of the profits from both old and updated products. In this paper, an integer programming model which is based on competition is established, and a multi-stage greedy algorithm is designed to solve large-scale instances. The basic idea of the algorithm is: select new product seeds iteratively in a certain stage of the planning period, and calculate the marginal influence of all other candidate seeds, calculate the total income of all cases, and find out the total profit of all cases. To maximize the total revenue, the seed delivery stage and seeds of the product are renewed. It is tested on scale-free network with n=1000, m=3 and a real social network data set Facebook. Computational experiments show that this algorithm has higher solution efficiency, which is 96% higher than the traditional greedy algorithm; And this algorithm has better solution quality, which is 253% better than random algorithm and 14% better than degree discount algorithm. At the same time, with simulations in a real network, it is found that the larger number of seeds of the updated products, or the larger planning stage, or the higher profit of the updated products tends to a later launching time to make the manufacturer obtain higher profits, and it can provide decision-making for enterprises to carry out network marketing.

Key words: social network analysis; influence maximization; update products; launch timing

中图分类号:

翁克瑞, 周静. 非退市条件下更新产品扩散的投放时间与种子优化研究[J]. 中国管理科学, 2023, 31(2): 226-234.

WENG Ke-rui, ZHOU Jing. Study on Updated Products Launch Timing and Seed Optimization under a Non-Delisting Strategy[J]. Chinese Journal of Management Science, 2023, 31(2): 226-234.

参考文献

［1］许博, 龚国华. 新产品投放市场的最佳时间分析［J］. 物流科技, 2005, 28(5):105-108.Xu Bo, Gong Guohua. Analysis on the optimal launch time of new product［J］. Logistics Sci-Tech, 2005, 28(5):105-108.
［2］贾昌荣.新产品投放:不懂规则难赢销［J］.中国机电工业, 2010(3):90-94.Jia Changrong. New product launch: it is difficult to win sales without understanding the rules［J］. China Machinery & Electric Industry, 2010(3):90-94.
［3］ Kempe D, Kleinberg J, Tardos E V. 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, DC,USA,August 24-27, Association for Computing Machinery, 2003: 137-146.
［4］王展昭.考虑重复购买因素的品牌竞争对新产品扩散的影响研究——基于小世界网络的仿真环境［J］. 中国管理科学, 2019, 27(12): 164-174.Wang Zhanzhao. The analysis of affect mechanism of the brand competition to new products diffusion with repeat purchase-based on the small-world network［J］. Chinese Journal of Management Science, 2019, 27(12): 164-174.
［5］张旭,侯光明.双口碑效应下新产品扩散研究——以电影为例［J］. 中国管理科学, 2018, 26(10): 79-88.Zhang Xu, Hou Guangming. New product diffusion on two effects of word of mouth: evidence from movies［J］. Chinese Journal of Management Science, 2018, 26(10): 79-88.
［6］ Lu Wei, Chen Wei, Lakshmanan L. From competition to complementarity: comparative influence diffusion and maximization［C］//Proceedings of the VLDB Endowment, Kohala Coast,Hawaii,August 31-September 4， 2015.
［7］ Ou Hanqing, Zhou Chongguang, Chen Mingxian. Influence maximization for complementary goods: why parties fail to cooperate?［C］//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, Indianapolis, IN, USA, October 24-28, Association for Computing Machinery, 2016:1713-1722.
［8］ Borodin A, Filmus Y, Oren J. Threshold models for competitive influence in social networks［C］//Proceedings of the 6th international conference on Internet and network economics, Stanford,CA,USA,December 13-17, Berlin, Springer-Verlag, 2010: 539-550.
［9］ Bozorgi A, Samet S, Kwisthout J, et al. Community based influence maximization in social networks under a competitive linear threshold model［J］. Knowledge-Based Systems, 2017, 134: 149-158.
［10］周琦萍,徐迪,杨芳.基于复杂社会网络和局部网络效应的新产品竞争扩散的计算实验研究［J］.软科学, 2013, 27(7): 13-17.Zhou Qiping, Xu Di, Yang Fang. Computational experiments for study of the competition diffusion of new products with local network effects based on complex social networks［J］. Soft Science, 2013,27(7): 13-17.
［11］吴靖. 基于复杂社会网络的初始种子用户对创新扩散的影响研究［D］. 成都：西南交通大学, 2015.Wu Jing. Research on the influences of the initial seed consumers on innovation diffusion based on complex social network［D］. Chengdu: Southwest Jiaotong University, 2015.
［12］ 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, California,USA,August 12-15, Association for Computing Machinery, 2007: 420-429.
［13］ Goyal A, Lu W, Lakshmanan L. 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, 2011.
［14］ Kimura M, Saito K. Tractable models for information diffusion in social networks［C］∥Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, Springer-Verlag, 2006: 259-271.
［15］ Chen Wei, Yuan Yifei, Zhang Li. Scalable influence maximization in social networks under the linear threshold model［C］// Proceedings of the 10th IEEE International Conference on Data Mining, Sydney, Australia, December 13-17, 2010: 88-97.
［16］ Wang Chi, Chen Wei, Wang Yajun. Scalable influence maximization for independent cascade model in large-scale social networks［J］. Data Mining and Knowledge Discovery, 2012, 25(3): 545-576.
［17］ Goyal A, Lu W, Lakshmanan L. SIMPATH: an efficient algorithm for influence maximization under the linear threshold model［C］//Proceedings of the 11th IEEE International Conference on Data Mining, Vancouver, BC, Canada,December 11-14, 2011: 211-220.
［18］ Chen Wei, Wang Yajun, Yang Siyu. Efficient influence maximization in social networks［C］//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, Paris, France, June 28-July 1, Association for Computing Machinery, 2009: 199-208.
［19］ Daliri Khomami M M, Rezvanian A, Bagherpour N, et al. Minimum positive influence dominating set and its application in influence maximization: a learning automata approach［J］. Applied Intelligence, 2018, 48(3): 570-593.
［20］ Bozorgi A, Haghighi H, Zahedi M S, et al. INCIM: a community-based algorithm for influence maximization problem under the linear threshold model［J］. Information Processing& Management, 2016, 52(6): 1188-1199.
［21］ Shang Jiaxing, Zhou Shangbo, Li Xin, et al. CoFIM: a community-based framework for influence maximization on large-scale networks［J］. Knowledge-Based Systems, 2017, 117: 88-100.
［22］ Cui Laizhong, Hu Huaxiong, Yu Shui, et al. DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks［J］. Journal of Network and Computer Applications, 2018, 103: 119-130.
［23］ Gong Maoguo, Yan Jianan, Shen Bo, et al. Influence maximization in social networks based on discrete particle swarm optimization［J］. Information Sciences, 2016, 367: 600-614.
［24］ 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,USA,January 5-7, Society for Industrial and Applied Mathematics, 2014: 946-957.
［25］ Su Meng, Rao V R. Timing decisions of new product preannouncement and launch with competition［J］. International Journal of Production Economics, 2011, 129(1):51-64.
［26］龚田华. 基于扩散理论的重购产品定价与投放策略研究［D］.南京:南京农业大学,2015.Gong Tianhua. Pricing and launch strategy of repurchased products based on diffusion theory［D］. Nanjing: Nanjing Agricultural University, 2015.
［27］全雄文,魏杰,涂菶生.更新产品投放市场时间的优化［J］.南开大学学报(自然科学版),2008,41(6):67-71.Quan XiongWen, Wei Jie, Tu BengSheng. Optimization of time to market for updated products［J］. Acta Scientiarum Naturalium Universitatis Nankaiensis,2008,41(6):67-71.
［28］ Swaminathan A. An algorithm for influence maximization and target set selection for the deterministic linear threshold model［D］. Blacksburg. Virginia Polytechnic Institute and State University, 2014.
［29］ Albert R, Barab A. Statistical mechanics of complex networks［J］. Reviews of Modern Physics, 2002, 74(1):47-97.