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

XU Yuguang; PAN Jingzhi; XIE Huiyang

doi:10.11999/IEIT160019

Volume 38 Issue 4

Apr. 2016

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2016 > 38(4): 795-802

XU Yuguang, PAN Jingzhi, XIE Huiyang. Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network[J]. Journal of Electronics & Information Technology, 2016, 38(4): 795-802. doi: 10.11999/IEIT160019

Citation:

XU Yuguang, PAN Jingzhi, XIE Huiyang. Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network[J]. Journal of Electronics & Information Technology, 2016, 38(4): 795-802. doi: 10.11999/IEIT160019

Citation:

PDF( 297 KB)

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

doi: 10.11999/IEIT160019 cstr: 32379.14.IEIT160019

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)

Received Date: 2016-01-05
Rev Recd Date: 2016-02-26
Publish Date: 2016-04-19

Abstract

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

FullText(HTML)

References(28)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views