Top

Hint

Swipe to navigate through the chapters of this book

Published in:

Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Entropy-Based Measure for Influence Maximization in Temporal Networks

Authors : Radosław Michalski, Jarosław Jankowski, Patryk Pazura

Published in: Computational Science – ICCS 2020

Publisher: Springer International Publishing

Abstract

The challenge of influence maximization in social networks is tackled in many settings and scenarios. However, the most explored variant is looking at how to choose a seed set of a given size, that maximizes the number of activated nodes for selected model of social influence. This has been studied mostly in the area of static networks, yet other kinds of networks, such as multilayer or temporal ones, are also in the scope of recent research. In this work we propose and evaluate the measure based on entropy, that investigates how the neighbourhood of nodes varies over time, and based on that and their activity ranks, the nodes as possible candidates for seeds are selected. This measure applied for temporal networks intends to favor nodes that vary their neighbourhood highly and, thanks to that, are good spreaders for certain influence models. The results demonstrate that for the Independent Cascade Model of social influence the introduced entropy-based metric outperforms typical seed selection heuristics for temporal networks. Moreover, compared to some other heuristics, it is fast to compute, thus can be used for fast-varying temporal networks.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt 90 Tage mit der neuen Mini-Lizenz testen!

inform now

previous chapter Mapping the Port Influence Diffusion Patterns: A Case Study of Rotterdam, Antwerp and Singapore

next chapter Evaluation of the Costs of Delayed Campaigns for Limiting the Spread of Negative Content, Panic and Rumours in Complex Networks

Barabási, A.L., et al.: Network Science. Cambridge University Press, Cambridge (2016) MATH

Bhowmick, A.K., Gueuning, M., Delvenne, J.C., Lambiotte, R., Mitra, B.: Temporal sequence of retweets help to detect influential nodes in social networks. IEEE Trans. Comput. Soc. Syst. 6(3), 441–455 (2019) CrossRef

Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., Scott, J.: Impact of human mobility on opportunistic forwarding algorithms. IEEE Trans. Mob. Comput. 6(6), 606–620 (2007) CrossRef

Erlandsson, F., Bródka, P., Borg, A.: Seed selection for information cascade in multilayer networks. In: Cherifi, C., Cherifi, H., Karsai, M., Musolesi, M. (eds.) COMPLEX NETWORKS 2017 2017. SCI, vol. 689, pp. 426–436. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72150-7_35 CrossRef

Friedkin, N.E., Cook, K.S.: Peer group influence. Soc. Methods Res. 19(1), 122–143 (1990) CrossRef

Friedkin, N.E., Johnsen, E.C.: Social Influence Network Theory: A sociological Examination of Small Group Dynamics, vol. 33. Cambridge University Press, Cambridge (2011) CrossRef

Goldenberg, J., Libai, B., Muller, E.: Talk of the network: a complex systems look at the underlying process of word-of-mouth. Mark. Lett. 12(3), 211–223 (2001). https://doi.org/10.1023/A:1011122126881 CrossRef

Goyal, A., Bonchi, F., Lakshmanan, L.V.: Learning influence probabilities in social networks. In: Proceedings of the third ACM international conference on Web search and data mining, pp. 241–250 (2010)

Goyal, A., Lu, W., Lakshmanan, L.V.: Celf++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on World wide web, pp. 47–48. ACM (2011)

10.

Hinz, O., Skiera, B., Barrot, C., Becker, J.U.: Seeding strategies for viral marketing: an empirical comparison. J. Mark. 75(6), 55–71 (2011) CrossRef

11.

Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012) CrossRef

12.

Huang, D.W., Yu, Z.G.: Dynamic-sensitive centrality of nodes in temporal networks. Sci. Rep. 7, 41454 (2017) CrossRef

13.

Jankowski, J., Michalski, R., Bródka, P.: A multilayer network dataset of interaction and influence spreading in a virtual world. Sci. Data 4, 170144 (2017) CrossRef

14.

Jankowski, J., Michalski, R., Kazienko, P.: Compensatory seeding in networks with varying avaliability of nodes. In: 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013, pp. 1242–1249. IEEE (2013)

15.

Jankowski, J., et al.: Probing limits of information spread with sequential seeding. Sci. Rep. 8(1), 13996 (2018) CrossRef

16.

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)

17.

Kitsak, M., et al.: Identification of influential spreaders in complex networks. Nat. Phys. 6(11), 888 (2010) CrossRef

18.

Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J.P., Moreno, Y., Porter, M.A.: Multilayer networks. J. Complex Netw. 2(3), 203–271 (2014) CrossRef

19.

Kulisiewicz, M., Kazienko, P., Szymanski, B.K., Michalski, R.: Entropy measures of human communication dynamics. Sci. Rep. 8(1), 1–8 (2018) CrossRef

20.

Michalski, R., Kajdanowicz, T., Bródka, P., Kazienko, P.: Seed selection for spread of influence in social networks: temporal vs static approach. New Gener. Comput. 32(3–4), 213–235 (2014) CrossRef

21.

Michalski, R., Kazienko, P.: Maximizing social influence in real-world networks—the state of the art and current challenges. In: Król, D., Fay, D., Gabryś, B. (eds.) Propagation Phenomena in Real World Networks. ISRL, vol. 85, pp. 329–359. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15916-4_14 CrossRef

22.

Michalski, R., Kazienko, P., Jankowski, J.: Convince a dozen more and succeed-the influence in multi-layered social networks. In: 2013 International Conference on Signal-Image Technology & Internet-Based Systems, pp. 499–505. IEEE (2013)

23.

Michalski, R., Palus, S., Bródka, P., Kazienko, P., Juszczyszyn, K.: Modelling social network evolution. In: Datta, A., Shulman, S., Zheng, B., Lin, S.-D., Sun, A., Lim, E.-P. (eds.) SocInfo 2011. LNCS, vol. 6984, pp. 283–286. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24704-0_30 CrossRef

24.

Nurek, M., Michalski, R.: Combining machine learning and social network analysis to reveal the organizational structures. Appl. Sci. 10(5), 1699 (2020) CrossRef

25.

Pan, R.K., Saramäki, J.: Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E 84(1), 016105 (2011) CrossRef

26.

Pfitzner, R., Scholtes, I., Garas, A., Tessone, C.J., Schweitzer, F.: Betweenness preference: quantifying correlations in the topological dynamics of temporal networks. Phys. Rev. Lett. 110(19), 198701 (2013) CrossRef

27.

Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27(3), 379–423 (1948) MathSciNetCrossRef

28.

Takaguchi, T., Nakamura, M., Sato, N., Yano, K., Masuda, N.: Predictability of conversation partners. Phys. Rev. X 1(1), 011008 (2011)

29.

Takaguchi, T., Yano, Y., Yoshida, Y.: Coverage centralities for temporal networks. Eur. Phys. J. B 89(2), 1–11 (2016). https://doi.org/10.1140/epjb/e2016-60498-7 CrossRef

30.

Tang, J., Scellato, S., Musolesi, M., Mascolo, C., Latora, V.: Small-world behavior in time-varying graphs. Phys. Rev. E 81(5), 055101 (2010) CrossRef

31.

Taylor, D., Myers, S.A., Clauset, A., Porter, M.A., Mucha, P.J.: Eigenvector-based centrality measures for temporal networks. Multiscale Model. Simul. 15(1), 537–574 (2017) MathSciNetCrossRef

32.

Wang, X., Zhang, X., Zhao, C., Yi, D.: Maximizing the spread of influence via generalized degree discount. PLoS ONE 11(10), e0164393 (2016) CrossRef

33.

Weng, L., Flammini, A., Vespignani, A., Menczer, F.: Competition among memes in a world with limited attention. Sci. Rep. 2, 335 (2012) CrossRef

34.

Weskida, M., Michalski, R.: Evolutionary algorithm for seed selection in social influence process. In: 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM, pp. 1189–1196. IEEE (2016)

35.

Weskida, M., Michalski, R.: Finding influentials in social networks using evolutionary algorithm. J. Comput. Sci. 31, 77–85 (2019) MathSciNetCrossRef

36.

Zhang, J.X., Chen, D.B., Dong, Q., Zhao, Z.D.: Identifying a set of influential spreaders in complex networks. Sci. Rep. 6, 27823 (2016) CrossRef

37.

Zhao, K., Karsai, M., Bianconi, G.: Models, entropy and information of temporal social networks. In: Holme, P., Saramäki, J. (eds.) Temporal Networks. Understanding Complex Systems, pp. 95–117. Springer, Heidelberg (2013) CrossRef

38.

Zhao, Y., Li, S., Jin, F.: Identification of influential nodes in social networks with community structure based on label propagation. Neurocomputing 210, 34–44 (2016) CrossRef

39.

Zhuang, H., Sun, Y., Tang, J., Zhang, J., Sun, X.: Influence maximization in dynamic social networks. In: 2013 IEEE 13th International Conference on Data Mining, pp. 1313–1318. IEEE (2013)

Title: Entropy-Based Measure for Influence Maximization in Temporal Networks
Authors: Radosław Michalski
Jarosław Jankowski
Patryk Pazura
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2020
Print ISBN: 978-3-030-50422-9

Electronic ISBN: 978-3-030-50423-6

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-50423-6_21

Springer Professional

Hint

Swipe to navigate through the chapters of this book

Abstract

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"