Impact de l’équilibrage bi-stochastique sur la détection de communautés

Télécharger le fichier pdf d’un mémoire de fin d’études

Critère d’Owsinski et Zadrozny

Le critère qu’Owsinsky et Zadrozny décrivent dans leur article [43] est une généralisa-tion du critère de Condorcet. A l’origine, il servait à résoudre des problèmes d’agrégation de préférence, c’est-à-dire avec des matrices relationnelles de Condorcet représentant une relation d’ordre – et donc non symétriques.
Dans la thèse de Patricia Conde-Céspedes [41], il a été démontré que, pour un graphe simple, le partitionnement maximisant le critère de Zahn est un partitionnement tel que dans chacune de ses classes, le nombre d’arêtes intra-classe est au moins égal à la moitié du nombre d’arêtes que possède le graphe complet des sommets de la classe. Cette propriété est assez restrictive, et le critère d’Oswinski et Zadrozny propose un critère semblable, mais avec un paramètre permettant de choisir le pourcentage d’arêtes intra-classes du meilleur partitionnement dans le cas d’un graphe simple. Ainsi, pour une matrice de Condorcet A et un partitionnement X donné, FOZ(A; X) = i;j (1 )ai;jxi;j + ai;jxi;j avec A la matrice complémentaire de la matrice de Condorcet définie comme à la section précédente, et 2 [0; 1]. Pour chaque classe du partitionnement maximisant ce critère, le nombre d’arêtes intra-classe est au moins 100 % du nombre d’arêtes du graphe complet correspondant.
Ce critère présente le même problème que le critère de Condorcet quant à sa générali-sation : il est nécessaire de connaître le problème de Condorcet initial pour l’utiliser. Il est cependant possible d’envisager ce critère comme un critère de Zahn paramétré.
Ce choix du paramètre correspond justement à un cas où l’utilisateur souhaite fixer la densité des communautés. Or, nous souhaitons ne pas supposer que nous avons une connaissance a priori sur l’aspect des communautés que nous souhaitons obtenir. Ce critère ne sera donc pas repris dans la suite de notre étude.

Critère de modularité équilibrée

Ce critère a été introduit pour les graphes simples par Patricia Conde-Céspedes dans [61]. Comme son nom l’indique, il permet d’équilibrer le critère de Newman et Girvan : on rappelle qu’étant donné un graphe et un partitionnement, le critère de Newman et Girvan compare le nombre des arêtes intra-communautés du graphe avec ce même nombre d’arêtes dans un graphe aléatoire. Le critère de modularité équilibré compare en plus le nombre d’arêtes inter-communautés du graphe avec cette valeur dans le même graphe aléatoire.
Nous allons voir en détail comment est construit ce critère, puis nous proposerons une généralisation différente de celle décrite par Romain Campigotto et al dans [53] pour un graphe à pondération quelconque, avant d’adapter cette généralisation au cas spécifique des matrices bi-stochastiques.

Comparaison de critères dans le cas des matrices bistochastiques

Cette section est dédiée à la comparaison des différents critères présentés à la Sec-tion 1.1, lorsque le graphe étudié est un graphe de transition, c’est-à-dire que la matrice des poids est stochastique – et donc bi-stochastique, puisque l’on s’intéresse à des graphes non orientés, et donc à des matrices symétriques.
Dans toute cette section, nous étudions une matrice A 2 Sn(R+) bi-stochastique. Nous commençons par simplifier et exprimer les différents critères sous une forme canonique permettant une comparaison plus aisée. Ensuite, nous comparons les différences entre les propriétés des partitionnements favorisant ces critères.

Rappel et homogénéisation des critères

Nous allons ici rappeler les critères vus à la section précédente, et les mettre sous forme d’un fonction à maximiser. En d’autres termes, lorsque le meilleur partitionnement est obtenu par minimisation du critère, nous allons modifier ce critère, afin que le meilleur partitionnement soit systématiquement obtenu par la maximisation du critère. En outre, nous allons faire les simplifications qui interviennent étant donné que la matrice étudiée est bi-stochastique.
Comme cela est proposé dans le Chapitre 6 de la thèse de Patricia Conde-Céspedes [41], nous ré-écrirons ces critères sous la forme canonique X F (A; X) = ( i;j i;j)xi;j (1.18).
Les coefficients i;j et i;j sont appelés respectivement terme d’accord positif et terme d’accord négatif. La raison de ce choix est que la comparaison des critères deux à deux est plus aisée via la comparaison de ces termes d’accord positifs et négatifs.

Impact de l’équilibrage bi-stochastique sur la détection de communautés

Nous rappelons que le but initial de cette étude est d’observer l’impact de l’équilibrage doublement stochastique de la matrice d’adjacence d’un réseau sur la mise en évidence de sa structure en communautés. Dans le cas de la détection de communautés au sens classique du terme, un tel équilibrage change fondamentalement la nature du problème. En effet, les valeurs numériques de la matrice doublement stochastique ont une grande influence dans la détection de ses blocs, tandis que la matrice d’adjacence est par essence binaire, puisqu’elle représente l’existence ou la non existence d’un lien entre deux sommets. Il est donc crucial de vérifier que l’équilibrage doublement stochastique des matrices d’adjacence des réseaux ne compromet pas la structure de communautés du-dit réseau.
Dans les sections précédentes, nous avons présenté un certain nombre de mesures de modularité, qui ont été généralisées au cas des graphes pondérés quand cela était possible, et en particulier adaptées au cas des matrices doublement stochastiques. Ici, nous allons comparer les résultats du découpage en communautés de réseaux simples (non pondérés, non orientés, et sans self-loop) dans le cas des différentes mesures de modularité présentées précédemment, dans leur version binaire ainsi que dans leur version numérique, en les appliquant aux matrices d’adjacence des réseaux, préalablement mises sous forme doublement stochastique.

Quelques définitions et théorèmes

Un certain nombre de points de ce chapitre font appel à des notions méritant d’être rappelées ou introduites. C’est le but de cette section.

Bi-stochasticité et vecteur de Perron-Frobenius

Nous commençons par des définitions et théorèmes en lien avec la propriété de bi-stochasticité des matrices. La plupart de ces résultats sont des rappels de la section introductive Définitions et Notations.
Définition 7. Matrice doublement stochastique : Une matrice carrée à coefficients non négatifs A 2 Rn n est dite doublement stochastique ou bi-stochastique si 8 <Ae = e ; :AT e = e e = (1; :::; 1)T 2 Rn..
Remarque 12. Toute matrice stochastique et symétrique est donc bi-stochastique.
Définition 8. Equilibrage doublement stochastique : Soit une matrice carrée à coefficients non négatifs A 2 Rn n, trouver un équilibrage doublement stochastique pour A signifie trouver deux vecteurs r; c 2 R+n tels que 8 <D(r)AD(c)e = e ; :D(c)AT D(r)e = e avec D : Rn ! Rn n l’opérateur transformant un vecteur en une matrice diagonale, et e = (1; :::; 1)T 2 Rn, où r et c sont appelés facteurs d’équilibrage de A.
Dans la suite, nous rappelons le théorème de Sinkhorn-Knopp [30], et les deux définitions sur la structure des matrices nécessaires à sa compréhension. Ces définitions peuvent être trouvées dans [34].
Définition 9. Bi-irréductibilité ou entière indécomposabilité : Une matrice A 2 Rn n est dite bi-irréductible s’il n’existe pas deux matrices de permutation R; Q telles que :  » # A1 A1;2 RAQ = 0 A2 avec A1; A2 deux matrices carrées non vides.
Remarque 13. Cela signifie qu’il n’existe pas de permutations indépendantes des lignes et des colonnes permettant de mettre A sous forme triangulaire par blocs.

Equilibrage doublement stochastique

Dans cette section, nous nous intéressons au partitionnement des matrices doublement stochastiques via leurs vecteurs singuliers dominants. Notamment, nous allons voir que, si la matrice a une structure par blocs, alors ces vecteurs doivent présenter un aspect constant par morceaux permettant de détecter cette structure.
L’équilibrage doublement stochastique pour du partitionnement a déjà été proposé dans [24]. Cependant, après la phase d’équilibrage, le partitionnement est effectué par un algorithme fusionnant tour à tour les noeuds les plus fortement connectés, et ne tient pas compte de la structure constante par morceaux des vecteurs singuliers dominants. En outre, dans l’article [12], les auteurs se servent de l’équilibrage doublement stochastique pour du partitionnement par détection de la structure constante par morceaux, non pas des vecteurs singuliers mais des facteurs d’équilibrage utilisés pour rendre la matrice doublement stochastique. Enfin, les auteurs de [38] utilisent aussi une matrice doublement stochastique pour de la classification non supervisée, mais dans leur cas, cette caractéristique est celle de la matrice représentant le partitionnement, qu’ils choisissent comme la solution minimisant une divergence de Bregman avec la matrice d’affinité, après relaxation de la contrainte forçant la matrice du partitionnement à être à valeurs dans f0; 1g.
Dans la suite de cette section, nous montrons en quoi les vecteurs singuliers dominants d’une matrice doublement stochastique sont particulièrement adaptés à la détection de sa structure par blocs. Ensuite, nous discutons sur la nécessité de perturber la diagonale de la matrice lorsqu’elle est vide, notamment afin de permettre son équilibrage.

Vecteurs singuliers dominants et structures par blocs des ma- trices bi-stochastiques

Le théorème suivant est une conséquence directe du théorème 3 dit de Perron-Frobenius.
Théorème 5. Soit S 2 Rn n symétrique, irréductible et doublement stochastique. Alors 1 est valeur propre de S de multiplicité 1, et le vecteur propre associé est un multiple de e = (1:::1)T . Par ailleurs, si S est symétriquement permutable en une matrice bloc diagonale avec k blocs irréductibles, alors 1 est valeur propre de multiplicité k, et une base du sous-espace propre associé est : fv(1); v(2); : : : ; v(k)g; où vq(p) pour p 2 f1; : : : ; kg est tel que vq(p) = ( 0; sinon: 1; si q est dans le bloc p Ainsi, le calcul d’un vecteur propre associé à 1 d’une telle matrice S sera de la forme x = a1v(1) + a2v(2) + + akv(k): En forçant x 2 e?, on peut raisonnablement supposer que ai 6= aj; 8i 6= j. Puisque ces vecteurs forment une partition disjointe de f1; : : : ; ng, il est possible d’identifier la contribution de chaque bloc précisément, et donc de caractériser les partitions de manière exacte, en utilisant l’ensemble fa1; : : : ; akg. En effet, réordonner le vecteur singulier suivant un ordre adapté à la structure par blocs de S le mettra sous forme constante par morceaux. Cette idée est proche de celle exploitée dans [80], où les auteurs se servent de l’ordre croissant des vecteurs singuliers dominants de deux équilibrages stochastiques d’une matrice A afin de visualiser la structure par blocs de A.
Comme corollaire du théorème 5, considérons une matrice doublement stochastique non symétrique P. Alors PPT et PT P sont toutes deux symétriques et doublement stochastiques, on peut donc leur appliquer le théorème 5. Ainsi, si PPT ou PT P possède une structure par blocs, le vecteur singulier gauche ou droit dominant de P aura une contribution de chaque vecteur de la base associée, et il sera possible, comme précédemment, d’identifier la structure par blocs de lignes et/ou de colonnes de P.
Notre algorithme est conçu pour des matrices qui sont des perturbations de matrices à support total – cf la définition 10. Les vecteurs singuliers dominants de telles matrices devraient avoir une structure proche d’une structure constante par morceaux. Ainsi, en réordonnant dans l’ordre croissant les vecteurs calculés, on devrait faire apparaître une structure proche d’une structure par blocs, ou au moins des blocs de lignes ou de colonnes faiblement corrélés les uns avec les autres. Le calcul de l’équilibrage doublement stochastique se fait avec la méthode de Newton décrite dans [62]. Cette méthode est peu coûteuse car elle ne fait intervenir que des produits matrices–vecteurs.
Remarque 17. Dans le cadre de cette thèse, nous ne nous intéressons pas aux problé-matiques du calcul performant des vecteurs singuliers dominants. Il s’agit essentiellement de justifier théoriquement et empiriquement les différentes étapes de l’algorithme, et les matrices auxquelles nous le confrontons sont de taille relativement restreinte. Pour cette raison, nous nous permettons de traiter quelques (disons d) vecteurs singuliers dominants d’une matrice P en calculant les d vecteurs propres dominants de P orthogonaux à e si P est symétrique, et les d vecteurs propres dominants de PPT , respectivement PT P, orthogonaux au vecteur e, si P n’est pas symétrique. Dans les deux cas, nous utilisons la fonction eigs de Matlab.
Il est évident que cette problématique devra être étudiée afin que l’algorithme soit en mesure de traiter des matrices de grande taille. En effet, le calcul des éléments singuliers d’une matrice a un coût numérique certain, et la qualité de la décomposition (totale ou partielle) obtenue dépend à la fois de la méthode utilisée et des caractéristiques de la matrice (séparabilité de ses valeurs singulières notamment). Plusieurs méthodes peuvent être envisagées ou associées, parmi lesquelles :
— Les algorithmes basés sur la bi-diagonalisation de Golub et Kahan [81], dont l’idée principale est de simplifier le problème de la décomposition en éléments singuliers de la matrice A en s’intéressant à la décomposition en éléments singuliers d’une matrice bi-diagonale B, obtenue par décomposition de A sous la forme A = XBY; où X; Y sont des matrices unitaires. La décomposition en éléments singuliers de B peut se faire de nombreuses façons [82]. En particulier, si l’on ne souhaite qu’une décomposition partielle, on peut utiliser les algorithmes ci-dessous.
— Les algorithmes basés sur la méthode de la puissance itérée par blocs – cf par exemple [83] –, où un groupe de vecteurs singuliers dominants est calculé de manière itérative, en multipliant un groupe de vecteurs par une puissance de A, puis en orthonormalisant ces vecteurs. Ces méthodes peuvent être couplées avec une projection de Rayleigh-Ritz pour accélérer la convergence [84].
— Les algorithmes itératifs basés sur les méthodes de Krylov, qui, couplés avec des filtres polynômiaux, permettent de trouver les vecteurs singuliers dominants de A de façon relativement efficace – cf par exemple [83].

Table des matières

1 Impact de l’équilibrage bi-stochastique sur les réseaux 
1.1 Généralisation de certains critères au cas des graphes pondérés
1.1.1 Critère de Zahn
1.1.2 Critère de Newman et Girvan
1.1.3 Critère de Condorcet
1.1.4 Critère d’Owsinski et Zadrozny
1.1.5 Critère de Demaine et Immorlica
1.1.6 Critère de modularité équilibrée
1.1.7 Critère d’écart à l’indétermination
1.1.8 Critère d’écart à l’uniformité
1.2 Comparaison de critères dans le cas des matrices bi-stochastiques
1.2.1 Rappel et homogénéisation des critères
1.2.2 Comparaison des critères
1.3 Impact de l’équilibrage bi-stochastique sur la détection de communautés
1.3.1 Démarche expérimentale
1.3.2 Résultats expérimentaux
1.4 Conclusion
2 Un Algorithme spectral 
2.1 Quelques définitions et théorèmes
2.1.1 Bi-stochasticité et vecteur de Perron-Frobenius
2.1.2 Connectivité algébrique des graphes et vecteur de Fiedler
2.1.3 Décomposition en valeurs singulières :
2.2 Equilibrage doublement stochastique
2.2.1 Vecteurs singuliers dominants et structures par blocs des matrices bi-stochastiques
2.2.2 Perturbation de la diagonale avant équilibrage
2.3 Identification des classes
2.3.1 Problèmes liés au filtre
2.3.2 Information apportée par les autres vecteurs
2.3.3 Approche bloc à bloc
2.3.4 Version finale : approche multi blocs
2.4 SVD projetée
2.5 Amélioration des classes
2.5.1 Superposition des partitions.
2.5.2 Mesure de qualité.
2.6 Synthèse de l’algorithme spectral
2.7 Application à la détection de formes
2.8 Conclusions
3 Applications 
3.1 Application à la détection de communautés
3.1.1 Prétraitement des données
3.1.2 Post-traitement des données
3.1.3 Comparaison entre deux structure en communautés
3.1.4 Bancs d’essais
3.1.5 Les Algorithmes
3.1.6 Tests Numériques
3.1.7 Conclusion
3.2 Préconditionnement de systèmes linéaires
3.2.1 Préconditionneur de Zhu et Sameh (ZS)
3.2.2 Notre premier préconditionneur (V0)
3.2.3 Notre second préconditionneur (V1)
3.2.4 Conclusion et perspectives
3.3 Traitement automatique du langage naturel
3.3.1 Représentation vectorielle du langage
3.3.2 Base de données STAC
3.3.3 Détection des actes de dialogues (DA)
3.3.4 Procédure de réduction des dimensions
3.4 Conclusion : d’autres types de structures
Conclusion et perspectives 
A Impact de l’équilibrage bi-stochastique sur les réseaux 
A.1 Annexe 1
A.2 Annexe 2
B Un Algorithme spectral 
B.1 Annexe 1
C Equilibrage bi-stochastique et matrices rectangulaires 
C.1 Annexe 1
C.1.1 Convergence de symscale1
C.1.2 Trouver la structure par blocs de la matrice initiale
Bibliographie 

Télécharger le rapport complet