[PDF] Science des Réseaux Un résumé Dé nition et Vocabulaire

View - Download Science des Réseaux Un résumé Dé nition et Vocabulaire

Previous PDF

Next PDF

Science des Réseaux

Un résuméProposé par

Rémy Cazabet? Dé?nition et Vocabulaire

Réseaux : notation graphe

Notation graphe :G= (V;E)

VEnsemble de noeuds/Vertex.

EEnsemble de liens

u2Vun noeud. (u;v)2Eun lien.

Réseaux : notation graphe

Graphe

????Notation graphe

G= (V;E)

V=f1;2;3;4;5;6g

E=f(1;2);(1;6);

(1;5);(2;4);(2;3);(2;5); (2;6);(6;5);(5;5);(4;3)gTypes de réseaux Réseaux simples: Les liens peuvent soit exister, soit ne pas exister entre les noeuds. Il n"y a pas de boucles (liens d"un noeud vers lui-même. Graphe dirigé:Les liens ont une direction:(u;v)2Vn"implique pas (v;u)2V Graphespondérés: Unpoidestassociéàchaquelien,pourindiquersaforce

par exemple.D"autres types de graphes existent (multigraphes, multipartite, hypergraphes, etc.)Compter les noeuds et les liens

N=ntaille: nombre de noeudsjVj.

L=mnombre de liensjEj

L maxNombre maximal de liens

Réseaux non-dirigés:

N 2 =N(N1)=2

Réseaux dirigés:

N 2 =N(N1)Description des noeuds/liens N uVoisinsdeu, noeuds qui partagent un lien avecu. k uDegrédeu, nombre de voisinsjNuj.N out uSuccesseursdeu, noeueds tels que(u;v)2Edans un graph dirigé N in uPrédécesseursdeu, noeuds tels que(v;u)2Edans un graphe dirigé k out uDegré sortantdeu, Nombre de liens dontuest l"origine jNout uj. k in jNin ujw u;vPoidd"un lien(u;v). s uForcedeu, somme des poids des liens adjacents,su=P vwuv.Description de réseaux - Noeuds/Liens hkiDegré moyen: Les réseaux réels sontclairsemé(sparse), i.e., typiquement le degré est petit par rapport au nombre de noeuds:hki n. Augmente lentement avec le nombre de noeuds, e.g.,dlog(m) hki=2mn d=d(G)Densité: Fraction des paires de noeuds connectées dansG. d=L=LmaxChemins - Marches - Distance Marche: Séquence de noeuds ou liens adjacents (e.g.,?.?.?.?.?est une marche valide) Chemin: Une marche dans laquelle tous les noeuds sont distincts. Longueur d"un chemin: nombre delienstraversés par un chemin Longueur pondérée d"un chemin: Somme des poids des liens sur un chemin Plus court chemin: Le plus court chemin entre deux noeudsu;vest un chemin delongueurminimale. Souvent, il n"y en a pas qu"un seul. Plus court chemin pondéré: Chemin de plus courtchemin pondéré. u;v: Distance: La distance entre les noeudsu;vest la longueur de plus court chemin entre eux.Description de réseaux - Chemins maxDiametre:distancemaximale entre ? noeuds du réseau. h`iDistancemoyenne, i.e., moyenne des distances entre toutes les paires de noeuds: h`i=1n(n1)X i6=jd ijDistribution de degré La distribution des degrés des noeuds est considéré une propriété impor- tante. On cherche principalement à savoir si elle suit l"une de ces deux formes : •Courbe en clocheDistribution (Normale/Poisson/Binomiale) •Sans-échelle(Scale-Free), aussi appelélongue-queue(long-tail) ou

Loi de puissance(Power-law)

Une courbe en cloche à uneéchelle, unevaleur type: la taille des êtres hu- mains, par exemple: la plupart des personnes ont une taille assez proches delavaleurmoyenne. Unedistributionsanséchelleestdi?érente,unexem- ple est la richesse des individus: Une grande partie des valeurs sont faibles, mais quelques valeurs sont extrêmement élevées. La moyenne n"est pas du tout représentative de l"ensemble des valeurs.sous-graphes Sous-grapheH(W)(Sous-graphe induit): ensemble des noeudsWdu grapheG= (V;E)et les liens qui les connectent dansG, i.e., sous-graphe

H(W) = (W;E0);WV;(u;v)2E0()u;v2W^(u;v)2E

Clique: sous-graphe de densité ?:d= 1

Triangle: clique de taille ?

Composante connexe: un sous-graphe tels que tous les noeuds sont con- nectés par un chemin, et pour lequel il n"y a pas de lien vers les autres noeuds de réseau. Composante fortement connexe: Dans un graphe dirigé, une composante connexe si l"on prend en compte les directions des liens. Composantefaiblementconnexe: Dansungraphedirigé, unecomposante connexe si l"on ne prend pas en compte les directions des liens

Triangles

u-Triades deu:nombre de triangles contenant le nodeu -Nombre de triangles dans le graphe =13 P u2Vu.Chaquetriangledans le graphe est compté comme unetriadeune fois par chacun des noeuds qui le compose. max u-Potentiel de triangle deu:Nombre maximal de triangles qui peu- vent exister contenantu, étant donné son degré:max u=(u) =ki2 max-Potentiel de triangle de G:Nombre maximal de triangles qui peu- vent exister dans le graphe, étant donné sa distribution de degré.max= 13 P u2Vmax(u)Coe?cient de clustering Le coe?cient de clustering est une mesure de la fermeture transitive présentedansungraphe. Lafermeturetransitiveestunenotionquiviensde l"analyse de réseaux sociaux, souvent résumée par l"aphorisme:Les amis de mes amis sont mes amis. Plus les voisins des voisins d"un noeudnont ten- dance à être des voisins den, plus le coe?cient de clustering est élevé.C u-Clustering coe?cient d"un noeud:densité du sous-graphe induit par les voisins du noeudu,Cu=d(H(Nu). Aussi interprété comme la fraction de tous les triangles possibles dansNuqui existent,u maxuhCi-Coe?cient de clustering moyen:Moyenne des coe?cients de clustering de tous les noeuds du graphe,C=1N P

u2VCu.Attention en interprétant cette valeur : les noeuds de faible degrés sont généralement majori-

taires dans les graphes réels, et leur valeur de clusteringCest très sensible, i.e., pour un noeud

ude degré ?,Cu20;1, tandis que les noeuds de fort degré ont tendance à avoir des scores plus contrastés.C g-Coe?cient de clustering global:Fraction de tous les triangles possi- bles qui existent dans le graphe,Cg= maxRéseau petit monde Un réseau est ditpetit monde(Small world) lorsqu"il a certaines propriétés structurellesa. La dé?nition n"a pas vraiment de dé?nition quantitative, mais correspond aux propriétés suivantes: •La distance moyenne doit être courte, i.e., de l"ordre de grandeur du log du nombre de noeud:h`i log(N) •Le coe?cient de Clustering doit être grand, i.e., largement supérieur à celui d"un graphe aléatoire de propriétés équivalente , e.g.,Cg d, avecdla densité du graphe. La propriété petit monde est considéré characteristique desréseaux réels, paroppositionauxréseauxaléatoires. Onassociecettepropriétéàcertaines characteristiques du graphe (robustesse aux défaillances, circulation e?-

cace de l"information, etc.).Attention: dans certains contextes,réseau petit mondepeut désigner sim-

plement un réseau dont la distance moyenne est courte, indépendemment de son coe?cient de clustering.a

Watts and Strogatz ????.coeurs et Shells

Beaucoup de réseaux réels sont connus pour avoir une structure dite en coeur-périphérie, i.e., il y a un coeur qui est densément connecté et une zone périphérique dont les noeuds sont faiblement connecté entre eux et avec le coeur.k-coeur:le k-coeur (coeur d"ordrek) du grapheG(V;E)est le plus grand sous-grapheH(C)tel que tous ses noeuds ont au moins un degrék, i.e.,

8u2C;kH

uk, aveckH ule degré du noeududans le sous-grapheH. coreness:Un noeudua une corenessks"il appartient auk-coeur mais pas auk+ 1-coeur. c-shell:Tous les noeuds dont la coreness est exactementc.Vocabulaire Singleton: ou noeud isolé, noeud de degré nulk= 0

Hub: noeudude large degré, i.e.,ku hkiPont: noeud ou lien qui, s"il est enlevé, sépare le graphe en plusieurs com-

posantes connexes.Bout: un bout est un demi-lien, i.e., le lien(u;v)a un

bout connecté àuet un autre connecté àv.Réseau complet: réseau où tous les liens possibles existe:L=Lmax

Réseau clairsemé (sparse): réseau ayant peu de lien,d1,LLmaxGraphe connecté: Graphe qui n"a qu"une seule composante connexe? Réseaux en tant que matrices

Les matrices en quelques mots

Les matrices sont des objets mathématiques qui sont destablesde nom- bres. La taille d"une matrice est exprimée commemn, pour une matrice avecmlignes etncolonnes.l"ordre (ligne/colonne) est important. M

ijreprésente l"élément sur laligneietcolonnej.A- Matrice d"adjacenceLa méthode la plus courante pour représenter un graphe par une matrice

consiste à créer une matrice d"adjacenceA. C"est une matrice carrée dont le nombre de lignes et de colonnes est égal au nombre de noeudsNdu graph. Les noeuds du graphe sont numérotés de ? àN, et il y a un lien entre les noeudsietjsi la valeur à la positionAijn"est pas0. •Une valeur sur la diagonale représente uneboucle •si le graphe estnon dirigé, la matrice estsymmétrique:Aij=Aji pour touti;j. •Dans un graphenon pondéré, les liens sont représentés par la valeur1. •Dans un graphepondéré, la valeurAijreprésente lepoidsdu lien (i;j)Notation matricielle - Exemple Graph ????A-AdjacencyMat.0 B

BBBB@0 1 0 0 1 1

1 0 1 1 1 1

0 1 0 1 0 0

0 1 1 0 0 0

1 1 0 0 1 1

1 1 0 0 1 01

C CCCCA

Science des Réseaux

Un résuméProposé par

Rémy Cazabet? Indices structurels

Indices structurels de noeuds

Les indices structurels de noeuds, souvent appeléscentralité, mesurent à quel point un noeud occupe un certain type de position dans la struc- ture du graphe. Cette notion est parfois résumée commeune mesure de l"importance des noeuds, cependantimportanceet la notion d"êtrecentral sont des notions subjectives. Une centralité, malgré son nom, ne mesure donc pas forcément à quel point le noeud est central ou important, mais par cette centralité.Centralité de degré Lacentralitédedegréestl"unedesplusutilisés. Ellepeutsouventêtreinter- prétée comme une mesure de popularité, e.g., plus j"ai de relations, d"amis

dans un réseau social, le plusimportantje suis dans ce réseau.Centralité de proximité / Harmonique

La centralité de proximité (closeness) d"un noeud mesure à quel point il est proche de tous les autres noeuds. Pour interpréter ce score, un parallele peut être fait avec la position d"un point dans un cercle: le point qui est le plus proche de tous les autres points du cercle est son centre. Le noeud de plus grande closeness est l"équivalent pour ce graphe du centre pour un cercle. Formellement, le plus simple est de le dé?nir comme l"inverser de lafarness.Farness:Distance moyenne à tous les noeuds du graphe.

Farness(u) =1N1X

v2Vnu` u;v

Closeness:Inverse de la farness

Closeness(u) =N1P

v2Vnu`u;v Centralité Harmonique:Une variante de la closeness dé?nie comme la moyenne des inverses des distances à tous les autres noeuds (moyenne harmonique). Cette mesure est dé?nie même sur des graphes non con- nexes, à condition de dé?nir 11 = 0. Son interprétation est la même que la

Closeness.

Harmonic(u) =1N1X

v2Vnu1` u;vCoe?cient de Clustering Ce score, déjà dé?ni, mesure lafermeture transitived"un noeud. Un score élevé est souvent interprété comme un noeud qui appartient fortement à une et une seule communauté (les amis de mes amis sont mes amis, car nous appartenons tous au même groupe). Un score faible peut signi?er que le noeud joue le rôle de pont: il n"y a pas de connections entre mes amis car ils appartiennent à des cercles sociaux di?érents.Centralité - exemples (a) Degré (b) Coe?cient de clustering (c) Closeness (d) Centralité Harmonique (e) Centralité d"intermédiarité (f) Centralité de Katz (g) Centralité valeurs propres (h) PageRankCentralité de Katz La centralité de Katz est considérée comme une mesure du potentiel d"in?uence du noeud. Pour un noeudu, elle est dé?nie comme la somme, pour tous les marches de distance`, du nombre de noeuds situés à une distance exactement`deu, diminuté d"un facteur décroissant rapidement lorsque`augmente. L"intuition est que, plus le nombre de noeuds qui peu- vent être atteind en un faible nombre de sauts est grand, plus la valeur est élevée. Plus formellement, elle est dé?nie comme: C

Katz(u) =1X

`=1N X v=1`(A`)vu avecA` vule nombre de marches de longueur`devàu, et <1 iun paramètre plus petit que la plus grande valeur propre deA, Ce qui permet de calculer ce score en forme matriciel: C

Katz(u) = ((IAT)1I)!I

Notons que dnas un graphe dirigé, la centralité de Katz doit être interprété comme un mécanisme devote: une centralité plus importante deusigni- ?e que plus de noeuds peuvent atteindreurapidement, et non queupeut atteindre de nombreux noeuds rapidement.Centralité d"intermédiarité La centralité d"intermédiarité (betweenness) mesure à quel point le noeud joue le rôle de pont, d"intermédiaire. Plus le score est haut, plus le noeud est essentiel au déplacement rapide dans le graphe.Plus formellement, la betweenness deuest dé?nie comme la fractions de tous les plus courts chemins entre toutes les paires de noeuds du graphe (saufu) qui passent paru. Par conséquent, si nous enlevons un noeud de betweenness élevé, de nombreux plus courts chemins vont devenir plus long, et donc la circu- lation dans le graphe sera plus di?cile. Un cas extrême est celui d"un noeud qui est le seul point de passage entre deux groupes de noeuds: si on le re- tire, la circulation n"est plus du tout possible entre certains sous-graphes. Ces noeuds ont donc tendance à avoir un score de betweenness très élevé.

Elle est dé?nie comme:

C

B(v) =X

s6=v6=t2V st(v) st avecstle nombre de plus court chemins entresettetst(v)le nombre de ces chemins qui passent par le noeudv. Labetweennesstendàaugmenteraveclatailledugraphe. Uneversionno- ramlisée peut être obtenue en divisant par le nombre de paires de noeuds, pour un graphe dirigé:Cnorm

B(v) =CB(v)(N1)(N2).

Centralité Eigenvector

La centralité Eigenvector, ou centralité de vecteurs propres (eigenvector en anglais), est une dé?nition récursive de l"importance: un noeud est impor- tant s"il est connecté à des noeuds importants. En pratique, elle est dé?nie de la manière suivante: la centralité eigenvectorCude chaque noeuduest telle que si chaque noeudenvoieson score de centralité a ses voisins, alors la somme des scores reçus par chaque noeud est égale àCu(avecune constante de normalisation). Plus formellement, C t+1 u=1 X v2NinuC t v(?) Cette dé?nition récursive peut être interprétée en termes de valeurs pro- pres et vecteurs propres, d"où le nom. Un vecteur propre d"une matrice est dé?ni par la relationAx=x, avecxun vecteur propre, etla valeur propre correspondante. La centralité eigenvector est dé?nie par le vecteur propre associé à la plus grande valeur propre, qui est la seule solution pour laquelle tous les élements du vecteur propre sont positifs. Une méthode simple pour calculer la centralité eigenvector est appelé la méthode des puissances itérées: des valeurs aléatoires sont attribuées à tous les noeuds, puis on répète l"équation ?. Au bout d"un certain nombre d"itération, il est prouvé que le résulta converge vers des valeurs ?xes: la centralité eigen- vecteur.La centralité Eigenvector ne peut pas être calculée, en général, sur des graphes orientés, à cause de l"existence denoeuds source, i.e.,kin= 0. Ces noeuds ont, par dé?nition, un score de centralité de ? at+ 1, et donc envoientune valeur de ? at+ 2, qui pourront de ce fait avoir maintenant un score de centralité de ?, qu"ils transmettront au prochain tour, et aisi de suite jusqu"à ce que tous ou une grande partie des noeuds ?nissent avec une centralité de ?.Pagerank

La centralité Pagerank

aest célèbre pour avoir été utilisée par Google pour classer les résultats de son moteur de recherche: Un score de Pagerank est calculé pour chaque page, sur le graph ou les noeuds sont des pages et les liens des liens hypertextes, puis, lorsque l"on recherche un ensem- ble de mots, toutes les pages qui contiennent ces mots sont retournées, classées par leur score PageRank. Aujourd"hui, les méthodes utilisées par Google sont plus complexes, notamment parce qu"elles personnalisent les résultats en fonction des utilisateurs. CetteméthodeestunevariantedelacentralitéEigenvector, permettantno- tamment de résoudre le problème des noeuds source. Pagerank introduit deux nouveautés: ?) à chaque étapet, chaque noeud gagne une petite valeur constante, ?) Les valeurs envoyées par chaque noeud sont divisées également parmi tous ses successeurs (normalisation par le degré). L"équation ? deviens donc: C t+1 u=X v2NinuC t vk outv+(?)

Avec, par convention,= 1,2[0;1]un paramètre.

grande valeur propre d"une matrice appelé lamatrice googleG, dé?nie telle queGij=Sij+ (1)=n, avecSijla matrice d"adjacence nor- malisée par colonne.a

Page et al. ????.Indices structurels de liens

La position des liens dans le réseau peut aussi être décrite en utilisant des centralitésdeliens, généralementsimilairesàcellesdé?niessurlesnoeuds. ClusteringCepour un lien(u;v)est dé?nit comme la fraction des voisins d"au moins l"un des deux noeuds aux extrémités qui est voisin des deux si- multanément. C e(u;v) =jNu\NvjjNu[Nvj 2 Les liens de fort clustering sont ditsIntégratifs, les liens de faible clustering sont dit dispersifs. Intermediarité des liensest dé?nie exactement comme la centralité d"intermédiarité des noeuds, mais en comptant le nombre de plus courts chemins qui passent par le lien au lieu du noeud, i.e., Cquotesdbs_dbs46.pdfusesText_46

[PDF] les fractions cm1 exercices ? imprimer

[PDF] les fractions de 4eme

[PDF] Les fractions du second degres

[PDF] Les fractions égales Besoin d'aide silvous plait

[PDF] Les fractions égyptiennes

[PDF] les fractions égyptiennes, j'y arrive pas !

[PDF] Les fractions en 3eme

[PDF] les fractions en 4eme

[PDF] Les fractions et les chocolats

[PDF] Les fractions et les proportionnalités

[PDF] les fractions et les recettes

[PDF] Les Fractions et proportions

[PDF] les Fractions et quotients

[PDF] les fractions exercices

[PDF] Les fractions fractionnaires