基于最小點覆蓋和反饋點集的社交網(wǎng)絡影響最大化算法

許宇光; 潘驚治; 謝惠揚

doi:10.11999/IEIT160019

基于最小點覆蓋和反饋點集的社交網(wǎng)絡影響最大化算法

doi: 10.11999/IEIT160019

1.
(北京大學信息科學技術學院北京 100871) ②(北京林業(yè)大學理學院北京 100083)

基金項目:

國家自然科學基金(61370193)

計量
- 文章訪問數(shù): 1580
- HTML全文瀏覽量: 211
- PDF下載量: 777
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2016-01-05
- 修回日期: 2016-02-26
- 刊出日期: 2016-04-19

Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network

1.
(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China)
2.
(College of Science, Beijing Forestry University, Beijing 100083, China)

Funds:

The National Natural Science Foundation of China (61370193)

摘要

摘要: 社交網(wǎng)絡中的影響最大化問題是指在特定的傳播模型下，如何尋找k個最具影響力的節(jié)點使得在該模型下社交網(wǎng)絡中被影響的節(jié)點最多，信息傳播的范圍最廣。該問題是一個優(yōu)化問題，并且已經(jīng)被證明是NP-難的?？紤]到圖的最小點覆蓋和反饋點集中的頂點對圖的連通性影響較大，該文提出一種基于最小點覆蓋和反饋點集的社交網(wǎng)絡影響最大化算法(Minimum Vertex Covering and Feedback Vertex Set, MVCFVS)，并給出了具體的仿真實驗和分析。實驗結果表明，與最新的算法比較，該算法得到的節(jié)點集在多種模型下都具有優(yōu)異的傳播效果，例如在獨立級聯(lián)模型和加權級聯(lián)模型中超過當前最好的算法，并且還具有更快的收斂速度。
- 社交網(wǎng)絡 /
- 影響最大化 /
- 傳播模型 /
- 最小點覆蓋 /
- 反饋點集
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.
- Social network /
- Influence maximization /
- Diffusion models /
- Minimum vertex covering /
- Feedback vertex set

HTML全文

參考文獻(28)

WATTS D J and STROGATZ S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442.

BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

ZOU F, WILLSON J, ZHANG Z, et al. Fast information propagation in social networks[J]. Discrete Mathematics Algorithms Applications, 2010, 2(1): 125-141.

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.

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.

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.

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.

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.

KARP R M. Reducibility among Combinatorial Problems, Complexity of Computer Computations[M]. New York, USA, Plenum Press, 1972: 85-103.

SCHULZ A. Correctness-proof of a greedy-algorithm for minimum vertex cover of a tree[OL]. http.//cs.stakexchange. com, 2013.

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.

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.

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.

施引文獻

資源附件(0)

訪問統(tǒng)計