Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 13973))
Included in the following conference series:
545Accesses
Abstract
Graph burning is a deterministic, discrete-time process that can be used to model how influence or contagion spreads in a graph. In the graph burning process, each node starts as dormant, and becomes informed/burned over time; when a node is burned, it remains burned until the end of the process. In each round, one can burn a new node (source of fire) in the network. Once a node is burned in roundt, in round\(t+1\), each of its dormant neighbors becomes burned. The process ends when all nodes are burned; the goal is to minimize the number of rounds. We study a variation of graph burning in order to model spreading processes in community-based networks. With respect to a specific piece of information, a community issatisfied when this information reaches at least a prescribed number of its members. Specifically, we consider the problem of identifying a minimum length sequence of nodes that, according to a graph burning process, allows to satisfy all the communities of the network. We investigate this NP-hard problem from an approximation point of view, showing both a lower bound and a matching upper bound. We also investigate the case when the number of communities is constant and show how to solve the problem with a constant approximation factor. Moreover, we consider the problem of maximizing the number of satisfied groups, given a budgetk on the number of rounds.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 8579
- Price includes VAT (Japan)
- Softcover Book
- JPY 10724
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For any integera, we denote by [a] the set {1, 2, ..., a}.
References
Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theor. Comp. Sci.411(44–46), 4017–4022 (2010)
Arora, S., Lund, C.: Hardness of approximation. In: Hochbaum, Ed. D. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 399–446 PWS Publishers (1995)
Bandyapadhyay, S., Inamdar, T., Pai, S., Varadarajan, K.: A constant approximation for colorful k-center.arXiv:1907.08906v1 (2019)
Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discrete Optim.8(1), 87–96 (2011)
Bonato, A.: A survey of graph burning. Contr. Discret. Math.16, 185–197 (2021)
Bonato, A., Kamali, S.: Approximation algorithms for graph burning. In: Gopal, T.V., Watada, J. (eds.) TAMC 2019. LNCS, vol. 11436, pp. 74–92. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-14812-6_6
Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX/RANDOM -2004. LNCS, vol. 3122, pp. 72–83. Springer, Heidelberg (2004).https://doi.org/10.1007/978-3-540-27821-4_7
Chen, W., Lakshmanan, L.V.S., Castillo, C.: Information and influence propagation in social networks. In: Synthesis Lectures on Data Management, vol. 5.4 (2013)
Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant thresholds can make target set selection tractable. Theory Comput. Syst.55(1), 61–83 (2014).https://doi.org/10.1007/s00224-013-9499-3
Cicalese, F., Cordasco, G., Gargano, L., Milanic, M., Vaccaro, U.: Latency-bounded target set selection in social networks. Theor. Comp. Sci.535, 1–15 (2014)
Coja-Oghlan, A., Feige, U., Krivelevich, M., Reichman, D.: Contagious sets in expanders. In: Proceedings of SODA, pp. 1953–1987 (2015)
Cordasco, G., Gargano, L., Rescigno, A.A.: Influence propagation over large scale social networks. In: Proceedings of ASONAM, pp. 1531–1538 (2015)
Cicalese, F., Cordasco, G., Gargano, L., Milanic, M., Peters, J., Vaccaro, U.: Spread of influence in weighted networks under time and budget constraints. Theor. Comp. Sci.586, 40–58 (2015)
Cordasco, G., Gargano, L., Rescigno, A.A.: On finding small sets that influence large networks. Soc. Netw. Anal. Min.6, 1–20 (2016)
Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks: algorithms and complexity. Networks71(4), 346–357 (2018)
Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: Discovering small target sets in social networks: a fast and effective algorithm. Algorithmica80, 1804–1833 (2018).https://doi.org/10.1007/s00453-017-0390-5
Cordasco, G., Gargano, L., Rescigno, A.A.: Active influence spreading in social networks. Theor. Comp. Sci.764, 15–29 (2019)
Cordasco, G., et al.: Whom to befriend to influence people. Theor. Comp. Sci.810, 26–42 (2020)
Cordasco, G., Gargano, L., Peters, J.G., Rescigno, A.A., Vaccaro, U.: Fast and frugal targeting with incentives. Theor. Comp. Sci.812, 62–79 (2020)
Dinh, T.N., Zhang, H., Nguyen, D.T., Thai, M.T.: Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE Trans. Net.22, 2001–2011 (2014)
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected world. Cambridge University Press, Cambridge (2010)
Gargano, L., Hell, P., Peters, J.G., Vaccaro, U.: Influence diffusion in social networks under time window constraints. Theor. Comp. Sci.584(C), 53–66 (2015)
Jia, X., Sheth, K., Svensson, O.: Fair colorful k-center clustering.arXiv:2007.04059v1 (2020)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of KDD 2003 (2003)
Lev, B., Soyster, A.L.: Integer programming with bounded variables via canonical separation. J. Oper. Res. Soc.29(5), 477–488 (1978)
Reddy, T.V.T., Rangan, C.P.: Variants of spreading messages. J. Graph Algorithms Appl.15(5), 683–699 (2011)
Shakarian, P., Eyre, S., Paulo, D.: A scalable heuristic for viral marketing under the tipping model. Soc. Netw. Anal. Min.3(4), 1225–1248 (2013).https://doi.org/10.1007/s13278-013-0135-7
Zhu, J., Ghosh, S., Wu, W.: Group influence maximization problem in social networks. IEEE Trans. Comput. Soc. Syst.6(6), 1156–1164 (2019)
Author information
Authors and Affiliations
Department of Psychology, University of Campania “L.Vanvitelli”, Caserta, Italy
Gennaro Cordasco
Department of Computer Science, University of Salerno, Fisciano, Italy
Luisa Gargano & Adele A. Rescigno
- Gennaro Cordasco
You can also search for this author inPubMed Google Scholar
- Luisa Gargano
You can also search for this author inPubMed Google Scholar
- Adele A. Rescigno
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toGennaro Cordasco.
Editor information
Editors and Affiliations
National Yang Ming Chiao Tung University, Hsinchu, Taiwan
Chun-Cheng Lin
National Yang Ming Chiao Tung University, Hsinchu, Taiwan
Bertrand M. T. Lin
University of Perugia, Perugia, Italy
Giuseppe Liotta
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cordasco, G., Gargano, L., Rescigno, A.A. (2023). Groups Burning: Analyzing Spreading Processes in Community-Based Networks. In: Lin, CC., Lin, B.M.T., Liotta, G. (eds) WALCOM: Algorithms and Computation. WALCOM 2023. Lecture Notes in Computer Science, vol 13973. Springer, Cham. https://doi.org/10.1007/978-3-031-27051-2_28
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-27050-5
Online ISBN:978-3-031-27051-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative