Influence Maximization in Dynamic Social Networks and Graphs

Authors: Gkolfo I. Smani, Vasileios Megalooikonomou

Abstract:

Influence and influence diffusion have been studied extensively in social networks. However, most existing literature on this task are limited on static networks, ignoring the fact that the interactions between users change over time. In this paper, the problem of maximizing influence diffusion in dynamic social networks, i.e., the case of networks that change over time is studied. The DM algorithm is an extension of Matrix Influence (MATI) algorithm and solves the Influence Maximization (IM) problem in dynamic networks and is proposed under the Linear Threshold (LT) and Independent Cascade (IC) models. Experimental results show that our proposed algorithm achieves a diffusion performance better by 1.5 times than several state-of-the-art algorithms and comparable results in diffusion scale with the Greedy algorithm. Also, the proposed algorithm is 2.4 times faster than previous methods.

Keywords: Influence maximization, dynamic social networks, diffusion, social influence.

References:

[1] Borgs C., Brautbar M., Chayes J., and Lucier B., Maximizing social influence in nearly optimal time. In SODA, pp. 946-957, 2014.
[2] Chen S., Wang C., Wang Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining -KDD 2010, pp. 1029-1038, 2010.
[3] Chen S., Wang Y., Yang Y., Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining -KDD 2009, pp. 199-207, 2009.
[4] Goyal Amit, Wei Lu, and Laks V. S. Lakshmanan. “SIMPATH: An Efficient Algorithm for Influence Maximization Under the Linear Threshold Model.” In: ICDM. 2011.
[5] Habiba and Berger-Wolf TY. Maximizing the extent of spread in a dynamic network. DIMACS Technical Report, 2007.
[6] Kempe D., Kleinberg J., and Tardos E. Maximizing the spread of influence through a social network. In KDD, pp. 137-146, 2003.
[7] Li G., Chen S., Feng J., Tan K.-L., and Li W.-S. Efficient location-aware influence maximization. In SIGMOD, pp. 87-98, 2014.
[8] Li H., Bhowmick S. S., Sun A., and Cui J. Conformity-aware influence maximization in online social networks. The VLDB Journal, 24(1):117-141, 2015.
[9] Li Y., D. Zhang, and K.-L. Tan. Real-time targeted influence maximization for online advertisements. PVLDB, 8(10):1070-1081, 2015.
[10] Murata T., Koga H. Extended methods for influence maximization in dynamic networks. Comput Soc Netw 5, 8, 2018.
[11] Nguyen H. T., Thai M. T., and Dinh T. N. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In SIGMOD, pp. 695-710, 2016.
[12] Osawa S, Murata T. Selecting seed nodes for influence maximization in dynamic networks. In: Proceedings of the 6th workshop on complex networks (CompleNet 2015), studies in computational intelligence. Berlin: Springer; pp.91–8, 2015
[13] Rong-Hua Li, Jeffrey Xu Yu, and Rui Mao. “Efficient core maintenance in large dynamic graphs.” In: IEEE Transactions on Knowledge and Data Engineering 26.10, pp. 2453–2465, 2014.
[14] Rossi M., Shi B., Tziortziotis N., Malliaros F., Giatsidis C., Vazirgiannis M., MATI: An efficient algorithm for influence maximization in social networks. PLoS ONE. 13. 1. 10.1371/journal.pone.0206318, 2018.
[15] Tang Y., Shi Y., and Xiao X. Influence maximization in near-linear time: A martingale approach. In SIGMOD, pp. 1539-1554, 2015.
[16] Tang Y., Xiao X., and Shi Y. Influence maximization: near-optimal time complexity meets practical efficiency. In SIGMOD, pp. 75-86, 2014.
[17] Wang X., Zhang Y., Zhang W., and Lin X. Distance-aware influence maximization in geo-social network. In ICDE, pp. 1-12, 2016.
[18] http://networkrepository.com
[19] https://snap.stanford.edu/data
[20] http://www.sociopatterns.org