Réseaux et signal : des outils de traitement du signal pour l’analyse des réseaux

Réseaux et signal : des outils de traitement du signal pour l’analyse des réseaux

Le noyau de filtre d’ondelettes

La famille d’ondelettes Ψ est entièrement déterminée, pour un graphe donné, par son noyau de filtre g et le choix des M échelles considérées. Nous verrons plus tard comment choisir ces échelles, mais nous pouvons d’ores et déjà nous intéresser à g. En classique, la construction de son équivalent ψˆ a été l’objet de beaucoup d’efforts de recherche depuis trente ans et des ondelettes de toutes formes existent maintenant, chacune plus ou moins adaptée au type de signaux étudiés. En ondelettes sur graphe, pour assurer la localisation des ondelettes, la seule contrainte qui existe sur g porte sur son comportement à l’origine qui doit être en x α (α > 1). Pour l’instant, une des formes génériques de passe-bande étudiées, est la forme “en cloche” avec un comportement en x α à l’origine et en x −β aux grandes valeurs propres. D’autres propositions plus sophistiquées ont été proposées [197, 137], qui prennent en compte le spectre particulier de chaque graphe, mais nous n’allons pas étudier ces variantes qui sont plus compliquées et demandent à calculer l’intégralité du spectre, ce qui exclut les grands graphes. Plus précisément, g est tel que : g(x; α, β, x1, x2) =    x −α 1 x α pour x < x1 p(x) pour x1 ≤ x ≤ x2 x β 2 x −β pour x > x2. (1.73) où p(x) est l’unique interpolation polynomiale cubique qui conserve la continuité de g et de sa dérivée g 0 . α, β, x1, x2 sont les paramètres du filtre. Nous verrons aussi dans le deuxième chapitre comment les ajuster en fonction de ce que l’on cherche à analyser, mais pour l’instant, dans le but d’illustrer les ondelettes, nous les choisissons comme dans [96] : α = β = 2, x1 = 1 et x2 = 2. La Fig. 1.10a montre le noyau de filtre dilaté par 5 paramètres d’échelle différents. On définit ces filtres comme des fonctions continues par commodité, mais en réalité, ces filtres sont discrets quand on les applique à des graphes : ils sont définis uniquement sur le spectre du graphe. On montre la version discrète du même banc de filtre sur la Fig. 1.10b, en utilisant le spectre du graphe de la Fig. 1.2.  1. Généralités sur les graphes et le traitement du signal sur graphes Banc de filtres continus : 0 0.5 1 1.5 2 0 2 4 6 λ g(s λ j ) j=1 j=2 j=3 j=4 j=5 a) Banc de filtres discrets : 0 0.5 1 1.5 2 0 2 4 6 λ g(s λ j ) j=1 j=2 j=3 j=4 j=5 b) Figure 1.10: a) Version continue et b) discrète (définie sur le spectre du graphe de la Fig. 1.2) d’un banc de filtres passe-bande définissant des ondelettes sur graphe. 3.6 Quelques illustrations Illustrons quelques ondelettes du graphe de la Fig. 1.2 correspondant au banc de filtres de la Fig. 1.10b. Dans un premier temps, on dessine sur la Fig. 1.11 dix ondelettes : les ondelettes centrées aux nœuds 8 et 15 aux cinq échelles considérées dans le banc de filtres. Par exemple, on observe très bien l’oscillation de l’ondelette ψs1,15. Aussi, on observe qu’à petite échelle et loin du nœud autour duquel l’ondelette est centrée, il n’y a presque plus d’énergie (les nœuds sont alors en vert clair). À grandes échelles, au contraire, l’énergie est distribuée sur tout le graphe, à tel point qu’il n’est plus possible de savoir à l’œil sur quel nœud l’ondelette est censée être centrée. Pour donner une intuition sur le comportement de la transformée en ondelettes, on représente sur la Fig. 1.12 un signal très simple (le Dirac centré sur le nœud 15) et sa transformée en ondelettes. La transformée est représentée sous forme de matrice où l’élément de la ligne i et de la colonne j est le coefficient d’ondelette W fsi,j calculé à l’échelle si et au nœud j. On observe l’équivalent de la cascade d’énergie centrée autour des singularités d’un signal dans une transformée en ondelettes classique. Sauf que dans notre cas, il faut reconstruire mentalement la cascade étant donné qu’il n’y a pas d’ordre naturel dans l’espace des nœuds

Détection multiéchelle de communautés à l’aide d’ondelettes

« No man is an island, entire of itself ; every man is a piece of the continent, a part of the main. » – John Donne, No Man Is An Island La première partie de ce chapitre est dédiée à une courte présentation générale sur la notion de communautés et l’utilité de leur détection. Nous rappellerons dans la deuxième partie quelques travaux classiques de partitionnement d’un graphe en communautés. Le choix des sujets abordés pourra paraître arbitraire au lecteur au fait de la volumineuse littérature sur le sujet : en effet, le but n’est pas de proposer une liste exhaustive des méthodes existantes, mais d’introduire le lecteur à quelques outils de base auxquels nous ferons appel par la suite. Ces deux premières parties sont surtout destinées au lecteur peu familier de la notion de communauté. La troisième partie, en revanche, porte plus précisément sur les méthodes multiéchelles existantes de détection en communautés et permet de poser précisément le problème abordé. Les quatre parties suivantes (parties 4, 5, 6 et 7) sont le cœur de ce chapitre et proposent une nouvelle méthode multiéchelle basée sur les ondelettes sur graphe. Elles reprennent avec plus de détails les idées essentielles déjà publiées dans [212, 216, 215, 211, 210]. La huitième partie présente un point de vue original sur une partie des méthodes multiéchelles existantes, les regroupant toutes sous un formalisme unique de modularité filtrée. Nous évoquerons dans la neuvième et dernière partie de ce chapitre les perspectives de ces travaux

Une communauté dans un graphe

Qu’est-ce qu’une communauté ?

Une communauté est un ensemble de nœuds plus connectés entre eux qu’avec le reste du graphe. Cette définition, nécessairement floue, a l’avantage d’être assez générale pour correspondre à une majorité des définitions, souvent plus précises, que donne chaque auteur travaillant sur le sujet. À mon sens, la notion même de communautés ne peut être envisagée sans le but que l’on se donne, sans savoir pourquoi on cherche des communautés. Il me semble que chercher des communautés dans un graphe, c’est chercher à regrouper assez de nœuds ensemble pour permettre la lecture et l’analyse du graphe, mais ne pas trop les regrouper pour garder au moins une partie des détails structurels du graphe. Il faudra donc garder en tête que la recherche en communautés est un équilibre à trouver entre trop de détails rendant le graphe difficilement analysable et trop d’agrégation qui fait éventuellement disparaître l’information pertinente du graphe. Cette recherche de communautés est donc naturellement spécifique au contexte du graphe étudié, à la finesse de l’analyse souhaitée, même à l’expérimentateur qui devra choisir parmi toutes les méthodes de recherche de communautés et donc introduire un biais à ce niveau là. Prenons un exemple classique et simple pour illustrer ce propos : le graphe social d’un club de karaté [229] observé sur une période de 3 ans dans les années 1970 dans le cadre d’une étude sur l’apparition de clivages dans un réseau social. Le graphe est binaire et composé de 34 nœuds, chacun correspondant à un membre du club, et un lien existe entre deux nœuds si les deux personnes ont des interactions sociales en dehors du club de karaté. Ce graphe est représenté sur la Fig. 2.1a. Considérons le nœud colorié de la Fig. 2.1b. Dans quelle communauté appartient-il ? Quelque part, chacune des 4 propositions (Figs. 2.1c-f) 

Détection multiéchelle de communautés à l’aide d’ondelettes 

Graphe du club de karaté de Zachary [229] : chaque nœud représente un des membres du club et un lien existe entre deux nœuds si les deux membres ont des interactions sociales en dehors du club. Considérons le nœud colorié de l’illustration b). Dans quelle communauté appartient-il ? Les nœuds coloriés des illustrations c-f) sont autant de réponses possibles. de communautés (représentées par les nœuds coloriés sur les figures) correspondent à une interprétation possible de la définition de communauté donnée au début de cette partie. Et aucune de ces propositions n’est mieux que l’autre : les propositions c et d sont justifiées parce que ce sont des cliques, c’est-à-dire des groupes de nœuds tous connectés les uns aux autres ; ce n’est pas le cas pour la proposition e mais celle-ci regroupe 5 nœuds qui sont tous connectés au reste du graphe par l’intermédiaire d’un seul nœud ; et la proposition f coupe le graphe en deux parties plus ou moins égales et peu connectées entre elles. C’est d’ailleurs cette dernière proposition qui correspond à la vérité de terrain discutée dans [229] : ce réseau social s’est finalement clivé en deux (selon les couleurs de f) et les deux sous-réseaux se sont finalement retrouvés dans deux clubs de karaté différents. Chacune des propositions de communautés est justifiable et justifiée. Et c’est uniquement l’étude de terrain et donc le contexte du graphe qui nous permet de savoir quelle acceptation du sens de communauté est pertinente. 

De l’utilité de la recherche de communautés

À la lecture du cas précédent, on est en droit de questionner l’utilité de la recherche de communautés : définition floue, multiplicité des solutions, nécessité de connaître le contexte du graphe pour savoir quel sens donner à la notion de communauté. . . En fait, pour se convaincre de son utilité, il faut comprendre la recherche 42 1. Une communauté dans un graphe en communautés comme une prospection, qui ne donnera jamais dans les graphes réels une réponse claire et définitive, mais plutôt un ensemble de réponses, autant d’hypothèses plausibles qu’il faudra ensuite étudier en détail avec les outils spécifiques au domaine d’application. Dans ce sens, la recherche de communautés est une méthode de fouille de données, où la donnée est un graphe.

Une brève histoire de la recherche de communautés

C’est en sociologie qu’est né le domaine de la recherche de communautés, même si aujourd’hui le domaine d’application est bien plus vaste. En effet, quelques travaux précurseurs de sociologues [54, 225, 175, 103] cherchent à grouper les humains en fonction de leurs opinions politiques, de leurs interactions sociales, etc. . . Dans les années 1960/1970, un groupe de chercheurs à la frontière entre les mathématiques et l’informatique a attaqué le problème de partitionnement de graphes [123, 82], essayant de formaliser le concept de communauté et développer des algorithmes de détection automatique, proposant par exemple le théorème flot-max/coupe-min (mincut/maxflow en anglais) qui stipule que le flot maximum pouvant aller d’un nœud s à un nœud t est égal à la somme minimale des poids des liens à retirer du graphe pour séparer s de t. Un des développements de ce groupe de chercheurs est le partitionnement spectral, initié par Donath et Hoffman [59] et poursuivi et amélioré depuis lors (voir le tutoriel de von Luxburg [221] pour une présentation plus générale du partitionnement spectral). Dans les années 2000, Girvan et Newman [89], plutôt ancrés en physique statistique sur réseaux, proposent une mesure de qualité d’une partition donnée appelée modularité. Cette mesure, couplée à des algorithmes très rapides comme celui de Louvain [32] et à des données de plus en plus accessibles et nombreuses, ont fait exploser le nombre de travaux sur la recherche de communautés. Aujourd’hui, ce domaine est à la frontière de l’informatique, des mathématiques, de la physique statistique, et de la science des réseaux. L’étendue des travaux dans ce domaine pourra être mesurée dans la revue de Fortunato [83]. 1.4 Partitionnement d’un graphe en communautés Le problème classique dans le domaine de la détection de communautés dans un graphe, est de trouver une partition de l’ensemble des nœuds V qui sépare le mieux le graphe en communautés. Par définition, une telle partition, notée P , est un ensemble de communautés deux à deux disjointes, dont la réunion équivaut à V : P = {Ci} tq ∀(i, j) Ci ∩ Cj = ∅ et [ i Ci = V. (2.1) Des améliorations peuvent être apportées à l’énoncé de ce problème, par exemple en autorisant les communautés à être recouvrantes, c’est-à-dire qu’un même nœud peut appartenir à plusieurs communautés. Le recouvrement existe bel et bien dans de nombreuses applications, mais les algorithmes sont souvent d’abord présentés sur le cas “simple” sans recouvrement avant d’être généralisés au cas avec recouvrement. Étant donné que nous allons présenter un nouvel algorithme dans la suite, nous examinerons ici uniquement des communautés non-recouvrantes et laisserons le recouvrement pour des travaux futurs. 43 2. Détection multiéchelle de communautés à l’aide d’ondelettes 2 Partitionner un graphe en communautés Nous référons le lecteur à la revue de Fortunato [83] qui recense et synthétise une grande partie de l’imposant état de l’art dans le domaine de la détection de communautés (recouvrantes ou non). Nous évoquerons ici uniquement quelques éléments utiles à la compréhension de la suite. Tout d’abord, posons le problème de la détection d’une partition d’un graphe en communautés. Nous nous cantonnons ici aux cas plus simples de graphes non-dirigés et de la recherche de communautés non-recouvrantes, c’est-à-dire d’une partition du graphe au sens stricte du terme. Nous nous posons le problème du “meilleur découpage” d’un graphe en communautés disjointes, et il se décompose, dans de nombreux travaux sur la question, en deux temps : 1. définir ce qu’est le “meilleur découpage” d’un graphe en communautés, c’està-dire proposer une mesure de la qualité d’une partition donnée. Nous allons présenter dans la partie 2.1 la mesure la plus connue appelée modularité. 2. maximiser cette mesure sur l’ensemble des partitions possibles. En pratique, cela est impossible étant donné qu’il existe beaucoup ( 1 N+1 .