HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

The Domination Number of On-line Social Networks and Random Geometric Graphs

Abstract : We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously derived for the domination number of graphs generated by the memoryless geometric protean random graph model. We establish sublinear bounds for the domination number of graphs in the Facebook 100 data set, and these bounds are well-correlated with those predicted by the stochastic model. In addition, we derive the asymptotic value of the domination number in classical random geometric graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-01291967
Contributor : Dieter Mitsche Connect in order to contact the contributor
Submitted on : Tuesday, March 22, 2016 - 1:04:51 PM
Last modification on : Tuesday, December 7, 2021 - 4:04:35 PM
Long-term archiving on: : Sunday, November 13, 2016 - 10:47:40 PM

File

2015_Domination-TAMC.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Anthony Bonato, Marc Lozier, Dieter Mitsche, Xavier Pérez-Giménez, Pawel Pralat. The Domination Number of On-line Social Networks and Random Geometric Graphs. Proceedings of the 12th Conference on Theory and Applications of Models of Computation (TAMC 2015), May 2015, Singapour, Singapore. pp.14, ⟨10.1007/978-3-319-17142-5_14⟩. ⟨hal-01291967⟩

Share

Metrics

Record views

55

Files downloads

189