Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Théorie des graphes et réseaux sociaux

No description
by

Adrien Lemaitre

on 29 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Théorie des graphes et réseaux sociaux

Les réseaux sociaux et la théorie des graphes Conclusion Hubs et Autorités I – Découverte de la théorie des graphes et des cliques. Concept : Un site A contient un lien vers un site B
-> Correspond a un "vote" de A pour B, plus B reçoit de vote, mieux il est référencé. 1 – Les 6 degré de séparation de Milgram
Réseau « small world » en anglais 2 - Descriptions de la théorie des graphes et des cliques. B A1 A2 A1,A2,.. = Hubs
B = Autorité Le PageRank La formule : PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) Elle admet l'hypothèse que toute personne sur la planète peut être reliée à n’importe quelle autre, au travers d’un enchaînement d’au plus cinq maillons. C'est un algorithme récursif Relation avec les réseaux sociaux PR(A) : le PageRank de la page A
PR(Tn) : le PageRank de la page Tn
C(Tn) : le nombre de liens émis sur la page Tn
d : tous les « votes » sont additionnés, mais pour en limiter l’importance, le total est multiplié par ce coefficient d’amortissement (0.85)
1 - d : Permet de garantir que la moyenne des PageRank de l’ensemble des pages du Web sera de 1. Les notations : Basée sur un échantillon de 721 millions de personnes (les utilisateurs de Facebook de l'époque), on sait désormais, chaque personne est reliée en moyenne par une chaîne de 4,74 relations à n'importe quelle autre. Exemple simple : Une page sans lien entrant : P(A)=(1 - 0.85) + 0.85*(0) = 0.15 Remarque : PageRank probablement établie sur
échelle logarithmique, et évoluant dans le temps... Pour simplifier les calculs, on choisi un log10. Le PageRank : Chaque niveau de PR est 10 fois plus difficile a obtenirque le nveau précédent dû au log10 Tableau indicatif : PageRange Affiché (log base 10) PageRank réel (calculé)
PR0 0=< PR < 1
PR1 1 =< PR < 10
PR2 10 =< PR < 100
PR3 100 =< PR < 1,000
PR4 1,000 =< PR < 10,000
...
PR10 1,000,000,000 =< PR 10,000,000,000 PageRank Notions à comprendre : Pour connaître le Pr d'une page A, il faut connaître le PR des pages Tn qui renvoient vers A ("crédit"), mais aussi le PR des pages renvoyant vers Tn, etc..


D'où la notion d'algorithme récursif...


-> Objectif : converger vers le résultat sans connaitre le PR final des pages Tn émettant vers A PageRank : Exemple 2 pages A et B pointant l'une vers l'autre.
Chaque page a un lien sortant donc C(A)=C(B)=1 A B hubs et Autorités Algorithme HITS : Objectif : Trouver les pages qui sont des "autorités" quant a la requête de l'utilisateur.

Inconveniant : Le calcul des autorités est fait pour chaque utilisateur, donc plus coûteux et complexe que le PageRank. Algorithme HITS A partir de l'ensemble des pages trouvés via une recherche, on forme un ensemble : Pages
vers
R_theta Pages
renvoyées
via
R_theta Introduction S_theta R_theta S_theta = grand ensemble
R_theta = ensemble des pages trouvées Les recherches de Milgram
La théorie des graphes, explications et vocabulaire:
Cliques
Hubs et autorité
La théorie des graphes à travers deux logiciels différents:
Vansande.org
Navicrawler Algorithme HITS On cherche :
-a(p) qui mesure la qualité d'une page en tant que receveuse de liens

-h(p) qui mesure la qualité d'une page en tant que page de liens Algorithme HITS Méthode : - On fixe d'abord a(p)=1 et h(p)=1
-On défini la matrice A correspondant aux liens entre les pages
-puis on effectue cette suite d'opération : ...Et on réitère ! Algorithme hits Exemple : J'effectue la recherche : "rabais postal vélo" Algorithme hits Interprétation : - Grâce à a(p), index.html à visiter en 1er, puis velos.html mais PAS produit.html

-Grâce à h(p), produit.html est la
meilleure page de liens (avec 2 liens) Le Navicrawler En quoi consiste le Navicrawler?

Comment fonctionne-t-il?

Quel est le rapprochement avec la théorie des graphes? Conclusion Conclusion

Plus les réseaux sociaux, comme Facebook par exemple grandissent, plus les gens sont connectés entre eux. 2- Application aux réseaux sociaux 1 .Utilité des cliques maximales dans les réseaux sociaux « vansande.org » : outil graphique qui explore notre réseau social.

-Lié avec le réseau social Facebook
-Permet de rassembler tous nos « amis » ou toutes les personnes liées à nous et les regrouper automatiquement en parties selon nos affinités. Un noeud Un noeud Un arc ( orienté) Notions de clique C'est un sous graphe complet, c’est-à-dire, un graphe dans un autre graphe plus grand que lui-même dont tous les sommets sont tous reliés 2 à 2 entre eux. Remarque

Graphe non orientés, sens des relations entre les différents nœoeuds non pris en compte (les arêtes du graphe ne sont pas des flèches) Explication

Plus la taille de la clique est important plus la personne aura la probabilité d’être en relation avec nous, et donc sera proposé dans les suggestions avant tous les autres. Conclusion

Le but de l’analyse des réseaux sociaux : calculer ces cliques maximales avec des matrices pour les traiter et réussir à exploiter les résultats pour mettre en relation les personnes dans la vraie vie. Dans un cas plus complexe La théorie des réseaux, dont l'étude est la diktyologie, s'intéresse aux graphes présents dans le monde réel, tels que :

•le World Wide Web,
•l'Internet,
•les réseaux de neurones,
•les réseaux sociaux
•etc. Applications pratiques très diverses :

•Optimisation des réseaux de transport ;
•Transports routiers ou transports d’information ;
•Conception de réseaux électriques, de réseaux de communication ;
•Mécanique statistique, formules chimiques, informatique théorique, sciences sociales, géographies, architecture, etc. Hubs et autorités Méthodes : PageRank : Etablie une note de 0 à 10 pour l'importance d'un site web en se basant sur les connexions entrantes dont il dispose.
Limites : Ne permet pas de relever les pages de références. A a Algorithme HITS R_theta=velo.html
S_theta=index.html + produits.html A= 0 1 1
1 0 0
0 1 0 index.html produits.html velos.html index.html produits.html velos.html Conclusion

Le but de l’analyse des réseaux sociaux : calculer ces cliques maximales avec des matrices pour les traiter et réussir à exploiter les résultats pour mettre en relation les personnes dans la vraie vie. Dans un cas plus complexe Expliquer les phénomènes présents sur les réseaux inter connectés

Comprendre l'internet (gestion de la vie privée)

Recherche opératonnelle outils de sciences sociales Clique maximale : clique la plus étendue.

Clique maximum : plus grande des cliques maximales Relation avec les réseaux sociaux
Full transcript