Abstract
We introduce a new graph parameter called the burning number, inspired by contact processes on graphs such as graph bootstrap percolation, and graph searching paradigms such as Firefighter. The burning number measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We provide a number of properties of the burning number, including characterizations and bounds. The burning number is computed for several graph classes, and is derived for the graphs generated by the Iterated Local Transitivity model for social networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Prałat, P., Wormald, N.: Cleaning regular graphs with brushes. SIAM Journal on Discrete Mathematics 23, 233–250 (2008)
Balogh, J., Bollobás, B., Morris, R.: Graph bootstrap percolation (preprint 2014)
Banerjee, S., Das, A., Gopalan, A., Shakkottai, S.: Epidemic spreading with external agents. In: Proceedings of IEEE Infocom (2011)
Barghi, A., Winkler, P.: Firefighting on a random geometric graph. Random Structures and Algorithms (accepted)
Bonato, A., Hadi, N., Horn, P., Prałat, P., Wang, C.: Models of on-line social networks. Internet Mathematics 6, 285–313 (2011)
Bonato, A., Janssen, J., Roshanbin, E.: Burning a graph is hard (preprint 2014)U
Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. American Mathematical Society, Providence (2011)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the 7th International Conference on Knowledge Discovery and Data Mining (KDD) (2001)
Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Mathematics 307, 2094–2105 (2007)
Finbow, S., MacGillivray, G.: The Firefighter problem: a survey of results, directions and questions. Australasian Journal of Combinatorics 43, 57–77 (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W.H (1979)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th International Conference on Knowledge scovery and Data Mining (KDD) (2003)
Kempe, David, Kleinberg, Jon M., Tardos, Éva: Influential Nodes in a Diffusion Model for Social Networks. In: Caires, Lu\’ıs, Italiano, Giuseppe F., Monteiro, Lu\’ıs, Palamidessi, Catuscia, Yung, Moti (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1127–1138. Springer, Heidelberg (2005)
Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: Proc. 32nd ACM Symp. Theory of Computing (2000)
Kramer, A.D.I., Guillory, J.E., Hancock, J.T.: Experimental evidence of massive-scale emotional contagion through social networks. Proceedings of the National Academy of Sciences 111, 8788–8790 (2014)
Meir, A., Moon, J.W.: Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics 61, 225–233 (1975)
Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Proceedings of 39th Annual ACM Symposium on Theory of Computing (STOC) (2007)
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the 8th International Conference on Knowledge scovery and Data Mining (KDD) (2002)
Small, L., Mason, O.: Information diffusion on the iterated local transitivity model of online social networks. Discrete Applied Mathematics 161, 1338–1344 (2013)
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bonato, A., Janssen, J., Roshanbin, E. (2014). Burning a Graph as a Model of Social Contagion. In: Bonato, A., Graham, F., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2014. Lecture Notes in Computer Science(), vol 8882. Springer, Cham. https://doi.org/10.1007/978-3-319-13123-8_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-13123-8_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13122-1
Online ISBN: 978-3-319-13123-8
eBook Packages: Computer ScienceComputer Science (R0)