Abstract
This paper proposes a method for solving influence maximization problem in a dynamic network. In our method, a node that increases its influence most will be searched and it is added to the seed nodes incrementally. Since exact computation of influence of a node is #P-Hard, we employ heuristics for approximate computation. The results of our experiments show that our method is more effective than the methods based on centralities for dynamic networks, especially when the networks exhibit community structures.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008(10), P10008 (2008)
Berger-Wolf, T.Y.: Maximizing the extent of spread in a dynamic network. DIMACS Technical Report 2007-20, 10 pages (2007)
Bai, W.-J., Zhou, T., Wang, B.-H.: Immunization of susceptible–infected model on scale-free networks. Physica A: Statistical Mechanics and its Applications 384(2), 656–662 (2007)
Cheng, S., Shen, H., Huang, J., Zhang, G., Cheng, X.: Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In: Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management, pp. 509–518 (2013)
Chen, W., 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, pp. 1029–1038 (2010)
Grindrod, P., Parsons, M.C., Higham, D.J., Estrada, E.: Communicability across evolving networks. Physical Review E 83(4), 046120 (2011)
Holme, P., Saramäki, J.: Temporal networks. Physics Reports 519(3), 97–125 (2012)
Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J.-F., Van den Broeck, W.: What’s in a crowd? analysis of face-to-face behavioral networks. Journal of Theoretical Biology 271(1), 166–180 (2011)
Jung, K., Heo, W., Chen, W.: Irie: Scalable and robust influence maximization in social networks. In: ICDM, pp. 918–923 (2012)
Jo, H.-H., Pan, R.K., Kaski, K.: Emergence of bursts and communities in evolving weighted networks. PloS One 6(8), e22687 (2011)
Jiang, Q., Song, G., Cong, G., Wang, Y., Si, W., Xie, K.: Simulated annealing based influence maximization in social networks. In: AAAI, pp. 127–132 (2011)
Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18(1), 39–43 (1953)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)
Newman, M.E.J.: Modularity and community structure in networks. Proceedings of the National Academy of Sciences 103(23), 8577–8582 (2006)
Peyrard, N., Sabbadin, R.: Evaluation of the expected size of a sir epidemics on a graph. UBIAT Resarch Report, RR-2012-1 (2012)
Vanhems, P., Barrat, A., Cattuto, C., Pinton, J.-F., Khanafer, N., Régis, C., Kim, B.-A., Comte, B., Voirin, N.: Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PloS One 8(9), 73970 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Osawa, S., Murata, T. (2015). Selecting Seed Nodes for Influence Maximization in Dynamic Networks. In: Mangioni, G., Simini, F., Uzzo, S., Wang, D. (eds) Complex Networks VI. Studies in Computational Intelligence, vol 597. Springer, Cham. https://doi.org/10.1007/978-3-319-16112-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-16112-9_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16111-2
Online ISBN: 978-3-319-16112-9
eBook Packages: EngineeringEngineering (R0)