advertisement

IC05 cours 1

75 %
25 %
advertisement
Information about IC05 cours 1

Published on March 17, 2008

Author: Eldarion

Source: slideshare.net

Description

Théorie des graphes et topologie des réseaux
advertisement

IC 05 / semestre printemps 2008 IC 05 / semestre printemps 2008 Franck.ghitalla Département TSH Président de WebAtlas [email_address]

IC 05 / semestre printemps 2008 Forme(s) et type(s) de réseaux ( between order and randomness ) Agrégats et loi de puissance ( information geography ) Dynamics ( information IN and ON nets ) Corrélation structure/contenu ( information distribution on power-law topology )

Forme(s) et type(s) de réseaux ( between order and randomness )

Agrégats et loi de puissance ( information geography )

Dynamics ( information IN and ON nets )

Corrélation structure/contenu ( information distribution on power-law topology )

Cadres conceptuels A.-L. BARABASI linked - the new science of networks , new ed. 2005. S. JONHSON - emergence: the connected lives of ants, brains, cities, and software, 2002. Théorie des graphes D. WATTS six degrees - the science of a connected age , 2004. S. STROGATZ - sync: the emerging science of spontaneous order , 2004. M. NEWMAN - the structure and dynamics of networks, 2003. Web-Mining S. CHAKRABARTI mining the web , 2002. J. KLEINBERG - algorithm design, 2006. InfoViz B. SHNEIDERMAN - readings in information visualization: using vision to think, 1999. Ouvrages de référence en Network Sciences IC 05 / semestre printemps 2008

IC 05 / semestre printemps 2008 The problem : in social networks, web graphs or cells organisation (and even each complex system), we have to understand the presence of two contradictory properties . « On the one hand, the network should display a large culstering coefficient , meaning that on average a person’s friends are far more likely to know each other than two people chosen at random. On the other hand, it should be possible to connect two people chosen at random via a chain of only a few intermediaries  .» (D; Watts, p77, Six Degrees)

IC 05 / semestre printemps 2008 « Most of networks (not only social networks) display what we call clustering, which is really just to say that most people’s friends are also to some extent friends of each other »… » (D. Watts, p40, Six Degrees ) 1) Clusters, proximity and long distances

Dans un réseau social, si chaque agent a 100 amis, et eux-mêmes 100, etc...A 5 degrés de distance, on arrive à 9 milliards. A priori, mathématiquement, ce type d'expansion permet de comprendre les fameux « 6 degrees » constants (à gauche). Cependant, dans les réseaux sociaux ou sur le web pour les sites/pages, il existe une forte redondance en termes de structure : mes amis ont de grandes chances d'être aussi les amis de mes amis (disons, dans le même « cluster social » ou communauté). IC 05 / semestre printemps 2008 Most of real networks (web, biology, social organization…) are highly clustered

IC 05 / semestre printemps 2008 Graphe de sites Graphe de mots-clef

La structure très clusterisée du web se mesure aisément à partir de calculs de densité pour la distribution de la connectivité hypertexte entre sites. C'est l'un des principes développés par J. Kleinberg dès 1996 pour la conception de l'algorithme HITS (Hypertext Induced Topic Search). IC 05 / semestre printemps 2008

IC 05 / semestre printemps 2008 « Some of the properties of extremely complicated systems can be understood without knowing anything about their detailed structure or governing rules… » (D. Watts, p65, Six Degrees ) 2) Randomness, universality and complex systems

(gauche) Random Graphe (non-orienté et orienté) (droite) Random Graph - (Rényi) IC 05 / semestre printemps 2008 « A random graph is, as the name might suggest, a network of nodes connected by links in a purely random fashion » (D. Watts)

IC 05 / semestre printemps 2008 « All we needed to do was find a way to tune each network between complete order and complete disorder in a way that it traced through all the various intermediate stages » (D. Watts, p86, Six Degrees ) 3) Small World

IC 05 / semestre printemps 2008 Clustering Degree = High Distance Degree = High Clustering Degree = Low Distance Degree = Low Clustering Degree = High Distance Degree = Low

IC 05 / semestre printemps 2008 A space of possible worlds – the parameter we can tune from 0 to 1, from randomness to order – in wich, at one end of the spectrum individuals always make new friends through thier current friends and, at the other end, they never do. « …in the middle, there is a version of reality. » (D. Watts). The «  Beta Model , the order-randomness-spectrum » (D. Watts, S. Strogatz) Order from 0 to 1 Randomness from 0 to 1 En moyenne, pour un network de 1 million de nœuds distribué en mode régulier (avec pour chaque nœud 100 voisins proches (« 50 à gauche, 50 à droite »), la distribution de 5 liens en mode random fait chuter les distances moyennes de 50%. Il faut multiplier ce chiffre par 10 (soit 5x10 = 50) pour faire chuter la moyenne encore de 50 %. Et ainsi de suite…Les effets sont donc décroissants.

IC 05 / semestre printemps 2008 3 propriétés des web-graphs a) de forme b) de distribution de l’ordre c) de domaines (mots, liens, acteurs)

IC 05 / semestre printemps 2008

IC 05 / semestre printemps 2008 IC 05 / semestre printemps 2008 Franck.ghitalla Département TSH Président de WebAtlas [email_address]

Add a comment

Related pages

Barcelona IC05 - Surgical management of malpositioned lenses

* 5. How useful was the course for your clinical practice? (1 = poor, 5 = excellent)
Read more

Version: 7.0 Immunisations for Healthcare Workers

IC 5 Immunisation for healthcare Workers Policy No: IC05 Version: 7.0 Name of Policy: Immunisations for Healthcare Workers Policy Effective From: 28/06/2012
Read more

AACPDM-1015-273 IC05 Survey - SurveyMonkey

AACPDM-1015-273 IC05 IC 5: Customized Employment as an ... 1) To understand the ... The course followed description in the program.
Read more

Information Circular IC05-62 - CBOE.com

Information Circular IC05-62 DATE: May 26, 2005 TO: ... Of course, we will also accept ... Members may participate by calling 1-888-552-9483, passcode:
Read more

INFECTION CONTROL - University of Massachusetts Medical School

INFECTION CONTROL Information: Memorial: 334-6078 office Jaquith 3 Bunker University: 856- 3293 office: HA-802 ... Gloves are worn to 1.
Read more

RST CE: ISS 2015 Schedule IC05 - University of Pittsburgh

RST CE Providing Quality Evidence-Based Continuing Education in Rehabilitation Science and Technology. Online/On-Demand Webinars, RESNA Exam Review Course ...
Read more

346 056F Open Interest v2 - CBOE.com

CBOE Open Interest Newsletter—June Liska + Associates #346.056F 02 June 2005 Revision 0 Information Circular IC05-67 June 2005 Marketing Initiatives ...
Read more

Intermediate Building Contract - The Joint Contracts ...

The JCT Intermediate Building Contract is designed for construction projects involving all the recognised trades and skills of the industry, where fairly det
Read more