社交网络影响力传播研究

doi:10.11959/j.issn.2096-0271.2015031

大数据 ›› 2015, Vol. 1 ›› Issue (3): 82-98.doi: 10.11959/j.issn.2096-0271.2015031

社交网络影响力传播研究

陈卫

微软亚洲研究院北京 100080

出版日期:2015-06-20 发布日期:2020-09-28
作者简介:陈卫，男，微软亚洲研究院高级研究员，清华大学客座教授，中国科学院计算所客座研究员，多个国际顶级数据挖掘和数据管理会议（KDD、WSDM、SIGMOD、ICDE、WWW等）的程序委员会成员，中国计算机学会大数据专家委员会首批成员，《大数据》期刊编委。近期主要研究方向包括社交与信息网络算法和数据挖掘、网络博弈论和经济学、在线学习等。近几年在社会影响力最大化方面的一系列开创性研究成果，在KDD、ICDM、SDM、WSDM、ICWSM、AAAI、VLDB等顶级数据挖掘、人工智能和数据库学术会议上发表后得到良好反响，并引发这一方向众多的后续工作。最早发表的KDD’2009论文被引用次数排同会议所有论文第二位，而第二篇KDD’2010论文被引用次数排同会议所有论文第一位。2013年与另外两位合作者合写了一部关于影响力传播和最大化的专著（Information and Influence Propagation in Social Networks,Morgan＆Claypool,2013），系统总结了这方面的研究成果和最新发展。另外，在与社会和信息网络相关的方向，如社区检测、网络中心化度量排序、网络博弈、网络定价、网络激励机制等方面也都做出开创性的工作，其中将博弈论引入网络社区检测的论文获得了2010年欧洲机器学习及数据挖掘会议最佳学生论文奖。
基金资助:
国家自然科学基金重点项目(61433014)

Research on Influence Diffusion in Social Network

Wei Chen

Microsoft Research Asia,Beijing 100080,China

Online:2015-06-20 Published:2020-09-28
Supported by:
The National Natural Science Foundation of China(61433014)

摘要/Abstract

摘要：

随着互联网和大数据的研究应用日益广泛，对社交网络影响力传播的研究成为数据挖掘和社交网络分析中的热点。从影响力传播模型、影响力传播学习和影响力传播优化3个方面总结了近些年计算机科学领域对影响力传播研究的主要成果，展示了影响力传播研究中对随机模型、数据挖掘、算法优化和博弈论等技术的综合运用。最后，简要讨论了影响力传播研究和应用中存在的问题、挑战及今后的研究方向。

关键词: 社交网络, 社会影响力, 影响力传播模型, 影响力最大化, 社会影响力学习, 病毒营销

Abstract:

With the wide spread of internet and big data research and applications,influence diffusion research in social network becomes one of the hot topics in data mining and social network analysis in recent years.The main results on social influence diffusion research from the field of computer science in the last decade,which covers the three main areas-- influence diffusion modeling,influence diffusion learning,and influence diffusion optimization,were summarized.Different techniques,such as stochastic modeling,data mining,algorithmic optimization,and game theory,were demonstrated in their application to influence diffusion research.Finally,some discussions on the current issues,challenges and future directions in influence diffusion research and applications were provided.

Key words: social network, social influence, influence diffusion model, influence maximization, social influence learning, viral marketing

中图分类号:

G206

陈卫. 社交网络影响力传播研究[J]. 大数据, 2015, 1(3): 82-98.

Wei Chen. Research on Influence Diffusion in Social Network[J]. Big Data Research, 2015, 1(3): 82-98.

图/表 2

参考文献 50

[1]	Bass F M . A new product growth for model consumer durables. Management Science, 1969,15(5): 215～227
[2]	Granovetter M . Threshold models for collective behavior. American Journal of Sociology, 1978,83(6): 1420～1443
[3]	Christakis N A , Fowler J H . The spread of obesity in a large social network over 32 years. New England Journal of Medicine, 2007,357(4): 370～379
[4]	Christakis N A , Fowler J H . The collective dynamics of smoking in a large social network. New England Journal of Medicine, 2008,358(21): 2249～2258
[5]	Aral S , Walker D . Identifying influential and susceptible members of social networks. Science, 2012(337): 337～341
[6]	Bond R M , Fariss C J , Jones J J , et al. A 61-million-person experiment in social influence and political mobilization. Nature, 2012(489):295～298
[7]	Charu C , Aggarwal . Social Network Data Analysis. New York: Springer, 2011: 177～214
[8]	吴信东, 李毅, 李磊 . 在线社交网络影响力分析. 中国计算机学报, 2014,37(4): 735～752
	Wu X D , Li Y , Li L . Influence analysis of online social networks. Chinese Journal of Computers, 2014,37(4): 735～752
[9]	Chen W , Lakshmanan L V S , Castillo C . Information and Influence Propagation in Social Networks. Californi: Morgan &Claypool Publishers, 2013
[10]	Domingos P , Richardson M . Mining the network value of customers. Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), San Francisco,USA, 2001: 57～66
[11]	Kempe D , Kleinberg J M , Tardos é , . Maximizing the spread of influence through a social network. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Washington DC,USA, 2003: 137～146
[12]	Chen W , Lu W , Zhang N , . Time-critical influence maximization in social networks with time-delayed diffusion process. Proceedings of the 26th National Conference on Artificial Intelligence(AAAI), Toronto,Canada, 2012
[13]	Centola D , Macy M . Complex contagion and the weakness of long ties. American Journal of Sociology, 2007,113(3): 702～734
[14]	Gomez-Rodriguez M , Balduzzi D , Sch?lkopf B , . Uncovering the temporal dynamics of diffusion networks. Proceedings of the 28th International Conference on Machine Learning (ICML), Bellevue,Washington,USA, 2012: 561～568
[15]	Newman M E J . Networks: an Introduction. Oxford: Oxford University Press, 2010
[16]	Even-Dar E , Shapira A . A note on maximizing the spread of influence in social networks. Proceedings of the 3rd Workshop on Internet and Network Economic (WINE), San Diego,USA, 2007,281～286
[17]	Li Y , Chen W , Wang Y , et al. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM), Rome,Italy, 2013:657～666
[18]	Immorlica N , Kleinberg J M , Mahdian M , et al. The role of compatibility in the diffusion of technologies through social networks. Proceedings of the 8th ACM Conference on Electronic Commerce (EC), San Diego,USA, 2007:75～83
[19]	Montanari A , Saberi A . Convergence to equilibrium in local interaction games. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta,USA, 2009: 303～312
[20]	Budak C , Agrawal D , Abbadi A E , . Limiting the spread of misinformation in social networks. Proceedings of the 20th International Conference on World Wide Web (WWW), Hyderabad,India, 2011:665～674
[21]	Chen W , Collins A , Cummings R , et al. Influence maximization in social networks when negative opinions may emerge and propagate. Proceedings of SIAM International Conference on Data Mining, Mesa,USA, 2011:379～390
[22]	He X , Song G , Chen W , et al. Influence blocking maximization in social networks under the competitive linear threshold Model. Proceedings of SIAM International Conference on Data Mining, Anaheim,USA, 2012:463～474
[23]	Lu W , Bonchi F , Goyal A , et al. The bang for the buck: fair competitive viral marketing from the host perspective. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Chicago,USA, 2013:928～936
[24]	Lu W , Chen W , Lakshmanan L V S . From competition to complementarity:comparative influence diffusion and maximization. Proceedings of the 42nd International Conference on Very Large Data Bases (VLDB), New Delhi,India, 2016Accepted
[25]	Nemhauser G , Wolsey L , Fisher M . An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 1978(14):265～294
[26]	Wang C , Chen W , Wang Y . Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 2012,25(3):545～576
[27]	Chen W , Yuan Y , Zhang L . Scalable influence maximization in social networks under the linear threshold Model. Proceedings of the 10th IEEE International Conference on Data Mining (ICDM), Sydney,Australia, 2010:88～97
[28]	Chen W , Wang Y , Yang S . Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Paris,France, 2009:199～208
[29]	Goyal A , Lu W , Lakshmanan L V S . SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. Proceedings of the 11st IEEE International Conference on Data Mining (ICDM), Vancouver,Canada, 2011:211～220
[30]	Jung K , Heo W , Chen W . IRIE: scalable and robust influence maximization in social networks. Proceedings of the 12nd IEEE International Conference on Data Mining (ICDM), Brussels,Belgium, 2012:918～923
[31]	Borgs C , Brautbar M , Chayes J , et al. Maximizing social influence in nearly optimal time. Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland,USA, 2014:946～957
[32]	Leskovec J , Krause A , Guestin C , et al. Cost-effective outbreak detection in networks. Proceedings of the 13rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), San Jose,USA, 2007:420～429
[33]	Tang Y , Shi Y , Xiao X . Influence maximization in near-linear time: a martingale approach. Proceedings of ACM SIGMOD Conference (SIGMOD), Melbourne,Australia, 2015:1539～1554
[34]	Tang Y , Xiao X , Shi Y . Influence maximization: near-optimal time complexity meets practical efficiency. Proceedings of ACM SIGMOD Conference (SIGMOD), Snowbird,USA, 2014:75～86
[35]	Cohen E , Delling D , Pajor T , et al. Sketch-based influence maximization and computation: scaling up with guarantees. Proceedings of the 23rd ACM International Conference on Information and Knowledge Management (CIKM), Shanghai,China, 2014:629～638
[36]	Goyal A , Bonchi F , Lakshmanan L V S , et al. On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining 2012,2(1)
[37]	Long C , Wong R CW . Minimizing seed set for viral marketing. Proceedings of the 11st IEEE International Conference on Data Mining (ICDM), Vancouver,Canada, 2011: 427～436
[38]	Lu W , Lakshmanan L V S . Profit maximization over social networks. Proceedings of the 12nd IEEE International Conference on Data Mining (ICDM), Brussels,Belgium, 2012: 479～488
[39]	Khalil E , Dilkina B , Song L . Scalable diffusion-aware optimization of network topology. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York,USA, 2014:1226～1235
[40]	Goldberg S , Liu Z . The diffusion of networking technologies. Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), New York,USA, 2013:1577～1594
[41]	Zhang P , Chen W , Sun X , et al. Minimizing seed set selection with probabilistic coverage guarantee in a social network. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York,USA, 2014:1306～1315
[42]	Chen W , Li F , Lin T , et al. Combining traditional marketing and viral marketing with amphibious influence maximization. Proceedings of the 16th ACM Conference on Economics and Computation (EC), Portland,USA, 2015:779～796
[43]	Yang DN , Hung HJ , Lee WC , et al. Maximizing acceptance probability for active friending in online social networks. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Chicago,USA, 2013:713～721
[44]	Anagnostopoulos A , Kumar R , Mahdian M . Influence and correlation in social networks. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Las Vegas,USA, 2008:7～15
[45]	Netrapalli P , Sanghavi S . Learning the graph of epidemic cascades. Proceedings of ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), London,UK, 2012: 211～222
[46]	Saito K , Nakano R , Kimura M . Prediction of information diffusion probabilities for independent cascade model. Proceedings of the 12nd International Conference on Knowledge-based Intelligent Information and Engineering Systems (KES), Zagreb,Croatia, 2008:67～75
[47]	Goyal A , Bonchi F , Lakshmanan L V S . Learning influence probabilities in social networks. Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM), New York,USA, 2010:241～250
	Barbieri N , Bonchi F , Manco G . Topic-aware social influence propagation models. Knowledge Information Systems 2013,37(3):555～584
[49]	Shakarian P , Salmento J , Pulleyblank W , et al. Reducing gang violence through network influence based targeting of social programs. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), New York,USA, 2014:1829～1836
[50]	Wang C , Yu X , Li Y , et al. Content coverage maximization on word networks for hierarchical topic summarization. Proceedings of the 22nd ACM International Conference on Information and Knowledge Management(CIKM), San Francisco,USA, 2013:249～258

社交网络影响力传播研究

Research on Influence Diffusion in Social Network

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 50

相关文章 5

Metrics

推荐阅读 0

[1]	张智杰, 孙晓明, 张家琳, 陈卫. 基于样本的优化[J]. 大数据, 2021, 7(5): 100-110.
[2]	孔芳, 杨悦然, 陈卫, 李帅. 基于优化反馈的组合在线学习[J]. 大数据, 2021, 7(5): 111-130.
[3]	秦烁, 吕欣, 孟凡辉, 胡延庆. 在线社交媒体信息冗余现象建模与实证研究[J]. 大数据, 2018, 4(5): 50-61.
[4]	邵蓥侠, 冯是聪. 社交网络分析在公共安全领域的应用[J]. 大数据, 2017, 3(2): 38-44.
[5]	程致远, 鲍玉斌, 冷芳玲. 面向大规模图数据的并行图布局算法[J]. 大数据, 2016, 2(5): 12-21.