.. _chap-tpGraphesPetitsMondes: ############################################################### Travaux pratiques - Fouille de réseaux sociaux, deuxième partie ############################################################### .. only:: html .. warning:: Ce sujet de TP est à faire à la suite de la séance :ref:`chap-tpGraphes`. .. container:: notebook .. image:: _static/zeppelin_classic_logo.png :class: svg-inline `Cahier Zeppelin `_ 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. .. only:: jupyter .. code-block:: bash %%bash mkdir -p /zeppelin/notebook/medline_data cd /zeppelin/notebook/medline_data if not ls medsamp2016{a,b}.xml 1>/dev/null 2>&1; then wget -nc ftp://ftp.nlm.nih.gov/nlmdata/sample/medline/medsamp2016{a,b}.xml.gz; else echo "les fichiers sont là, passez à la cellule suivante"; fi .. code-block:: bash %%bash cd /zeppelin/notebook/medline_data if not ls medsamp2016{c,d}.xml 1>/dev/null 2>&1; then wget -nc ftp://ftp.nlm.nih.gov/nlmdata/sample/medline/medsamp2016{c,d}.xml.gz; else echo "les fichiers sont là, passez à la cellule suivante"; fi .. code-block:: bash %%bash cd /zeppelin/notebook/medline_data if not ls medsamp2016{e,f}.xml 1>/dev/null 2>&1; then wget -nc ftp://ftp.nlm.nih.gov/nlmdata/sample/medline/medsamp2016{e,f}.xml.gz; else echo "les fichiers sont là, passez à la cellule suivante"; fi .. code-block:: bash %%bash cd /zeppelin/notebook/medline_data if not ls medsamp2016{g,h}.xml 1>/dev/null 2>&1; then wget -nc ftp://ftp.nlm.nih.gov/nlmdata/sample/medline/medsamp2016{g,h}.xml.gz; else echo "les fichiers sont là, passez à la cellule suivante"; fi Décompressons les fichiers et regardons leur taille. .. code-block:: bash %%bash cd /zeppelin/notebook/medline_data gunzip *.gz ls -ltr medsamp* .. 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:///zeppelin/notebook/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 } .. only:: html .. raw:: html .. container:: toggler .. container:: ui-widget-content ui-corner-all :name: effect D'abord, dans le terminal (dans le dossier `tpgraphes`) : .. code-block:: bash $ 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/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. .. only:: html 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` 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 :math:`{\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 :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 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 :math:`{\chi}^2` à un degré de liberté donne un niveau de confiance permettant de rejeter l'hypothèse `nulle` que les variables sont indépendantes. .. 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. .. only:: jupyter 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 : .. code-block:: scala print(s"""-\tOuiB\tNonB\tTotalA\t\nOuiA\tOO\tON\tOA\t\nNonA\tNO\tNN\tNA\t\nTotalB\tOB\tNB\tT\t\n""") 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 : .. 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 \\\\\\\\( {\\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. .. 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 \\\\\\\\( {\\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 val T = medline.count() println(s"T : ${T}\n") 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 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 val topicCountGraph = Graph(topicCountsRdd, topicGraph.edges) .. only:: html 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 : .. only:: jupyter 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 : .. 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) }) chiSquaredGraph.edges.map(x => x.attr).stats() Vous devriez observer quelque chose formaté comme ceci mais avec des valeurs différentes : .. 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. .. only:: html 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). .. only:: jupyter 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. .. code-block:: scala val interesting = chiSquaredGraph.subgraph(triplet => triplet.attr > 19.5) 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 val interestingComponentCounts = sortedConnectedComponents(interesting.connectedComponents()) println(s"Nb composantes connexes : ${interestingComponentCounts.size}\n") Puis, comme précédemment, regardez le top10 : .. code-block:: 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 val interestingDegrees = interesting.degrees.cache() 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 "top 10" des nœuds de plus forts degrés : .. code-block:: scala topNamesAndDegrees(interestingDegrees, topicGraph).foreach(println) Conclusion sur cette partie --------------------------- .. only:: html 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… .. only:: jupyter 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 ************************************************************* .. only:: html 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 : .. only:: jupyter 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 : .. 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 val triCountGraph = topicGraph.triangleCount() triCountGraph.vertices.map(x => x._2).stats() .. only:: html 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 : .. only:: jupyter 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 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 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: