Quelques points de repères dans l’étude des réseaux par la théorie des graphes

Laurence Saglietto

Description

Networks and Communication StudiesNETCOM, vol. 20, n° 1-2, 2006p. 195-216Quelques points de repères dans l’étudedes réseaux par la théorie des graphes1Laurence SagliettoAbstract.—The notion of network and its theories, are very old. However, these are at an interestingchange in their evolution, as today interdisciplinary exchanges are important. Maybe the creation of aunique theory is under way?Keywords.— Network, Graph theoryRésumé.— La notion de réseau et les théories qui lui sont consacrées, sont très anciennes. Cependant,elles sont à un tournant intéressant de leur évolution, puisque aujourd’hui les échangesinterdisciplinaires sont nombreux. Peut-être que la création d’une théorie unique est en cours?Mots clés.— Réseaux, Théorie des graphesINTRODUCTIONeLa notion de réseau, dont l’origine remonte au XVIII siècle (Bakis, 1993;Assens, 1999), a fait couler beaucoup d’encre sur ses divers sens et réalités: physiques(transports, espaces géographiques), fonctionnelles, organisationnelles (réseaux d’en-treprises) ou sociales (réseau d’individus). Étant un élément essentiel de maintes disci-plines (géographie, sociologie, économie, urbanisme, physique, mathématique…),cette notion a longtemps été entourée d’un certain flou sémantique.Aujourd’hui, chaque discipline a clarifié, positionné et légitimé «le réseau»,comme en témoignent leurs références académiques. Ces enrichissements ontcontribué à l’émergence d’échanges interdisciplinaires permettant de ...

Informations

• Publié par: Mefer
• Nombre de lectures: 124
• Langue: Français

Extrait

Networks and Communication Studies NETCOM, vol. 20, n° 1-2, 2006 -

1. Maître de conférences HDR en Science de Gestion. Responsable du M2 Professionnel «Audit Informationnel et Stratégique », Master des Affaires de l’IAE de NICE. GREDEG UMR 6727, 250 rue Albert Einstein, 06560 Valbonne. E-mail : [e-mail]

Tableau 1. Exemples célèbres en théorie des graphes 1/ Est-il possible de trouver un parcours 2/ Quel est le nombre minimum de ferm é qui passe, une et une seule fois, par couleurs n é cessaire pour colorier chacun des 7 ponts de cette ville? cette carte de l ’ Afrique?

3/ Le r é seau commercial et marital des familles florentines du XV e si è cle d é termine la structure du pouvoir politique et, par elle, la vie de la r é gion. Qui d é tient donc ce pouvoir?

-°

4/ É tant donn é deux individus pris au hasard dans la population, quelle est la probabilit é  que le minimum d ’ interm é diaires entre eux soit de 0, 1, 2 ou plus? Par exemple, combien y a-t-il d ’ interm é diaires entre les acteurs Kevin Bacon et Gary Grant (c ’ est-à -dire une collaboration d ’ acteurs dans des films ou des s é ries)?

5/Quel est le mod è le-type de r é seau qui repr é sente le mieux la propagation des é pid é mies?

7/Connaissez-vous les grandes th é matiques des recherches actuelles sur les r é seaux en sociologie, informatique, physique, math é matique, é conomie, gestion …

6/ Quel est le mod è le-type de r é seau qui repr é sente le mieux le transport a é rien ?

8/ Au regard de ce sch é ma, qui est la firme pivot de ce r é seau (Star Alliance)?

198





NETCOM, vol.

20, n

°

1-2, 2006

Graphes

A o

C o

Graphe

B o

o D

Matrice A B C D A - 0 1 1 B 0 - 0 1 C 1 0 - 1 D 1 1 1 - Figure 1. Représentation graphique

Graphes non orient é s Graphes orient é s = digraphes En donnant un sens aux ar ê tes d ’ un graphe, on obtient un digraphe (ou graphe orient é ).

Graphes non valu é s ou valu é s

200

NETCOM, vol.

20, n

°

1-2, 2006



Th é orie des graphes

Les sciences de l ’ univers et du vivant Les sciences sociales (math é matique, physique, biologie, (sociologie, linguistique, é conomie informatique, g é ographie communication, psychologie) Exemples L ’ analyse spatiale des ph é nom è nes g é ographiques

Les grands r é seaux d ’ interaction





Les r é seaux sociaux

°

-

2. C ’ est-à -dire la coloration des sommets d ’ un graphe planaire (sans boucles) de telle sorte que toutes les ar ê tes aient des extr é mit é s de couleurs diff é rentes. 3. É tant donn é qu ’ aucun des deux ne s ’ est av é r é pouvoir ê tre un mod è le g é n é ral capable de repr é - senter des syst è mes complexes divers, tels que les r é seaux de neurones, les é cosyst è mes ou l ’ Internet.

’ Objectif Comment g é n é rer des gra rencontr é es en pratique ? Contexte La majorit é des grands gra des propri é t é s bien partic d ’ expliquer, les grands r é s l ’ interm é diaire de mod è le ayant certaines propri é t é s.

-Exemples Liens hypertextes entre sit sur Internet, é changes de c les articles scientifiques, sy distribution d' é lectricit é , r é d' é pid é mies … Notions de base (Latapy Soit un graphe G = (V,E) -La densit é est le rapport e de liens possibles -La distance entre deux s minimale d'un chemin les la moyenne pour tout cou eux. -Le coefficient de clusterin probabilit é , é tant donn é d voisins entre eux. Le coeffi moyenne du coefficient de -La distribution des degr é nombre de sommets de G soit une loi de puissance (s de poisson (si proportionn Comparaison des graphes propri é t é s communes) ave d ’ Erdos & R é nyi 1959). R é Graphes rencontr é s en p Graphes Densit Distance Clusteri Distributio Scale free Al é atoire ~1/ ~ log/ ~1/ Loi Poisson Networks

Objectif Comment forme d ’ u v é cu par le Contexte Appr é hen fois au tra g é ographi territoires).

Exemples Gestion des r é seaux techniques, am é na transports, risque et environnement, tran et de secours … Notions de base (Grasland, 2001) Les indicateurs globaux de connexit é m fragmentation d ’ un graphe en composa unes des autres. - Indice de connexit é simple: IC1 = (S-C  - Indice de connexit é pond é r é : IC2 = [(S1_) + (Sk_)]/S_ (S = nombre de sommets de G, C = les c S1 … Sk le nombre de sommets de chac connexes) Les indicateurs globaux de connectivit é  vari é t é des relations possibles, directes o sommets d'un graphe. Plus les indices so connexit é et forte - Indice de connectivit é  ß = rapport entr nombre de sommets - Indice de connectivit é  γ = rapport entre et nombre maximal de liens possibles - Le nombre de cyclomatique µ = le no ind é pendants que l ’ on peut construire si graphe - Indice de connectivit é : α = rapport entr

r é seau par un ou plusieurs param è tre(s).

Objectif La majorit é des grands graphes rencontr é s en pratiques ont des propri é t é s bien particuli è res. Les travaux actuels tentent d ’ expliquer, les grands r é seaux d ’ interactions, par l ’ interm é diaire de mod è les g é n é rateurs de graphes al é atoires ayant certaines propri é t é s. Contexte Etudier les r é seaux sociaux individuels ou collectifs au travers de la formalisation syst é matique des relations entre les acteurs qui Exemples Les r é seaux de parent é , d'affinit é , de communication, marchands, d'entreprises, d'amiti é… Notions de base (Wasserman et Faust 1994) Du langage des graphes ou r é seaux sociaux - L ’ indice de coh é sion entre deux sommets repr é sente la force du lien qui relie ces deux sommets. C'est linverse de la distance g é od é sique entre deux sommets - La force d ’ un lien = fr é quence des contacts si < moyenne = lien fort ; si > moyenne = lien faible - La densit é est le rapport entre le  nombre de liens et le nombre de liens possibles entre sommets: - Centralit é de degr é d ’ un sommet = nombre de connexion d ’ un sommet aux autres - Centralit é de proximit é d ’ un sommet = somme des distances g é od é siques reliant ce sommet à tous les autres points du graphe. rm é diarit é d ’ un e des probabilit é s es les paires d ’ acteurs go demi degr é int é rieur ique) = un sous complet. Si un sous- omme longueur emins reliant tous les parlera de n-clique. Si phe un n œ ud n ’ a pas au plus K autres ignera de K-plex. s un K-noyau chaque t à k autres n œ uds. loin -É tudes et ’é volution des ns, en particulier au se des mod è les logits es r é seaux small eaux scale free nce d ’é chelle idem





Figur

e

2. Les diff





é rents types de r



é seaux (Source







: Watts et Strogatz, 1998)

°

-

4. Elle n ’ est mais une analyse.

ni

une

nouvelle

bo

î te

à 

outils

m

é thodologiques,

ni

une

th

é orie,

ni

un

paradigme