Travaux pratiques - Fouille de réseaux sociaux, deuxième partie¶
Environnement de travail¶
Avertissement
Ce sujet de TP est à faire à la suite de la séance Travaux pratiques - Analyse d’un grand graphe (Medline).
Vous trouverez ici une variante de ce TP utilisant le langage Scala.
Références externes utiles :
Introduction aux réseaux Petits Mondes¶
C’est notamment avec l’avènement de l’Internet (puis du Web et des réseaux sociaux en ligne) que des graphes de grande taille ont été collectés, permettant d’observer la formation de réseaux réels. Il est rapidement apparu que ces derniers avaient des propriétés différentes de celles des modèles idéaux étudiés en théorie des graphes traditionnelle. L’un des premiers articles sur le sujet, publié en 1998 par Duncan Watts et Steven Strogatz, s’appelait « Collective dynamics of small world networks », et présentait un premier modèle mathématique disposant des propriétés observées sur ces graphes de terrain, à savoir :
la plupart des nœuds ont un degré faible et appartiennent à un sous-ensemble dense de nœuds (autrement dit : une fraction importante des voisins d’un nœud sont connectés entre eux, ou encore : « mes amis sont amis entre eux ») ;
malgré cette première propriété, il est possible d’atteindre n’importe quel autre nœud du graphe assez facilement, c’est-à-dire en passant par un faible nombre d’intermédiaires (mathématiquement, cela correspond à une moyenne des plus courts chemins faible).
Depuis cet article originel, des réseaux réels ont été étudiés dans des domaines très variés et nombre d’entre eux possèdent ces propriétés : on les appelle des « réseaux petits mondes ».
Objectifs du TP¶
Dans un premier temps, on poursuit l’étude abordée dans la séance précédente, en examinant la structure du graphe après avoir proposé un filtrage des nœuds.
Ensuite, on s’intéresse à une métrique définie par Watts et Strogatz permettant de voir à quel point les deux propriétés ci-dessus sont vraies pour le graphe étudié. Nous allons utiliser GraphX pour effectuer ce calcul, qui repose sur le nombre de triangles.
Filtrer le graphe¶
Revenir à l’état de la fin de la séance précédente¶
Voici la liste des commandes que vous devez saisir pour revenir rapidement à la fin de la première séance.
Une nouvelle pondération¶
Dans notre graphe, les arêtes sont pour le moment pondérées par le nombre de fois qu’une paire de concepts est apparue dans les différents articles (si A et B sont apparus dans ensemble dans 216 articles, l’arête A-B a pour attribut 216). On n’a pas utilisé cette valeur auparavant.
En construisant le graphe comme on l’a fait, on n’a donc pas distingué quelles sont les paires de concepts utilisées conjointement car elles ont un sens ensemble, et celles qui apparaissent fréquemment dans tous les documents. (pensez par analogie avec la fréquence seule des mots dans de la fouille de texte, et à l’amélioration fournie par le score TF-IDF). Nous allons donc rechercher une manière de pondérer qui tienne compte de cela, en essayant d’évaluer dans quelle mesure la co-occurrence de deux sujets est intéressante. On va utiliser pour cela un test du \({\chi}^2\) pour mesurer si l’occurence d’un concept est indépendante de celle d’un autre (et préserver les paires de concepts non indépendants). Vous trouverez sur Wikipedia un rappel de ce qu’est un test de \({\chi}^2\), il sera utilisé ici dans sa variante corrigée par F. Yates.
Pour une paire (A,B) de concepts, on a la table de contingence suivante qui représente les co-occurrences des majorsTopics dans notre base Medline :
Oui B |
Non B |
Total A |
|
|---|---|---|---|
Oui A |
OO |
ON |
OA |
Non A |
NO |
NN |
NA |
Total B |
OB |
NB |
T |
Dans cette table, OO, ON, NO et NN représentent les valeurs brutes de présence/absence des concepts A et B. OA et NA désignent les sommes pour des lignes pour le concept A (respectivement OB, NB pour B). T est le nombre total de documents. Pour notre test \({\chi}^2\), on suppose OO, ON, NO et NN tirés d’une distribution inconnue. On calcule la valeur du \({\chi}^2\) à partir de ces valeurs avec la formule suivante :
Si nos concepts sont indépendants, on peut s’attendre à ce que la valeur obtenue soit celle d’une loi de \({\chi}^2\) avec le nombre de degrés de liberté approprié. Ici, le nombre de degrés de liberté est \((r - 1)(c - 1) = 1\).
Une valeur plus élevée indique que les variables ont moins de chances d’être indépendantes, ce qui pour nous caractérise une paire intéressante de concepts, que l’on souhaitera conserver.
Note
plus précisément, la p-value associée la distribution (CDF) du \({\chi}^2\) à un degré de liberté donne un niveau de confiance permettant de rejeter l’hypothèse nulle que les variables sont indépendantes.
Nous allons donc calculer cette valeur de \({\chi}^2\) pour chacune des paires/arêtes de notre graphe de co-occurrences.
Traitement des arêtes¶
La partie la plus facile à calculer, que l’on a déjà croisée dans la séance précédente, c’est T, le nombre total de documents. On peut l’obtenir via
medline.count()
De même, il est assez facile de retrouver combien de documents contiennent chaque concept, puisqu’on s’en est servi pour créer topicCounts. On va cependant cette fois conserver l’information dans un RDD :
topicCountsRdd = topics.map(lambda p: (p, 1)).reduceByKey(add)
Une fois que l’on a ce VertexRDD avec les nombres d’occurrences, on peut l’utiliser pour créer un nouveau graphe, dans lequel il nous servira d’ensemble de sommets (et l’on garde l’ensemble des arêtes précédent) :
topicGraph = GraphFrame(topicCountsRdd, topicGraph.edges)
On dispose maintenant de tout ce qu’il faut pour calculer le test de \({\chi}^2\) pour chacune des arêtes de topicCountGraph. Il nous faut ici combiner des informations stockées à la fois sur les sommets (le nombre de fois que chaque sujet apparaît) ainsi que sur les arêtes (le nombre de fois qu’une paire apparaît dans un document). GraphX nous permet d’effectuer ce type de calculs à l’aide d’une structure de données appelée EdgeTriplet[VD, ED], qui encapsule de l’information sur les arêtes et les sommets dans un seul objet (avec les IDs de chaque sommet). En utilisant ce EdgeTriplet sur notre topicCountGraph, on peut calculer le \({\chi}^2\) ainsi :
def chiSq(oo, ob, oa, t):
nb = t - ob
na = t - oa
on = oa - oo
no = ob - oo
nn = t - no - on - oo
inner = (oo * nn - on * no) - t / 2.0
res = t * math.pow(inner, 2) / (oa * na * ob * nb)
return res
def chiSq(OO: Int, OB: Int, OA: Int, T: Long): Double = {
val NB = T - OB
val NA = T - OA
val ON = OA - OO
val NO = OB - OO
val NN = T - NO - ON - OO
val inner = (OO * NN - ON * NO) - T / 2.0
T * math.pow(inner, 2) / (OA * NA * OB * NB)
}
On peut ensuite combiner cette méthode avec l’opérateur mapTriplets, ce qui va nous retourner la valeur du test pour chacune des paires. On pourra ensuite, avec stats(), avoir une idée de la distribution des valeurs pour les arêtes de notre graphe :
val chiSquaredGraph = topicCountGraph.mapTriplets(triplet => { chiSq(triplet.attr, triplet.srcAttr, triplet.dstAttr, T) })
chiSquaredGraph.edges.map(x => x.attr).stats()
Vous devriez observer quelque chose formaté comme ceci mais avec des valeurs différentes :
Exemple :
(count: 259920, mean: 546.97, stdev: 3428.85, max: 222305.79, min: 0.0)
Maintenant que l’on a calculé cette valeur, on va s’en servir pour filtrer les arêtes qui ne semblent pas fournir d’information pertinente, selon le principe décrit ci-dessus. Cette métrique prend des valeurs très différentes sur l’ensemble des arêtes, et l’on peut du coup essayer d’employer un filtre très strict pour éliminer les arêtes peu importantes.
Pour une table de contingence 2x2 dans laquelle il n’y aurait pas de relation entre les variables, la valeur du test doit suivre une loi de \({\chi}^2\) à un degré de liberté. La valeur tabulée du \({\chi}^2\) à un degré de liberté pour 0.00001 est de 19.5, on peut essayer avec cette valeur comme limite pour éliminer des arêtes (ce qui ne nous laissera donc que des arêtes dont on est très sûrs qu’elles représentent des co-occurrences significatives).
Pour effectuer le filtrage, on utilise la méthode subgraph, qui requiert en paramètre une fonction (anonyme) retournant un booléen à partir d’un EdgeTriplet, pour déterminer quelles arêtes sont à préserver.
val interesting = chiSquaredGraph.subgraph(triplet => triplet.attr > 19.5)
interesting.edges.count
Question :
Quelle fraction (approximative) des nœuds a-t-on filtré ? Qu’en concluez-vous ?
Dans la section suivante, on examine l’impact de ce filtrage sur la structure de notre graphe.
Analyse du graphe filtré¶
Commencez par réutiliser la méthode qui nous avait permis d’obtenir les composantes connexes auparavant :
val interestingComponentCounts = sortedConnectedComponents(interesting.connectedComponents())
println(s"Nb composantes connexes : ${interestingComponentCounts.size}\n")
Puis, comme précédemment, regardez le top10 :
interestingComponentCounts.take(10).foreach(println)
Question :
Qu’obtenez-vous ? Qu’en concluez-vous ?
Intéressez-vous ensuite à la distribution de degrés, avec des commandes similaires à ce qu’on avait vu précédemment :
val interestingDegrees = interesting.degrees.cache()
interestingDegrees.map(_._2).stats()
Ce qui doit donner (quelque chose comme) :
(count: 12062, mean: 28.30, stdev: 44.84, max: 1603.0, min: 1.0)
Question :
Qu’obtenez-vous ? Qu’en concluez-vous ?
Regardez ce qu’il s’est passé pour le « top 10 » des nœuds de plus forts degrés :
topNamesAndDegrees(interestingDegrees, topicGraph).foreach(println)
Conclusion sur cette partie¶
Notre filtrage à partir d’un test d’indépendance du \({\chi}^2\) a eu l’effet escompté : il nous a permis d’éliminer les arêtes de notre graphe qui reliaient des concepts génériques entre eux, en préservant les associations porteuses d’information. Bien entendu, il serait maintenant intéressant d’explorer différentes valeurs de filtrage, pour voir l’impact qu’elles peuvent avoir sur la connexité du graphe et la distribution de degrés. Il existe peut-être une valeur particulière à partir de laquelle la composante connexe « éclate » en petites parties, à moins qu’elle ne « fonde » progressivement, comme un gigantesque iceberg…
Réseaux Petits Mondes : Cliques et coefficients de clustering¶
On dit qu’un graphe est complet si chaque sommet est connecté à chacun des autres par une arête. Dans un graphe \(G\) quelconque, il peut exister des sous-ensembles de nœuds induisant un sous-graphe complet de \(G\) : on appelle cet ensemble de sommet une clique. La présence de cliques de grande taille dans un graphe indique qu’il possède une structure locale similaire aux grands réseaux réels. Cependant, trouver des cliques est un problème NP-difficile (donc on ne sait pas en général trouver de solution en temps raisonnable). On a donc développé des métriques moins coûteuses pour estimer la densité locale, comme le calcul du nombre de triangles à un sommet. Un triangle est simplement un graphe complet de trois sommets et le nombre de triangles au sommet \(V\) est le nombre de triangles contenant \(V\), ce qui permet d’estimer si les voisins de \(V\) sont connectés entre eux. Watts et Strogatz ont ainsi défini le coefficient de clustering local, la fraction du nombre de triangles existants et du nombre total de triangles possibles. Pour un sommet \(V\) avec \(k\) voisins et \(t\) triangles, \(C\) vaut :
On peut utiliser GraphX pour calculer ce coefficient de clustering sur le graphe que l’on a construit, grâce à la méthode triangleCount fournie.
val triCountGraph = topicGraph.triangleCount()
triCountGraph.vertices.map(x => x._2).stats()
Cela nous permet d’obtenir le numérateur du coefficient de clustering pour chaque nœud. Pour le dénominateur, il nous faut connaître le nombre total de triangles possibles contenant chaque sommet. Rappelez-vous que ce nombre vaut \(n(n-1)/2\) si \(n\) est le nombre de voisins du noeud. On peut donc effectuer le calcul à pour chaque nœud :
val maxTrisGraph = topicGraph.degrees.mapValues(d => d * (d - 1) / 2.0)
Avec triCountGraph et maxTrisGraph (ce sont des VertexRDD), on peut donc calculer le coefficient de clustering pour chaque nœud :
val clusterCoefGraph = triCountGraph.vertices.innerJoin(maxTrisGraph) {
(vertexId, triCount, maxTris) => {
if (maxTris == 0) 0
else triCount / maxTris
}
}
Ce qui nous intéresse maintenant, c’est le coefficient de clustering moyen de ce graphe :
clusterCoefGraph.map(_._2).sum() / topicGraph.vertices.count()
Question :
Qu’observez-vous ? Qu’en concluez-vous ?
Bibliographie¶
Karau, H., A. Konwinski, P. Wendell et M. Zaharia, Learning Spark, O’Reilly, 2015.
Ryza, S., U. Laserson, S. Owen and J. Wills, Advanced Analytics with Spark, O’Reilly, 2010.
Large-Scale Structure of a Network of Co-Occurring MeSH Terms: Statistical Analysis of Macroscopic Properties, by Kastrin et al. (2014),