.. _chap-tpGraphesPetitsMondes:
###############################################################
Travaux pratiques - Fouille de réseaux sociaux, deuxième partie
###############################################################
.. warning::
Ce sujet de TP est à faire à la suite de la séance :ref:`chap-tpGraphes`.
Références externes utiles :
* `Documentation Spark `_
* `Documentation API Spark en Scala `_
* `Documentation langage Scala `_
**************************************
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 :
1. 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") ;
2. 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
--------------------------------------------------
.. <<< commandes TP précédent
Voici la liste des commandes que vous devez saisir pour revenir rapidement à la
fin de la première séance.
.. raw:: html
.. container:: toggler
.. container:: ui-widget-content ui-corner-all
:name: effect
D'abord, dans le terminal :
.. code-block:: bash
[cloudera@quickstart tpgraphes]$ spark-shell --driver-memory 1g --jars lsa.jar
Puis dans ce spark-shell :
.. code-block:: scala
import com.cloudera.datascience.common.XmlInputFormat
import org.apache.spark.SparkContext
import scala.xml._
import org.apache.hadoop.io.{Text, LongWritable}
import org.apache.hadoop.conf.Configuration
import org.apache.spark.rdd.RDD
def loadMedline(sc: SparkContext, path: String) = {
@transient val conf = new Configuration()
conf.set(XmlInputFormat.START_TAG_KEY, "")
val in = sc.newAPIHadoopFile(path, classOf[XmlInputFormat], classOf[LongWritable], classOf[Text], conf)
in.map(line => line._2.toString)
}
val medline_raw = loadMedline(sc, "file:///home/cloudera/tpgraphes/medline_data")
def majorTopics(elem: Elem): Seq[String] = {
val dn = elem \\ "DescriptorName"
val mt = dn.filter(n => (n \ "@MajorTopicYN").text == "Y")
mt.map(n => n.text)
}
val mxml: RDD[Elem] = medline_raw.map(XML.loadString)
val medline: RDD[Seq[String]] = mxml.map(majorTopics).cache()
val topics: RDD[String] = medline.flatMap(mesh => mesh)
val topicPairs = medline.flatMap(t => t.sorted.combinations(2))
val cooccurs = topicPairs.map(p => (p, 1)).reduceByKey(_+_)
cooccurs.cache()
import com.google.common.hash.Hashing
def hashId(str: String) = {
Hashing.md5().hashString(str).asLong()
}
import org.apache.spark.graphx._
val vertices = topics.map(topic => (hashId(topic), topic))
val edges = cooccurs.map(p => { val (topics, cnt) = p
val ids = topics.map(hashId).sorted
Edge(ids(0), ids(1), cnt)
})
val topicGraph = Graph(vertices, edges)
topicGraph.cache()
def topNamesAndDegrees(degrees: VertexRDD[Int], topicGraph: Graph[String, Int]): Array[(String, Int)] = {
val namesAndDegrees = degrees.innerJoin(topicGraph.vertices) {
(topicId, degree, name) => (name, degree)
}
val ord = Ordering.by[(String, Int), Int](_._2)
namesAndDegrees.map(_._2).top(10)(ord)
}
def sortedConnectedComponents(connectedComponents: Graph[VertexId, _]): Seq[(VertexId, Long)] = {
val componentCounts = connectedComponents.vertices.map(_._2).countByValue
componentCounts.toSeq.sortBy(_._2).reverse
}
.. >>>
------------------------
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 :math:`{\chi}^2`
(`Wikipedia `_) 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).
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 :math:`{\chi}^2`, on suppose OO, ON, NO et NN
tirés d'une distribution inconnue. On calcule la valeur du :math:`{\chi}^2` à
partir de ces valeurs avec la formule suivante :
.. math::
\chi^2 = T \frac{(OO * NN - ON * NO)^2}{OA * NA * OB * NB}
Si nos concepts sont indépendants, on peut s'attendre à ce que la valeur obtenue
soit celle d'une loi de :math:`{\chi}^2` avec le nombre de degrés de liberté
approprié. Ici, le nombre de degrés de liberté est :math:`(r - 1)(c - 1) = 1`.
Une valeur é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, à conserver.
.. More specifically, the CDF of the one-degree chi-squared distribution yields
a p-value that is the level of confidence with which we can reject the null
hypothesis that the variables are independent.
Nous allons donc calculer cette valeur de :math:`{\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
.. code-block:: scala
scala> val T = 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 :
.. code-block:: scala
scala> val topicCountsRdd = topics.map(x => (hashId(x), 1)).reduceByKey(_+_)
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) :
.. code-block:: scala
scala> val topicCountGraph = Graph(topicCountsRdd, topicGraph.edges)
On dispose maintenant de tout ce qu'il faut pour calculer le test de
:math:`{\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 :math:`{\chi}^2` ainsi :
.. code-block:: scala
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 :
.. code-block:: scala
val chiSquaredGraph = topicCountGraph.mapTriplets(triplet => { chiSq(triplet.attr, triplet.srcAttr, triplet.dstAttr, T) })
scala> chiSquaredGraph.edges.map(x => x.attr).stats()
Vous devriez observer quelque chose comme :
.. code-block:: scala
(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 :math:`{\chi}^2` à
un degré de liberté. La valeur tabulée du :math:`{\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.
.. code-block:: scala
scala> val interesting = chiSquaredGraph.subgraph(triplet => triplet.attr > 19.5)
scala> interesting.edges.count
.. admonition:: Question :
Quelle fraction (approximative) des nœuds a-t-on filtré ? Qu'en concluez-vous ?
.. ifconfig:: tpscala in ('public')
.. admonition:: Correction :
Avec cette règle stricte, on a enlevé environ un tiers des arêtes (!). On
s'attend à ce que la plupart des nœuds soient connectés, traduisant une
relation sémantique entre les concepts, et on peut être assez satisfait de
ce filtrage.
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 :
.. code-block:: scala
scala> val interestingComponentCounts = sortedConnectedComponents(interesting.connectedComponents())
scala> interestingComponentCounts.size
Puis, comme précédemment, regardez le top10 :
.. code-block:: scala
scala> interestingComponentCounts.take(10).foreach(println)
.. admonition:: Question :
Qu'obtenez-vous ? Qu'en concluez-vous ?
.. ifconfig:: tpscala in ('public')
.. admonition:: Correction :
En enlevant un tiers des nœuds, on observe une faible variation dans la
connexité de celui-ci : il y a 3 "ilôts" supplémentaires (1042 / 1039
composantes connexes) et la taille de la plus grande a perdu seulement 3
sommets. Cela nous indique que 3 composantes faiblement connectées ont été
retirées de la composante connexe géante. Celle-ci reste de taille très
importante, le graphe est robuste au filtrage.
Intéressez-vous ensuite à la distribution de degrés, avec des commandes
similaires à ce qu'on avait vu précédemment :
.. code-block:: scala
scala> val interestingDegrees = interesting.degrees.cache()
scala> interestingDegrees.map(_._2).stats()
Ce qui doit donner (quelque chose comme) :
.. code-block:: scala
(count: 12062, mean: 28.30, stdev: 44.84, max: 1603.0, min: 1.0)
.. admonition:: Question :
Qu'obtenez-vous ? Qu'en concluez-vous ?
.. ifconfig:: tpscala in ('public')
.. admonition:: Correction :
Le degré moyen précédemment était proche de 43, il est maintenant proche de
28. Ce qui est intéressant aussi, c'est la chute de la valeur maximale du
degré, passant de plus de 3700 à 1600 ici.
Regardez ce qu'il s'est passé pour le top10 des degrés :
.. code-block:: scala
scala> topNamesAndDegrees(interestingDegrees, topicGraph).foreach(println)
Conclusion sur cette partie
---------------------------
Notre filtrage à partir d'un test d'indépendance du :math:`{\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 :math:`G` quelconque, il peut exister des
sous-ensembles de nœuds induisant un sous-graphe complet de :math:`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 :math:`V` est le nombre de triangles contenant :math:`V`, ce qui permet
d'estimer si les voisins de :math:`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 :math:`V` avec :math:`k` voisins et :math:`t` triangles, :math:`C` vaut :
.. math::
C(V) = \frac{2 * t}{k(k-1)}
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.
.. code-block:: scala
scala> val triCountGraph = topicGraph.triangleCount()
scala> 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
:math:`n(n-1)/2` si :math:`n` est le nombre de voisins du noeud. On peut donc
effectuer le calcul à pour chaque nœud :
.. code-block:: scala
scala> 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 :
.. code-block:: scala
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 :
.. code-block:: scala
scala> clusterCoefGraph.map(_._2).sum() / topicGraph.vertices.count()
.. admonition:: Question :
Qu'obtenez-vous ? Qu'en concluez-vous ?
.. ifconfig:: tpscala in ('public')
.. admonition:: Correction :
On obtient une valeur assez élevée (28%). Des graphes aléatoires
équivalents sont en général en deça des 4%.
*************
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),
.. vim : set fdm=marker:fmr=<<<,>>>:fdl=0: