Modèle de configuration douce - Soft configuration model

Science des réseaux
Théorie
Graphique Réseau complexe Contagion Petit monde Sans échelle Structure communautaire Percolation Évolution Contrôlabilité Dessin graphique Capital social Analyse des liens Optimisation La réciprocité Fermeture L'homophilie Transitivité Attachement préférentiel Théorie de l'équilibre Effet de réseau Influence sociale
Types de réseaux
Informatif (informatique) Télécommunication Transport Social Collaboration scientifique Biologique Neural artificiel Interdépendant Sémantique Spatial Dépendance Couler sur puce
Graphiques
traits Clique Composant Couper Cycle Structure de données Bord Boucle quartier Chemin Sommet Liste  / matrice d'adjacence Liste  / matrice d' incidence Les types Bipartite Achevée Dirigé Hyper Multi Aléatoire Pondéré
Métrique Algorithmes
Centralité Diplôme Entre les deux Proximité Classement Motif Clustering Répartition des diplômes Assortativité Distance Modularité Efficacité
Des modèles
Topologie Graphique aléatoire Erdős – Rényi Barabási – Albert Modèle de fitness Watts – Strogatz Aléatoire exponentiel (ERGM) Géométrique aléatoire (RGG) Hyperbolique (HGN) Hiérarchique Bloc stochastique Entropie maximale Configuration douce Benchmark LFR Dynamique Réseau booléen basé sur un agent Épidémie / SIR
Listes Catégories
Les sujets Logiciel Scientifiques du réseau Catégorie: Théorie des réseaux Catégorie: Théorie des graphes
v t e

En mathématiques appliquées, le modèle de configuration souple (SCM) est un modèle de graphe aléatoire soumis au principe d'entropie maximale sous contraintes sur l' espérance de la séquence en degrés des graphes échantillonnés . Alors que le modèle de configuration (CM) échantillonne uniformément des graphiques aléatoires d'une séquence de degrés spécifique, le SCM ne conserve que la séquence de degrés spécifiée en moyenne sur toutes les réalisations du réseau; en ce sens le SCM a des contraintes très assouplies par rapport à celles du CM (contraintes "douces" plutôt que "fortes"). Le SCM pour les graphes de taille a une probabilité non nulle d'échantillonner n'importe quel graphe de taille , alors que le CM est limité aux seuls graphes ayant précisément la structure de connectivité prescrite. ${\ displaystyle n}$${\ displaystyle n}$

Formulation du modèle

Le SCM est un ensemble statistique de graphes aléatoires ayant des sommets ( ) étiquetés , produisant une distribution de probabilité sur (l'ensemble des graphes de taille ). Des contraintes sont imposées à l'ensemble , à savoir que la moyenne d'ensemble du degré de sommet est égale à une valeur désignée , pour tous . Le modèle est entièrement paramétré par sa taille et la séquence de degrés attendue . Ces contraintes sont à la fois locales (une contrainte associée à chaque sommet) et douces (contraintes sur la moyenne d'ensemble de certaines quantités observables), et donnent ainsi un ensemble canonique avec un grand nombre de contraintes. Les conditions sont imposées à l'ensemble par la méthode des multiplicateurs de Lagrange (voir Modèle de graphe aléatoire à entropie maximale ). ${\ displaystyle G}$${\ displaystyle n}$${\ Displaystyle n = | V (G) |}$${\ displaystyle \ {v_ {j} \} _ {j = 1} ^ {n} = V (G)}$${\ displaystyle {\ mathcal {G}} _ {n}}$${\ displaystyle n}$${\ displaystyle n}$ ${\ displaystyle k_ {j}}$${\ displaystyle v_ {j}}$${\ displaystyle {\ widehat {k}} _ {j}}$${\ displaystyle v_ {j} \ in V (G)}$${\ displaystyle n}$${\ displaystyle \ {{\ widehat {k}} _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle \ langle k_ {j} \ rangle = {\ widehat {k}} _ {j}}$

Dérivation de la distribution de probabilité

La probabilité que le SCM produise un graphe est déterminée en maximisant l' entropie de Gibbs sous réserve de contraintes et de normalisation . Cela revient à optimiser la fonction de Lagrange multi-contraintes ci-dessous: ${\ displaystyle \ mathbb {P} _ {\ text {SCM}} (G)}$${\ displaystyle G}$ ${\ displaystyle S [G]}$${\ displaystyle \ langle k_ {j} \ rangle = {\ widehat {k}} _ {j}, \ j = 1, \ ldots, n}$${\ displaystyle \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) = 1}$

${\ displaystyle {\ begin {aligné} & {\ mathcal {L}} \ left (\ alpha, \ {\ psi _ {j} \} _ {j = 1} ^ {n} \ right) \\ [6pt ] = {} & - \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) \ log \ mathbb {P} _ { \ text {SCM}} (G) + \ alpha \ left (1- \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} ( G) \ right) + \ sum _ {j = 1} ^ {n} \ psi _ {j} \ left ({\ widehat {k}} _ {j} - \ sum _ {G \ in {\ mathcal { G}} _ {n}} \ mathbb {P} _ {\ text {SCM}} (G) k_ {j} (G) \ right), \ end {aligné}}}$

où et sont les multiplicateurs à fixer par les contraintes (normalisation et séquence de degrés attendue). Mettre à zéro la dérivée de ce qui précède par rapport à pour un rendement arbitraire${\ displaystyle \ alpha}$${\ displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ displaystyle \ mathbb {P} _ {\ text {SCM}} (G)}$${\ displaystyle G \ in {\ mathcal {G}} _ {n}}$

${\ displaystyle 0 = {\ frac {\ partial {\ mathcal {L}} \ left (\ alpha, \ {\ psi _ {j} \} _ {j = 1} ^ {n} \ right)} {\ partial \ mathbb {P} _ {\ text {SCM}} (G)}} = - \ log \ mathbb {P} _ {\ text {SCM}} (G) -1- \ alpha - \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ \ Rightarrow \ \ mathbb {P} _ {\ text {SCM}} (G) = {\ frac {1} {Z} } \ exp \ left [- \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ right],}$

la constante étant la fonction de partition normalisant la distribution; l'expression exponentielle ci-dessus s'applique à tous , et donc la distribution de probabilité. Nous avons donc une famille exponentielle paramétrée par , qui est liée à la séquence de degrés attendue par les expressions équivalentes suivantes: ${\ displaystyle Z: = e ^ {\ alpha +1} = \ sum _ {G \ in {\ mathcal {G}} _ {n}} \ exp \ left [- \ sum _ {j = 1} ^ { n} \ psi _ {j} k_ {j} (G) \ right] = \ prod _ {1 \ leq i <j \ leq n} \ left (1 + e ^ {- (\ psi _ {i} + \ psi _ {j})} \ right)}$${\ displaystyle G \ in {\ mathcal {G}} _ {n}}$${\ displaystyle \ {\ psi _ {j} \} _ {j = 1} ^ {n}}$${\ displaystyle \ {{\ widehat {k}} _ {j} \} _ {j = 1} ^ {n}}$

${\ displaystyle \ langle k_ {q} \ rangle = \ sum _ {G \ in {\ mathcal {G}} _ {n}} k_ {q} (G) \ mathbb {P} _ {\ text {SCM} } (G) = - {\ frac {\ partial \ log Z} {\ partial \ psi _ {q}}} = \ sum _ {j \ neq q} {\ frac {1} {e ^ {\ psi _ {q} + \ psi _ {j}} + 1}} = {\ widehat {k}} _ {q}, \ q = 1, \ ldots, n.}$

Références