On some diffusion and spanning problems in configuration model

Kumar Gaurav 1
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Résumé : Un certain nombre de systèmes dans le monde réel, comprenant des agents interagissant, peut être utilement modélisé par des graphes, où les agents sont représentés par les sommets du graphe et les interactions par les arêtes. De tels systèmes peuvent être aussi divers et complexes que les réseaux sociaux (traditionnels ou virtuels), les réseaux d'interaction protéine-protéine, internet, réseaux de transport et les réseaux de prêts interbancaires. Une question importante qui se pose dans l'étude de ces réseaux est: dans quelle mesure, les statistiques locales d'un réseau déterminent sa topologie globale. Ce problème peut être approché par la construction d'un graphe aléatoire contraint d'avoir les mêmes statistiques locales que celles observées dans le graphe d'intérêt. Le modèle de configuration est un tel modèle de graphe aléatoire conçu de telle sorte qu'un sommet uniformément choisi présente une distribution de degré donnée. Il fournit le cadre sous-jacent à cette thèse. En premier lieu nous considérons un problème de propagation de l'influence sur le modèle de configuration, où chaque sommet peut être influencé par l'un de ses voisins, mais à son tour, il ne peut influencer qu'un sous-ensemble aléatoire de ses voisins. Notre modèle étendu est décrit par le degré total du sommet typique et le nombre de voisins il est capable d'influencer. Nous donnons une condition stricte sur la distribution conjointe de ces deux degrés, qui permet à l'influence de parvenir, avec une forte probabilité, à un ensemble non négligeable de sommets, essentiellement unique, appelé la composante géante influencée, à condition que le sommet de la source soit choisi à partir d'un ensemble de bons pionniers. Nous évaluons explicitement la taille relative asymptotique de la composant géante influencée, ainsi que de l'ensemble des bons pionniers, à condition qu'ils soient non-négligeable. Notre preuve utilise l'exploration conjointe du modèle de configuration et de la propagation de l'influence jusqu'au moment où une grande partie est influencée, une technique introduite dans Janson et Luczak (2008). Notre modèle peut être vu comme une généralisation de la percolation classique par arêtes ou par sites sur le modèle de configuration, avec la différence résultant de la conductivité orientée des arêtes dans notre modèle. Nous illustrons ces résultats en utilisant quelques exemples, en particulier, motivés par le marketing viral - un phénomène connu dans le contexte des réseaux sociaux…
Type de document :
Thèse
Dynamical Systems [math.DS]. Université Pierre et Marie Curie - Paris VI, 2016. English. 〈NNT : 2016PA066362〉
Liste complète des métadonnées

Littérature citée [54 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01400999
Contributeur : Abes Star <>
Soumis le : mercredi 1 mars 2017 - 11:38:23
Dernière modification le : samedi 7 juillet 2018 - 03:06:00
Document(s) archivé(s) le : mardi 30 mai 2017 - 16:03:12

Fichier

2016PA066362.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01400999, version 2

Collections

Citation

Kumar Gaurav. On some diffusion and spanning problems in configuration model. Dynamical Systems [math.DS]. Université Pierre et Marie Curie - Paris VI, 2016. English. 〈NNT : 2016PA066362〉. 〈tel-01400999v2〉

Partager

Métriques

Consultations de la notice

756

Téléchargements de fichiers

72