Travaux pratiques - Fouille de réseaux sociaux, deuxième partie

Avertissement

Ce sujet de TP est à faire à la suite de la séance Travaux pratiques - Fouille de réseaux sociaux, première partie.

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 :

  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

Voici la liste des commandes que vous devez saisir pour revenir rapidement à la fin de la première séance.

D’abord, dans le terminal (dans le dossier tpgraphes) :

$ spark-shell --driver-memory 1g --jars lsa.jar

Puis dans ce spark-shell :

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, "<MedlineCitation ")
  conf.set(XmlInputFormat.END_TAG_KEY, "</MedlineCitation>")
  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/licencep/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 \({\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 \({\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 :

\[\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 \({\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

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 :

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) :

scala> val topicCountGraph = Graph(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: 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) })

scala> chiSquaredGraph.edges.map(x => x.attr).stats()

Vous devriez observer quelque chose comme :

(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.

scala> val interesting = chiSquaredGraph.subgraph(triplet => triplet.attr > 19.5)
scala> interesting.edges.count

Question :

Quelle fraction (approximative) des nœuds a-t-on filtré ? Qu’en concluez-vous ?

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 :

scala> val interestingComponentCounts = sortedConnectedComponents(interesting.connectedComponents())
scala> interestingComponentCounts.size

Puis, comme précédemment, regardez le top10 :

scala> interestingComponentCounts.take(10).foreach(println)

Question :

Qu’obtenez-vous ? Qu’en concluez-vous ?

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 :

scala> val interestingDegrees = interesting.degrees.cache()
scala> 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 ?

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 :

scala> 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 :

\[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.

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 \(n(n-1)/2\) si \(n\) est le nombre de voisins du noeud. On peut donc effectuer le calcul à pour chaque nœud :

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 :

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 :

scala> clusterCoefGraph.map(_._2).sum() / topicGraph.vertices.count()

Question :

Qu’obtenez-vous ? Qu’en concluez-vous ?

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),