基于最小点覆盖和反馈点集的社交网络影响最大化算法

doi:10.11999/IEIT160019

Abstract
Figure/Table
References (28)
Related Citation (15)

Download: PDF (297 KB)
Export: BibTeX | EndNote (RIS)

Abstract

Influence maximization is an optimization issue of finding a subset of nodes under a given diffusion model, which can maximize the spread of influence. This optimization issue has been proved to be NP-hard. Leveraging the fact that vertices in minimum vertex covering and feedback vertex set are of great importance for the connectivity of a graph, a heuristic algorithm for influence maximization based on Minimum Vertex Covering and Feedback Vertex Set (MVCFVS). Extensive experiments on various diffusion models against state of the art algorithms are carried out. Specifically, the proposed algorithm performs excellent on Independent Cascade Model (ICM) and Weighted Cascade Model (WCM), which exhibits its great advantages in terms of influence range and convergent speed.

Key words： Social network Influence maximization Diffusion models Minimum vertex covering Feedback vertex set

Received: 05 January 2016 Published: 09 March 2016

PACS:

TP393

Fund:

The National Natural Science Foundation of China (61370193)

Corresponding Authors: XIE Huiyang E-mail: xhyang@bjfu.edu.cn

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	XU Yuguang
	PAN Jingzhi
	XIE Huiyang

Cite this article:

XU Yuguang,PAN Jingzhi,XIE Huiyang. Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network[J]. JEIT, 2016, 38(4): 795-802.

URL:

http://jeit.ie.ac.cn/EN/10.11999/IEIT160019 OR http://jeit.ie.ac.cn/EN/Y2016/V38/I4/795

[1]	WATTS D J and STROGATZ S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442.
[2]	BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[3]	SAITO K, NAKANA R, and KIMURA M. Prediction of information diffusion probabilities for independent cascade model[J]. Lecture Notes in Computer Science, 2008, 5179: 67-75.
[4]	TANG J, SUN J, and YANG Z. Social influence analysis in large-scale networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA, 2009: 807-816.
[5]	GOYAL A, BONCHI F, and LASKHMANAN L. Learning influence probabilities in social networks[C]. Proceedings of the Third ACM International Conference on Web Search & Data Mining, New York, USA, 2010: 241-250.
[6]	WANG C, TANG J, SUN J, et al. Dynamic social influence analysis through time-dependent factor graphs[C]. Proceedings of the 2011 International Conference on Advances in Social Networks Analysis and Mining, Washington, DC, USA, 2011: 239-246.
[7]	DOMIGOS P and RICHARDSON M. Mining the network value of customers[C]. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, USA, 2001: 57-66.
[8]	RICHARDSON M and DOMINGOS P. Mining knowledge- sharing sites for viral marketing[C]. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Alberta, Canada, 2002: 61-70.
[9]	KEMPE D, KLEINBERG J, and TARDOS E. Influential nodes in a diffusion model for social networks[J]. International Colloquium on Automata, Languages and Programming, 2005, 32: 1127-1138.
[10]	KEMPE D, KLEINBERG J, and TARDOS E. Maximizing the spread of influence in a social network[C]. Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, 2003: 137-146.
[11]	LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost- effective outbreak detection in networks[C]. Proceedings of the Kdd 07 ACM SIGKDD International Conference on Knowledge Discovery and Data, Pittsburgh, PA, USA, 2007: 420-429.
[12]	ZHOU C and GUO L. A note on influence maximization in social networks from local to global and beyond[C]. Proceedings of the 1th International Conference on Data Science (ICDS), Beijing, China, 2014: 27-28.
[13]	ZHOU C, ZHANG P, GUO J, et al. An upper bound based greedy algorithm for mining top-k influential nodes in social networks [C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data, Seoul, Korea, 2014: 421-422.
[14]	CHENG S, SHEN H, HUANG J, et al. IMRank: influence maximization via finding self-consistent ranking[C]. Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval?(SIGIR '14), New York, NY, USA, 2014: 475-484.
[15]	CHEN W, WANG Y, and YANG S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, 2009: 199-208.
[16]	JIANG Q, SONG G, CONG G, et al. Simulated annealing based influence maximization in social networks[C]. Proceedings of the 25th AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 2011: 127-132.
[17]	ZOU F, ZHANG Z, and WU W. Latency-bounded minimum influential node selection in social networks[C]. Proceedings of the Wireless Algorithms, Systems, and Applications, 4th International Conference, Boston, MA, USA, 2009: 519-526.
[18]	ZOU F, WILLSON J, ZHANG Z, et al. Fast information propagation in social networks[J]. Discrete Mathematics Algorithms & Applications, 2010, 2(1): 125-141.
[19]	COHEN E, DELLING D, PAJOR T, et al. Sketch-based influence maximization and computation: scaling up with guarantees[C]. Proceedings of Conference on Information and Knowledge Management, CIKM, Shanghai, China, 2014: 629-638.
[20]	JIANG F, JIN S, WU Y, et al. A uniform framework for community detection via influence maximization in social networks[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Beijing, China, 2014: 27-32.
[21]	CAO J, DAN D, XU S, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese Journal of Computers, 2015, 38(2): 238-248.
[22]	LUCIER B, OREN J, and SINGER Y. Singer influence at scale: distributed computation of complex contagion in networks[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, 2015: 735-744.
[23]	GOLDENBERG J, LIBAI B, and MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth [J]. Marketing Letters, 2001, 12(3): 211-223.
[24]	KARP R M. Reducibility among Combinatorial Problems, Complexity of Computer Computations[M]. New York, USA, Plenum Press, 1972: 85-103.
[25]	SCHULZ A. Correctness-proof of a greedy-algorithm for minimum vertex cover of a tree[OL]. http.//cs.stakexchange. com, 2013.
[26]	LESKOVEC J, KLEINBERG J, and FALOUTSOS C. Graph evolution: densification and shrink diameters[J]. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 1-41.
[27]	LESKOVEC J, LANG K, DASGUPTA A, et al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29-123.
[28]	MCAULEY J and LESKOVEC J. Learning to discover social circles in ego networks[C]. Proceedings of the 26th Annal Conference on Information Processing Systems, Lake Tahoe, NeVada, USA, 2012: 539-547.