1	Révision: les réseaux complexes
2	Sommaire Révision Notions de base sur les graphes Rappel des propriétés des grands graphes de terrain (un peu de théorie) Exemples d’application: Les réseaux économiques (CAC 40) La propagation des épidémies Les relations entre maladies Internet (pour mémoire) Le réseau Le WEB Intérêt: comprendre, prévoir, agir
3	Introduction De récentes avancées dans le domaine des systèmes complexes ont fait ressortir le rôle central que jouent les graphes dans de nombreux phénomènes. Ces grands graphes permettent de modéliser les interactions entre les différents acteurs de ces phénomènes complexes. De manière surprenante ces graphes, appelés grands graphes de terrain ou complex networks, possèdent des propriétés structurelles non triviales communes qui ont fait l'objet de nombreuses et récentes études. Ces propriétés communes permettent d'envisager une nouvelle algorithmique des grands graphes de terrain. Les avancées qui en découlent ont des applications potentielles dans les divers domaines concernés.
4	Graphes : deux exemples simples Avant de rappeler les propriétés des grands graphes de terrain, les notions de base sont illustrées par deux exemples simples (« triviaux ») : Graphe régulier Graphe « petit mondisé » NB: Les définitions de bas sur les graphes sont rappelées en annexe
5	Exemple 1 : Graphe régulier 100 sommets
6	Exemple 2 : Graphe « petit mondisé »
7	Caractéristiques des graphes de terrain Les grands () graphes de terrain rencontrés dans différentes disciplines sont très différents des graphes réguliers. Ils ont des caractéristiques communes, en particulier : un faible degré moyen et une forte hétérogénéité des degrés : distribution de puissance des degrés des sommets ; des chemins courts entre tous les sommets. C’est la propriété du petit monde ; une faible densité globale couplée à une forte densité locale : on parle de clustering ; NB: Distribution de puissance et Petit Monde sont des propriétés liées () Grands graphes: Internet: ~ 20 000 AS, 180 10⁶ sites; cerveau: 10¹² neurones
8	Propriétés des graphes (Selon Barabasi)
9	Exemples de loi de puissance
10	Exemples de Petit Monde d (individus) = 6 (Milgram) d (IP) = 15 (réseau physique d’Internet) d (WWW) = 21 (Liens hypertexte entre pages du WEB)
11	Le clustering
12	Génération des graphes de terrain Plusieurs modèles ont été imaginés pour simuler la constitution de graphes de terrain: Génération aléatoire (Watts et Strogatz) ; Rattachement préférentiel « les riches deviennent plus riches »: ce mécanisme explique la création de réseaux « petit monde », par exemple le réseau physique d’Internet ; Phénomène de percolation: effet de seuil pour la connectivité ; Les propriétés des graphes de terrain peuvent être considérées comme une émergence résultant des interactions élémentaires entre les sommets.
13	Modèle de Watts & Strogatz
14	Phénomène de percolation
15	La percolation comme principe de base des contagions dans les réseaux
16	La résilience : percolation à l’envers On distingue : Panne = suppression de sommets au hasard Attaque = suppression de sommets choisis (par exemple des sommets d’AS de niveau 1). Une panne peut être considérée comme une « percolation à l’envers » Par exemple, Internet est résistant aux pannes et sensible aux attaques
17	La détection de communautés
18	Grandes catégories de graphes de terrain Les réseaux sociaux. Ils constituent un champ d'application ancien et important dans lequel les acteurs sont des individus ou entités sociales (associations, entreprises, pays, etc). Les liens entre eux peuvent être de différentes natures : les réseaux de connaissance (deux individus sont reliés s'ils se connaissent), les réseaux de contact physique (deux individus sont reliés s'ils ont été physiquement en contact), les réseaux de collaboration (deux individus sont reliés s'ils ont travaillé ensemble, en particulier de nombreux travaux ont étudié les collaborations scientifiques, les réseaux d'appels téléphoniques (deux individus ou numéros de téléphones sont reliés s'il y a eu un appel entre eux), les réseaux d'échanges (deux entités sont reliées si elles ont échangé un fichier ou un courrier électronique par exemple), etc.
19	Grandes catégories de graphes de terrain Les réseaux biologiques. Il en existe plusieurs types parmi lesquels nous pouvons citer: les réseaux métaboliques (les sommets sont des gènes ou des protéines qui sont liés par leurs interactions chimiques), les réseaux de neurones (chaque neurone est connecté à plusieurs autres neurones), les réseaux trophiques (les espèces d'un écosystème sont reliées pour représenter les chaînes alimentaires). Les réseaux d'infrastructure. Ils représentent des connections matérielles entre objets distribués dans un espace géographique. Nous pouvons citer les réseaux de transport (routes entre villes ou liaisons aériennes entre aéroports), les réseaux de distribution électrique (câbles entre les lieux de production et de consommation) le réseau physique de l'Internet (câbles entre ordinateurs).
20	Grandes catégories de graphes de terrain Les réseaux d'information. Ils représentent des liens abstraits de référencement entre des supports d'information. Parmi eux : les réseaux de citation d'articles les graphes du Web (les sommets sont des pages Web liées par des liens hypertextes. Les réseaux linguistiques. Ils relient les mots d'un langage donné et regroupent entre autres les réseaux des synonymie (deux mots sont reliés s'ils sont synonymes), les réseaux de co-occurrences (deux mots sont reliés s'ils apparaissent dans une même phrase d'un ouvrage), les réseaux de dictionnaires (deux mots sont liés si l'un est utilisé dans la définition de l'autre).
21	Le petit monde du CAC 40 (2003)
22	Les patrons du CAC 40 (2007)
23	Modèles d’épidémies Les petits mondes constituent un bon modèle pour étudier la propagation d'influences à travers un réseau. Par exemple, ces influences peuvent être des épidémies se propageant au sein d'une population ou des virus informatiques diffusés par messages électroniques. On distingue en général deux modes de propagation : Mode SIR (Susceptible, Infected, Removed) : dans ce mode lorsqu'un individu a été infecté, il est ensuite retiré du réseau. Ex: maladies ; Mode SIS (Susceptible, Infected, Susceptible) : dans ce mode les individus guérissent de la maladie et sont à nouveau susceptibles de l'attraper. Ex: virus informatiques ;
24	Épidémies : importance de la topologie du réseau de contacts
25	Réseau de contacts sexuels humains
26	Réseau d’interaction des protéines
27	Réseau des maladies (selon Barabasi)
28	Les réseaux des maladies et des gènes humains
29	Conclusion : à quoi tout cela sert-il ? Pour la science : Comprendre et théoriser Modéliser, prévoir Agir : Algorithmes routage data-mining Fiabilisation Épidémiologie Interactions biologiques Etc.
30	Annexes Définitions des graphes Rappel : cas d’Internet
31	Définitions de base des graphes (1) Un graphe est composé de n sommets et de m arêtes ; L’ordre du graphe n est le nombre de sommets présents dans le graphe ; Le degré k d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité ; La longueur d’une chaîne est le nombre d’arêtes qui la composent ; La distance d entre deux sommets est la plus courte longueur des chaînes qui la relient. La moyenne de ces distances est la longueur caractéristique L ; Le diamètre D d’un graphe est la plus grande distance entre deux sommets ;
32	Définitions de base des graphes (2) degré moyen d’un graphe: k=2m/n densité d’un grand graphe : proportion de m par rapport au nombre total possible m_max=n(n-1)/2: δ=m/m_{max =}2m/(n(n-1)) connexité d’un graphe: un graphe est complet si deux nœuds quelconques peuvent être reliés par une chaîne ;
33	Distribution de puissance dans Internet