Centralité d’interdépendance
La centralité de percolation est une version de la centralité d’interdépendance pondérée, mais elle prend en compte l »état’ des nœuds source et cible de chaque chemin le plus court pour calculer ce poids. La percolation d’une « contagion » se produit dans des réseaux complexes dans un certain nombre de scénarios. Par exemple, une infection virale ou bactérienne peut se propager dans des réseaux sociaux de personnes, appelés réseaux de contact. La propagation d’une maladie peut également être envisagée à un niveau d’abstraction plus élevé, en considérant un réseau de villes ou de centres de population, reliés par des liaisons routières, ferroviaires ou aériennes. Les virus informatiques peuvent se propager par le biais de réseaux informatiques. Les rumeurs ou les informations sur les offres et les transactions commerciales peuvent également se propager via des réseaux sociaux de personnes. Dans tous ces scénarios, une « contagion » se propage sur les liens d’un réseau complexe, modifiant les « états » des nœuds à mesure qu’elle se propage, de manière récupérable ou non. Par exemple, dans un scénario épidémiologique, les individus passent de l’état « sensible » à l’état « infecté » à mesure que l’infection se propage. Les états que les nœuds individuels peuvent prendre dans les exemples ci-dessus peuvent être binaires (comme recevoir/non recevoir une nouvelle), discrets (sensible/infecté/récupéré), ou même continus (comme la proportion de personnes infectées dans une ville), à mesure que la contagion se propage. La caractéristique commune à tous ces scénarios est que la propagation de la contagion entraîne un changement d’état des nœuds dans les réseaux. C’est dans cette optique qu’a été proposée la centralité de percolation (PC), qui mesure spécifiquement l’importance des nœuds en termes d’aide à la percolation dans le réseau. Cette mesure a été proposée par Piraveenan et al.
La centralité de percolation est définie pour un nœud donné, à un moment donné, comme la proportion de ‘chemins percolés’ qui passent par ce nœud. Un ‘chemin percolant’ est le plus court chemin entre une paire de nœuds, où le nœud source est percolant (par exemple, infecté). Le nœud cible peut être percolé ou non percolé, ou dans un état partiellement percolé.
P C t ( v ) = 1 N – 2 ∑ s ≠ v ≠ r σ s r ( v ) σ s r x t s ∑ – x t v {\displaystyle PC^{t}(v)={\frac {1}{N-2}}\sum _{s\neq v\neq r}{\frac {\sigma _{sr}(v)}{\sigma _{sr}}{\frac {{x^{t}}_{s}}{\sum {}-{x^{t}}_{v}}}}
où σ s r {\displaystyle \sigma _{sr}}
est le nombre total de plus courts chemins depuis le nœud s {\displaystyle s}.
au noeud r {\displaystyle r}.
et σ s r ( v ) {\displaystyle \sigma _{sr}(v)}
est le nombre de ces chemins qui passent par v {\displaystyle v}
. L’état de percolation du nœud i {\displaystyle i}
au temps t {\displaystyle t}
est noté par x t i {\displaystyle {x^{t}}_{i}}
et deux cas particuliers sont lorsque x t i = 0 {\displaystyle {x^{t}}_{i}=0}
qui indique un état non percolé au temps t {\displaystyle t}.
alors que lorsque x t i = 1 {\displaystyle {x^{t}}_{i}=1}
ce qui indique un état de percolation complète au temps t {\displaystyle t}.
. Les valeurs intermédiaires indiquent des états partiellement percolés ( par exemple, dans un réseau de cantons, ce serait le pourcentage de personnes infectées dans cette ville).
Les poids attachés aux chemins de percolation dépendent des niveaux de percolation attribués aux nœuds sources, en partant du principe que plus le niveau de percolation d’un nœud source est élevé, plus les chemins qui partent de ce nœud sont importants. Les nœuds qui se trouvent sur les chemins les plus courts provenant de nœuds fortement percolés sont donc potentiellement plus importants pour la percolation. La définition de la PC peut également être étendue pour inclure les poids des nœuds cibles. Les calculs de centralité de percolation s’exécutent en O ( N M ) {\displaystyle O(NM)}.
temps avec une implémentation efficace adoptée à partir de l’algorithme rapide de Brandes et si le calcul doit prendre en compte les poids des nœuds cibles, le temps le plus défavorable est O ( N 3 ) {\displaystyle O(N^{3})}.
