Vue d’ensemble

La centralité de vecteur propre mesure le pouvoir ou l'influence d'un node. Dans un réseau orienté, le pouvoir d'un node provient de ses voisins entrants. Ainsi, le score de centralité de vecteur propre d'un node dépend non seulement du nombre de liens entrants qu'il a, mais aussi de la puissance de ses voisins entrants. Les connexions avec des nodes à score élevé contribuent davantage au score du node que les connexions avec des nodes à faible score. Dans le scénario de propagation de maladie, un node avec une plus haute centralité de vecteur propre est plus susceptible d'être proche de la source d'infection, ce qui nécessite des précautions particulières.

Le bien connu PageRank est une variante de la centralité de vecteur propre.

La centralité de vecteur propre prend des valeurs entre 0 et 1, les nodes avec des scores plus élevés étant plus influents dans le réseau.

Concepts

Centralité de Vecteur Propre

La puissance (score) de chaque node peut être calculée de manière récursive. Prenez le graph ci-dessous comme exemple, la matrice adjacente A reflète les liens entrants de chaque node. En initialisant que chaque node a un score de 1, et il est représenté par le vecteur s⁽⁰⁾.

À chaque tour de transition de puissance, mettez à jour le score de chaque node par la somme des scores de tous ses voisins entrants. Après un tour, le vecteur s⁽¹⁾ = As⁽⁰⁾ est comme suit, la normalisation L2 est appliquée pour remettre à l'échelle :

Après k itérations, s^(k) = As^(k-1) = A^ks⁽⁰⁾. À mesure que k augmente, s^(k) se stabilise. Dans cet exemple, la stabilisation est atteinte après environ 20 tours.

En fait, s^(k) converge vers le vecteur propre de la matrice A qui correspond à la plus grande valeur propre absolue, d'où les éléments dans s^(k) sont appelés centralité de vecteur propre.

Valeur Propre et Vecteur Propre

Étant donné A est une matrice carrée n x n, λ est une constante, x est un vecteur non-nul n x 1. Si l'équation Ax = λx est vraie, alors λ est appelée la valeur propre de A, et x est le vecteur propre de A qui correspond à la valeur propre λ.

La matrice ci-dessus A a 4 valeurs propres λ₁, λ₂, λ₃ et λ₄ qui correspondent respectivement aux vecteurs propres x₁, x₂, x₃ et x₄. x₁ est le vecteur propre correspondant à la valeur propre dominante λ₁ qui a la plus grande valeur absolue.

Selon le théorème de Perron-Forbenius, si la matrice A a des valeurs propres |λ₁| > |λ₂| ≥ |λ₃| ≥ ... ≥ |λ_n|, alors à mesure que k → ∞, la direction de s^(k) = A^ks⁽⁰⁾ converge vers x₁, et s⁽⁰⁾ peut être n'importe quel vecteur non nul.

Itération de Puissance

Pour la meilleure efficacité de calcul et précision, cet algorithme adopte l'approche d'itération de puissance pour calculer le vecteur propre dominant (x₁) de la matrice A：

• s⁽¹⁾ = As⁽⁰⁾
• s⁽²⁾ = As⁽¹⁾ = A²s⁽⁰⁾
• ...
• s^(k) = As^(k-1) = A^ks⁽⁰⁾

L'algorithme continue jusqu'à ce que s^(k) converge dans certaines tolérances, ou que le nombre maximum d'itérations soit atteint.

Considérations

• L'algorithme utilise la somme de la matrice d'adjacence et de la matrice unité (c'est-à-dire, A = A + I) plutôt que seulement la matrice d'adjacence pour garantir la convergence.
• Le score de centralité de vecteur propre des nodes sans lien entrant converge vers 0.
• La boucle sur soi-même est comptée comme un lien entrant, son poids n'étant compté qu'une seule fois (graph pondéré).

Syntaxe

• Commande : algo(eigenvector_centrality)
• Paramètres :

Exemples

L'exemple est un réseau web, la propriété d'arête @link.value peut être utilisée comme pondération :

File Writeback

algo(eigenvector_centrality).params({
  max_loop_num: 15,
  tolerance: 0.01
}).write({
    file: {
      filename: 'rank'
    }
})

Résultats : Fichier rank

web7,4.63007e-06
web6,0.0198426
web5,0.255212
web3,0.459901
web4,0.255214
web2,0.573512
web1,0.573511

Property Writeback

algo(eigenvector_centrality).params({
  edge_weight_property: 'value'  
}).write({
    db: {
      property: 'ec'
    }
})

Résultats : Le score de centralité pour chaque node est écrit dans une nouvelle propriété nommée ec

Direct Return

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01,
  edge_weight_property: '@link.value',
  order: 'desc'
}) as ec 
return ec

Résultats : ec

Stream Return

Exemple : Calculez la centralité de vecteur propre pondérée pour tous les nodes, comptez le nombre de nodes avec un score supérieur à 0,4 ou autrement respectivement

algo(eigenvector_centrality).params({
  edge_weight_property: '@link.value'
}).stream() as ec
with case
when ec.rank > 0.4 then 'attention'
when ec.rank <= 0.4 then 'normal'
END as r
group by r
return table(r, count(r))

Résultats : table(r, count(r))