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

Anthony Bonato 1 Marc Lozier 1 Dieter Mitsche 2 Xavier Pérez-Giménez 3 Pawel Pralat 3
1 Department of Mathematics (Toronto, Ryerson Uni.)
2 UNS - Université Nice Sophia Antipolis
3 Ryerson University (Toronto)
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.
Type de document :
Communication dans un congrès
Proceedings of the 12th Conference on Theory and Applications of Models of Computation (TAMC 2015), May 2015, Singapour, Singapore. Proceedings of the 12th Conference on Theory and Applications of Models of Computation (TAMC 2015), Lecture Notes in Computer Science 9076, Springer, 2015, 150-163. pp.14, 2015, Lecture Notes in Computer Science 9076, Springer, 2015, 150-163. 〈10.1007/978-3-319-17142-5_14〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01291967
Contributeur : Dieter Mitsche <>
Soumis le : mardi 22 mars 2016 - 13:04:51
Dernière modification le : jeudi 11 janvier 2018 - 16:50:44
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 22:47:40

Fichier

2015_Domination-TAMC.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNICE | INSMI | UNIV-COTEDAZUR

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. Proceedings of the 12th Conference on Theory and Applications of Models of Computation (TAMC 2015), Lecture Notes in Computer Science 9076, Springer, 2015, 150-163. pp.14, 2015, Lecture Notes in Computer Science 9076, Springer, 2015, 150-163. 〈10.1007/978-3-319-17142-5_14〉. 〈hal-01291967〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

41

Téléchargements de fichiers

46

Contact


archive-ouverte@inria.fr