On the shoulders of giants: incremental influence maximization in evolving social networks. (English) Zbl 1377.91144
Summary: Influence maximization problem aims to identify the most influential individuals so as to help in developing effective viral marketing strategies over social networks. Previous studies mainly focus on designing efficient algorithms or heuristics on a static social network. As a matter of fact, real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time. In this paper, we propose an incremental approach, IncInf, which can efficiently locate the top-\(K\) influential individuals in evolving social networks based on previous information instead of calculation from scratch. In particular, IncInf quantitatively analyzes the influence spread changes of nodes by localizing the impact of topology evolution to only local regions, and a pruning strategy is further proposed to narrow the search space into nodes experiencing major increases or with high degrees. To evaluate the efficiency and effectiveness, we carried out extensive experiments on real-world dynamic social networks: Facebook, NetHEPT, and Flickr. Experimental results demonstrate that, compared with the state-of-the-art static algorithm, IncInf achieves remarkable speedup in execution time while maintaining matching performance in terms of influence spread.
Keywords:
incremental influence maximization; evolving social networks; effective viral marketing strategiesSoftware:
CELF++References:
| [1] | 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 ’01), ACM Press |
| [2] | Twitter 2012 Facts and Figures, 2012, http://www.website-monitoring.com/blog/2012/11/07/ |
| [3] | 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 ’09), ACM · doi:10.1145/1557019.1557047 |
| [4] | Wang, C.; Chen, W.; Wang, Y., Scalable influence maximization for independent cascade model in large-scale social networks, Data Mining and Knowledge Discovery, 25, 3, 545-576 (2012) · Zbl 1260.91219 · doi:10.1007/s10618-012-0262-1 |
| [5] | Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; Vanbriesen, J.; Glance, N., Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’07) · doi:10.1145/1281192.1281239 |
| [6] | Liu, X.; Li, S.; Liao, X.; Wang, L.; Wu, Q., In-Time Estimation for Influence Maximization in Large-Scale Social Networks, Proceedings of the ACM EuroSys Workshop on Social Network Systems |
| [7] | Barabasi, A.-L.; Albert, R., Emergence of scaling in random networks, American Association for the Advancement of Science. Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [8] | Liu, X.; Liao, X.; Li, S.; Lin, B., Towards efficient influence maximization for evolving social networks, Proceedings of the 18th Asia Pacific Web Conference |
| [9] | Tang, Y.; Shi, Y.; Xiao, X., Influence maximization in near-linear time: a martingale approach, Proceedings of the ACM SIGMOD International Conference on Management of Data, (SIGMOD ’15) · doi:10.1145/2723372.2723734 |
| [10] | Wang, Y.; Cong, G.; Song, G.; Xie, K., Community-based Greedy algorithm for mining top-K influential nodes in mobile social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’10), ACM · doi:10.1145/1835804.1835935 |
| [11] | Goyal, A.; Lu, W.; Lakshmanan, L. V. S., CELF++: optimizing the greedy algorithm for influence maximization in social networks, Proceedings of the 20th International Conference Companion on World Wide Web, (WWW ’11) · doi:10.1145/1963192.1963217 |
| [12] | Jung, K.; Heo, W.; Chen, W., IRIE: A Scalable Influence Maximization Algorithm for Independent Cascade Model and Its Extensions, https://arxiv.org/abs/1111.4795 |
| [13] | Liu, X.; Li, M.; Li, S.; Peng, S.; Liao, X.; Lu, X., IMGPU: GPU-accelerated influence maximization in large-scale social networks, IEEE Transactions on Parallel and Distributed Systems, 25, 1, 136-145 (2014) · doi:10.1109/TPDS.2013.41 |
| [14] | Chen, Y.-C.; Zhu, W.-Y.; Peng, W.-C.; Lee, W.-C.; Lee, S.-Y., CIM: community-based influence maximization in social networks, ACM Transactions on Intelligent Systems and Technology, 5, 2, article no. 25 (2014) · doi:10.1145/2532549 |
| [15] | Wang, X.-G., An algorithm for critical nodes problem in social networks based on owen value, The Scientific World Journal, 2014 (2014) · doi:10.1155/2014/414717 |
| [16] | Lu, Z.; Zhang, W.; Wu, W.; Kim, J.; Fu, B., The complexity of influence maximization problem in the deterministic linear threshold model, Journal of Combinatorial Optimization, 24, 3, 374-378 (2012) · Zbl 1261.91041 · doi:10.1007/s10878-011-9393-3 |
| [17] | Lu, Z.; Fan, L.; Wu, W.; Thuraisingham, B.; Yang, K., Efficient influence spread estimation for influence maximization under the linear threshold model, Computational Social Networks, 1, 1 (2014) |
| [18] | Nguyen, H.; Zheng, R., On budgeted influence maximization in social networks, IEEE Journal on Selected Areas in Communications, 31, 6, 1084-1094 (2013) · doi:10.1109/JSAC.2013.130610 |
| [19] | Han, M.; Yan, M.; Cai, Z.; Li, Y., An exploration of broader influence maximization in timeliness networks with opportunistic selection, Journal of Network and Computer Applications, 63, 39-49 (2016) · doi:10.1016/j.jnca.2016.01.004 |
| [20] | Liu, B.; Cong, G.; Zeng, Y.; Xu, D.; Chee, Y. M., Influence spreading path and its application to the time constrained social influence maximization problem and beyond, IEEE Transactions on Knowledge and Data Engineering, 26, 8, 1904-1917 (2014) · doi:10.1109/TKDE.2013.106 |
| [21] | Pei, S.; Teng, X.; Shaman, J.; Morone, F.; Makse, H. A., Efficient collective influence maximization in cascading processes with first-order transitions, Scientific Reports, 7 (2017) · doi:10.1038/srep45240 |
| [22] | Habiba, Y. Y.; Berger-Wolf, T. Y.; Saia, J., Finding Spread Blockers in Dynamic Networks, Advances in Social Network Mining and Analysis. Advances in Social Network Mining and Analysis, Lecture Notes in Computer Science, 5498, 55-76 (2010), Berlin, Germany: Springer, Berlin, Germany · doi:10.1007/978-3-642-14929-0_4 |
| [23] | Michalski, R.; Kajdanowicz, T.; Bródka, P.; Kazienko, P., Seed selection for spread of influence in social networks: Temporal vs. static approach, New Generation Computing, 32, 3-4, 213-235 (2014) · doi:10.1007/s00354-014-0402-9 |
| [24] | Chen, W.; Lu, W.; Zhang, N., Time-critical influence maximization in social networks with time-delayed diffusion process, Proceedings of the Proceedings of the 26th Conference on Artificial Intelligence |
| [25] | Gomez-Rodriguez, M.; Scholkopf, B., Influence Maximization in Continuous Time Diffusion Networks, Proceedings of the 29th International Conference on Machine Learning |
| [26] | Aggarwal, C.; Lin, S.; Yu, P. S., On influential node discovery in dynamic social networks, Proceedings of the 12th SIAM International Conference on Data Mining, (SDM ’12) |
| [27] | Zhuang, H.; Sun, Y.; Tang, J.; Zhang, J.; Sun, X., Influence maximization in dynamic social networks, Proceedings of the 13th IEEE International Conference on Data Mining, ICDM 2013 · doi:10.1109/ICDM.2013.145 |
| [28] | Tong, G.; Wu, W.; Tang, S.; Du, D.-Z., Adaptive Influence Maximization in Dynamic Social Networks, IEEE/ACM Transactions on Networking, 25, 1, 112-125 (2017) · doi:10.1109/TNET.2016.2563397 |
| [29] | Kempe, D.; Kleinberg, J.; Tardos, E., Maximizing the spread of influence through a social network, Proceedings of the Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining |
| [30] | Richardson, M.; Domingos, P., Mining knowledge-sharing sites for viral marketing, Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’02), ACM · doi:10.1145/775047.775057 |
| [31] | Chen, Y.-C.; Peng, W.-C.; Lee, S.-Y., Efficient algorithms for influence maximization in social networks, Knowledge and Information Systems, 33, 3, 577-601 (2012) · doi:10.1007/s10115-012-0540-7 |
| [32] | Heidari, M.; Asadpour, M.; Faili, H., SMG: fast scalable greedy algorithm for influence maximization in social networks, Physica A: Statistical Mechanics and its Applications, 420, 124-133 (2015) · doi:10.1016/j.physa.2014.10.088 |
| [33] | Morone, F.; Makse, H. A., Influence maximization in complex networks through optimal percolation, Nature, 524, 7563, 65-68 (2015) · doi:10.1038/nature14604 |
| [34] | Song, G.; Zhou, X.; Wang, Y.; Xie, K., Influence maximization on large-scale mobile social network: a divide-and-conquer method, IEEE Transactions on Parallel and Distributed Systems, 26, 5, 1379-1392 (2015) · doi:10.1109/tpds.2014.2320515 |
| [35] | Zhou, C.; Zhang, P.; Zang, W.; Guo, L., On the upper bounds of spread for greedy algorithms in social network influence maximization, IEEE Transactions on Knowledge and Data Engineering, 27, 10, 2770-2783 (2015) · doi:10.1109/TKDE.2015.2419659 |
| [36] | Capocci, A.; Servedio, V. D. P.; Colaiori, F.; Buriol, L. S.; Donato, D.; Leonardi, S.; Caldarelli, G., Preferential attachment in the growth of social networks: The internet encyclopedia Wikipedia, Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 74, 3 (2006) · doi:10.1103/PhysRevE.74.036116 |
| [37] | Leskovec, J.; Backstrom, L.; Kumar, R.; Tomkins, A., Microscopic evolution of social networks, Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2008 · doi:10.1145/1401890.1401948 |
| [38] | Easley, D.; Kleinberg, J., Networks, Crowds, and Markets: Reasoning about a Highly Connected World (2010), Cambridge, Mass, USA: Cambridge University Press, Cambridge, Mass, USA · Zbl 1205.91007 · doi:10.1017/cbo9780511761942 |
| [39] | CORONA, V. P., Memory, Monsters, and Lady Gaga, The Journal of Popular Culture, 46, 4, 725-744 (2013) · doi:10.1111/j.1540-5931.2011.00809.x |
| [40] | Viswanath, B.; Mislove, A.; Cha, M.; Gummadi, K. P., On the evolution of user interaction in Facebook, Proceedings of the 2nd ACM SIGCOMM Workshop on Online Social Networks · doi:10.1145/1592665.1592675 |
| [41] | ArXiv NetHEPT dataset, http://www.cs.cornell.edu/projects/kddcup/datasets.html |
| [42] | Mislove, A.; Koppula, H. S.; Gummadi, K. P.; Druschel, P.; Bhattacharjee, B., Growth of the flickr social network, Proceedings of the 1st ACM SIGCOMM Workshop on Social Networks (WOSN ’08), ACM · doi:10.1145/1397735.1397742 |
| [43] | Tang, J.; Sun, J.; Wang, C.; Yang, Z., Social influence analysis in large-scale networks, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’09 · doi:10.1145/1557019.1557108 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
