These Nacim Chikhi v8.0
These Nacim Chikhi v8.0
These Nacim Chikhi v8.0
Fabien GANDON, Chargé de Recherche
(HDR), INRIA Sophia Antipolis
Hamamache KHEDDOUCI, Professeur,
Université Claude Bernard Lyon 1
(Proverbe arabe)
1
2
Remerciements
3
4
Résumé
5
Abstract
6
Table des matières
Introduction .............................................................................................. 11
Motivations ................................................................................................................ 11
Les graphes de documents ......................................................................................... 12
Publications dans le cadre de la thèse........................................................................ 14
Organisation de la thèse............................................................................................. 15
7
2.3.1 HITS et la décomposition en valeurs singulières..................................................... 51
2.3.2 Décomposition de la matrice d’adjacence en matrices non négatives ..................... 53
2.3.3 Détails de l’algorithme............................................................................................. 54
2.3.4 Résultats avec les graphes jouets ............................................................................. 54
2.3.5 Effet du nombre de dimensions et convergence de l’algorithme............................. 56
2.4 L’algorithme DocRank ........................................................................................ 56
2.4.1 Principe .................................................................................................................... 56
2.4.2 Distributions stationnaires ....................................................................................... 57
2.4.3 Détails de l’algorithme............................................................................................. 60
2.4.4 Exemples jouets ....................................................................................................... 60
2.5 Environnement d’expérimentation ...................................................................... 61
2.5.1 Graphes de documents utilisés................................................................................. 61
2.5.2 Mesures d’évaluation ............................................................................................... 63
2.5.3 Algorithmes comparés ............................................................................................. 64
2.6 Résultats expérimentaux ...................................................................................... 65
2.6.1 Evaluation de la qualité du classement .................................................................... 65
2.6.2 Evaluation de la diversité thématique ...................................................................... 73
2.7 Bilan..................................................................................................................... 74
8
3.3.1 Introduction aux modèles génératifs ........................................................................ 90
3.3.2 Approches basées sur le modèle de mélange de multinomiales .............................. 98
3.3.3 Approches basées sur le modèle PLSA ................................................................. 102
3.3.4 Approches basées sur le modèle SBM ................................................................... 110
3.4 Synthèse des approches présentées et leur adéquation à l’analyse
des graphes de documents ................................................................................. 115
9
Table des %otations
%otion Description
x 2
Norme L2 du vecteur x ( x 2 = ∑ x2 )
i =1 i
K Nombre de communautés
x ~ Mult ( k , p ) k tirages suivant une loi multinomiale de paramètre p
x ~ Bern ( p ) Tirage selon une loi de Bernoulli de paramètre p
x ~ Dir (α ) Tirage selon une loi de Dirichlet de paramètre α
10
Introduction
Introduction
Motivations
L’infobésité (ou surcharge d’information) constitue sans doute l’un des plus grands défis
auxquels nous sommes confrontés aujourd’hui. Que nous soyons industriels, chercheurs
scientifiques ou simples utilisateurs du web, nous faisons tous face à cette immense quantité
d’information disponible dont l’appréhension, l’ampleur, le contenu (et donc l’accès) nous
échappent. Même une cartographie de l’existant dépasse nos capacités de traitement cognitif.
Certaines avancées technologiques accentuent même ce phénomène à l’instar du Web 2.0 qui
permet à n’importe quel internaute de déposer facilement et rapidement de l’information sur
le web. Devant une telle situation, il devient plus que jamais nécessaire de disposer de
moyens permettant de caractériser ces ressources documentaires afin d’en faciliter l’accès. La
caractérisation peut porter sur les sources documentaires elles-mêmes, prises séparément,
comme le proposent le Web 2.0 ou même le web sémantique. Mais on peut aussi vouloir
caractériser globalement ces grandes quantités de ressources, comme un tout auquel on peut
attribuer des propriétés. C’est ce dernier aspect qui nous intéresse dans cette thèse. Deux
critères peuvent être envisagés pour caractériser ces grandes collections de documents.
Le premier de ces critères est celui de la (plus ou moins grande) pertinence que l’on
accordera à un document pour répondre à une interrogation donnée (i.e. à une requête). La
solution la plus naturelle pour estimer cette pertinence est de mesurer la proximité entre le
contenu d’un document et le contenu de la requête. Une solution radicalement différente
consiste à caractériser a priori l’importance des différents documents [Getoor and Diehl 05].
Pour estimer cette importance, on a coutume de considérer qu’un document est d’autant plus
important qu’il existe un grand nombre de documents qui pointent vers lui [Garfield 70],[Liu
06]. Si l’on considère le graphe des liens entre documents (que l’on appellera graphe de
documents tout court), on s’aperçoit que les documents importants sont alors ceux qui
11
Introduction
occupent des positions centrales (ou stratégiques) dans un tel graphe. Dans le développement
de cette thèse, nous privilégierons cette deuxième solution.
Le second de ces critères vient de la capacité à structurer de grandes collections de
documents en groupes traitant chacun d’un même sujet ou d’une même thématique. Là
encore, la majorité des techniques existantes s’est focalisée sur l’utilisation des contenus
textuels. Le regroupement obtenu correspond alors à des ensembles de documents qui sont à
la fois fortement similaires au sein d’un même groupe et faiblement similaires aux documents
d’autres groupes. Cependant, dans le cadre de cette thèse, nous nous intéresserons à
l’utilisation des liens entre documents pour le regroupement automatique de documents. Les
liens entre documents ont été utilisés depuis longtemps en bibliométrie pour l’évaluation des
revues scientifiques par exemple. La plupart des techniques existantes basées sur les liens se
contentent, en fait, d’utiliser d’anciennes notions issues de la bibliométrie telles que la co-
citation [Small 73] ou le couplage bibliographique [Kessler 63]. Nous pensons pourtant que
les liens contribuent à la sémantique d’un document, et qu’ils constituent par conséquent une
source d’information précieuse qu’il serait important de prendre en compte lors de la tâche
d’identification de thématiques. Concrètement, le regroupement obtenu en se basant sur les
liens correspond à des ensembles de documents qui ont plus de liens à l’intérieur qu’à
l’extérieur de chacun des groupes [Getoor and Diehl 05]. En observant le graphe de liens
entre documents, on s’aperçoit que ces groupes de documents sont ceux qui partagent des
préoccupations communes, on dit qu’ils constituent des communautés à l’intérieur du graphe.
Ces deux critères méritent d’être distingués. Le premier est sensé se focaliser sur
quelques documents qui l’emportent, toutes thématiques confondues. Le second concerne tous
les documents en les classant selon des thématiques particulières. Pour autant, ces deux
critères ne sont pas indépendants. Le calcul de documents centraux dans des graphes de
documents est souvent biaisé par la présence de communautés dans le graphe. Inversement,
une fois des communautés identifiées, il est nécessaire d’identifier les éléments centraux de
chacune d’elles afin de faciliter leur interprétation.
Les objets que nous manipulerons tout au long de cette thèse sont des graphes de
documents. Un graphe de documents est un graphe où les sommets correspondent à des
documents et les liens à des références créées par le(s) auteur(s) des documents. Des exemples
de graphes de documents incluent les graphes de citations (i.e. d’articles scientifiques reliés
par des références bibliographiques) [Price 65][Scharnhorst and Thelwall 05], les graphes du
web (i.e. de pages web reliées par des hyperliens) [Kleinberg 99b][Scharnhorst and Thelwall
05] et les graphes de brevets [Yoon and Park 04].
De nombreuses études empiriques réalisées ces dernières années sur des graphes dans
divers domaines (biologie, sciences sociales, web, etc.) ont montré que ces graphes possèdent
des propriétés communes qui les distinguent des graphes aléatoires tels que les graphes
d’Erdös-Rényi [Fortunato 10]. Ces graphes "non aléatoires" sont connus sous les noms de
réseaux complexes [Bornholdt and Schuster 03], de graphes d’interaction [Guillaume 04] ou
encore de grands graphes de terrain [Pons 07]. Les graphes de documents sont justement un
12
Introduction
cas particulier de graphes complexes ayant des particularités. Une des caractéristiques les plus
évidentes concerne l’orientation des liens dans un graphe de documents. En effet, alors que la
plupart des graphes complexes étudiés sont non-orientés, les graphes de documents sont
orientés. Cette orientation possède une sémantique bien précise qu’il serait incorrect de
négliger. En plus de l’orientation, nous présentons ci-dessous trois des propriétés les plus
importantes des graphes de documents.
Une caractéristique importante des graphes de documents est que la distribution des
degrés de leurs nœuds (i.e. du nombre de liens) ne suit pas une loi de Poisson comme c’est le
cas des graphes aléatoires d’Erdös-Rényi, mais suit plutôt une loi de puissance [Redner
98][Albert et al. 99][Broder et al. 00]. Cette particularité a en effet été rapportée par de
nombreuses études empiriques qui se sont intéressées à la distribution des degrés dans des
graphes de documents. La loi de puissance énonce que la probabilité, P(k), qu’un nœud ait un
degré égal exactement à k, est donnée par [Caldarelli 07] :
P ( k ) = Z .k − λ
où Z est une constante de normalisation et λ, l’exposant de la loi, est un réel dont la valeur est
généralement comprise entre 2 et 3. Cette loi indique donc que le nombre de nœuds ayant un
degré égal à k est proportionnel à k − λ . Elle traduit également le fait que dans les réseaux
complexes, un petit nombre (non négligeable) de nœuds possède un fort degré alors qu’un
grand nombre de nœuds possède un faible degré.
Une autre interprétation de la distribution des degrés en loi de puissance est que, dans un
graphe, les nœuds jouent des rôles différents. Il est alors particulièrement intéressant de
repérer les nœuds qui occupent une position stratégique dans le graphe. La Partie I de cette
thèse est d’ailleurs consacrée à cette problématique.
Notons enfin que les graphes possédant une telle propriété (i.e. distribution des degrés en
loi de puissance) sont appelés graphes sans échelle (ou graphes à invariance d’échelle ou
encore scale-free graphs) [Barabasi 09].
Une autre propriété des graphes de documents concerne le faible degré moyen [Albert et
al. 99][Broder et al. 00]. Pour un graphe orienté et sans boucles G = (V , E ) d’ordre & et de
taille M, le degré moyen est donné par :
d moy = M
&
Le fait que les graphes de documents aient un degré moyen faible implique que l’on peut
considérer que le nombre de liens dans un graphe est linéaire (i.e. du même ordre) par rapport
au nombre de nœuds.
13
Introduction
La densité d’un graphe est égale à la proportion de liens existants par rapport au nombre
total de liens possibles. Pour le graphe orienté et sans boucles G, sa densité δ est donnée par :
δ= M
& ( & − 1)
Le nombre de liens M étant du même ordre que le nombre de nœuds &, la densité δ tend
par conséquent vers des valeurs très faibles lorsque le nombre de nœuds croit. En d’autres
termes, la densité d’un graphe est inversement proportionnelle au nombre de ses sommets.
Une appellation souvent utilisée pour désigner les graphes ayant une faible densité est
celle de graphes creux (ou "sparse") en référence à leur matrice d’adjacence qui est creuse
(i.e. contient beaucoup de zéros).
Ci =
∑ ∑
j∈Vi k∈Vi
a jk
di ( d i − 1)
où di est le degré total du nœud i (degré entrant + degré sortant), Vi = { j : aij = 1 ∨ a ji = 1} est
l’ensemble des nœuds voisins du nœud i.
Le coefficient de regroupement global d’un graphe est égal à la moyenne des coefficients
de regroupement de tous ses nœuds i.e.
&
C (G ) = 1 ∑C i
& i =1
14
Introduction
Organisation de la thèse
Cette thèse est organisée en deux parties qui peuvent être lues de manière indépendante.
La première partie est consacrée au calcul de centralité dans les graphes de documents tandis
que la deuxième partie traite la problématique de l’identification de structures de
communautés (ISC) dans les graphes de documents. Chacune de ces deux parties est à son
tour composée de deux chapitres : un chapitre d’état de l’art critique et un chapitre qui
présente les nouvelles approches proposées dans cette thèse ainsi que leur évaluation.
15
Introduction
16
Chapitre 1 Etat de l’Art sur le Calcul de Centralité
17
Chapitre 1 La notion de centralité dans les graphes
Dans le cadre de l’analyse des réseaux sociaux, les chercheurs ont remarqué que certains
acteurs jouent un rôle plus "important" que d’autres. Certaines personnes avaient par exemple
beaucoup de contacts au sein du réseau alors que d’autres personnes n’en avaient que très peu.
Ces personnes occupent en fait une position stratégique (ou avantageuse) au sein du réseau
social ; suivant les cas, ces personnes peuvent être plus influentes ou avoir une plus grande
notoriété. Ce phénomène n’est pas propre aux réseaux sociaux puisqu’on le retrouve dans
beaucoup d’autres types de graphes. Par exemple, dans les réseaux de communication,
certains nœuds jouent un rôle très important dans la communication entre les nœuds alors que
d’autres nœuds n’ont aucune influence sur le réseau. Ce phénomène s’explique par la nature
de ces réseaux qui sont des réseaux complexes et dont la distribution des nœuds suit une loi
de puissance [Caldarelli 07]. Cette loi de probabilité signifie qu’un petit nombre de nœuds
possède beaucoup de connexions (i.e. de liens) alors qu’un grand nombre de nœuds possède
peu de liens avec les autres nœuds du réseau. En d’autres termes, les nœuds n’ont pas les
mêmes rôles au sein du réseau.
Dans le but de quantifier cette notion d’importance d’un nœud dans un graphe, les
chercheurs ont proposé plusieurs définitions connues sous le nom de mesures de centralité
[Koschützki et al. 05]. En effet, l’identification des nœuds centraux dans un graphe représente
un enjeu important dans plusieurs domaines. En reprenant l’exemple des réseaux de
communication, le fait de connaître les nœuds importants permet d’adopter des stratégies afin
de mieux protéger ces nœuds qui jouent un rôle essentiel dans la communication au sein du
réseau. Si l’on considère à titre d’exemple le réseau de communication de la figure 1.1, on
remarque que si le nœud B tombe en panne, la communication entre les différents nœuds ne
sera pas affectée. Par contre, si le nœud A tombe en panne, cela engendrerait un grand
problème de communication puisque tous les nœuds se retrouveront isolés.
En recherche d’information, le classement (ou "ranking") des résultats est basé non
seulement sur une mesure de similarité entre la requête utilisateur et les documents mais aussi
sur le degré d’importance (ou d’autorité) d’un document dans le graphe de citations.
D
C E
B A F
I G
H
18
Chapitre 1 La notion de centralité dans les graphes
Lors de l’étude de la notion de centralité, il est important de distinguer le cas des graphes
orientés du cas des graphes non-orientés. Dans les graphes orientés, les nœuds possèdent deux
types de liens, à savoir des liens entrants et des liens sortants. Pour une définition donnée de
la notion de centralité, chaque nœud aura alors deux mesures d’importance : une mesure
relative à ses liens sortants, appelée mesure de centralité, d’influence, d’hubité ou de
centralité sortante, et une autre mesure relative à ses liens entrants, appelée mesure de
prestige, de popularité, d’autorité ou de centralité entrante [Wasserman and Faust 94]. Dans
un graphe non-orienté, chaque nœud possède un seul type de liens ou de relations avec les
autres nœuds. Chaque nœud possède alors une seule mesure d’importance (correspondant à
une définition précise) appelée mesure de centralité [Wasserman and Faust 94].
Dans la suite de ce chapitre, nous décrivons quelques mesures de centralité dans les
graphes orientés et non-orientés. Nous commençons par rappeler les principales mesures
proposées dans le domaine de l’analyse des réseaux sociaux. Celles-ci incluent les centralités
de degré, d’intermédiarité, de proximité ainsi que la centralité du vecteur propre (appelée
aussi centralité spectrale). Ensuite, nous présentons quelques uns des algorithmes les plus
populaires pour le calcul de l’importance d’un document dans un graphe d’hyperliens ou de
références bibliographiques. Il s’agit des algorithmes PageRank, HITS, Salsa et HubAvg.
Afin d’illustrer les différentes mesures de centralité, nous utiliserons les trois graphes jouets
de la figure 1.2
C
B G
A F
C A E F H D H
B G
D I
E
(a) (b)
B F
A C E G I
D H
(c)
Figure 1.2 – (a) Graphe jouet G1 ; (b) Graphe jouet G2 ; (c) Graphe jouet G3
19
Chapitre 1 Mesures de centralité issues de l’ARS
Le calcul de centralité est depuis plusieurs décennies une problématique importante dans
le domaine de l'analyse des réseaux sociaux [Wasserman and Faust 94]. La centralité est une
notion qui permet de rendre compte de la popularité ou visibilité d'un acteur au sein d'un
groupe. L'article "Centrality in social networks: Conceptual clarification [Freeman 79]" de
Freeman représente sans doute l'une des contributions les plus importantes dans le domaine de
l'analyse des réseaux sociaux. Dans son article, Freeman propose trois définitions formelles
du concept de centralité que nous présentons ci-dessous. Nous présentons également une
quatrième définition introduite par Bonacich qui est à la base d’un grand nombre de mesures
de centralité dans les graphes de documents.
La centralité de degré [Freeman 79] représente la forme la plus simple et la plus intuitive
de la notion de centralité. Elle est basée sur l’idée que l’importance d’un individu au sein d’un
groupe dépend du nombre total de personnes qu’il connaît ou avec lesquelles il interagit
directement. Selon cette mesure, déterminer l’importance d’un nœud dans un graphe revient
donc à calculer le nombre de ses sommets voisins, ou de manière équivalente, à calculer le
nombre de liens qui lui sont incidents. En théorie des graphes, ce nombre est appelé degré du
nœud, d’où l’appellation de centralité de degré.
Soit G = (V , E ) un graphe d’ordre & représenté par sa matrice d’adjacence A . Dans le
cas où le graphe G est non-orienté, la centralité de degré d’un nœud vi ∈ V est définie par :
&
1
& −1 ∑
C deg ( vi ) = aij (1.1)
j =1
En termes de matrices, les vecteurs de centralité de degré sortant et de degré entrant sont
donnés respectivement par cdeg = A × 1 et cdeg = AT × 1 .
out
& −1 in
& −1
Les figures 1.3 et 1.4 indiquent respectivement la centralité de degré pour les nœuds
graphes jouets G1 et G2. Les résultats fournis par cette analyse de la centralité de degré
montrent que les nœuds A et F, ayant quatre liens chacun, sont les plus importants dans le
20
Chapitre 1 Mesures de centralité issues de l’ARS
CDE=.43
CDE=.14 C CDS=.43
CDE=.29
B CD=.13 CD=.13 G CDS=.43 CDS=.29
A F CDE=.29
CD=.13 CD=.25 CD=.13 CDS=.14
C A E F H D H
CD=.50 CD=.50 CDE=.71
B CDS=.29 G
CDE=.14
D CD=.13 CD=.13 I CDE=.29 CDS=.29
E
CDS=.43 CDE=.29
CDS=.29
Figure 1.3 - Centralité de degré (CD) pour les Figure 1.4 - Centralités de degré entrant (CDE)
nœuds du graphe G1 et sortant (CDS) pour les nœuds du graphe G2
graphe G1. Pour le graphe G2, les nœuds A, B et C possèdent la plus forte centralité par
rapport aux liens sortants, tandis que le nœud D possède la plus forte centralité par rapport
aux liens entrants.
La centralité de degré est aussi appelée mesure de centralité locale [Scott 00] car elle ne
prend pas en compte la structure globale du graphe et n’est calculée qu’à partir du voisinage
immédiat d’un sommet. Bien qu’elle soit pertinente dans certaines situations, la centralité de
degré s’avère être peu informative dans d’autres cas, comme par exemple pour l’analyse des
graphes de pages web [Kleinberg 99a]. Les mesures que nous présentons dans la suite sont
toutes des mesures de centralité globales.
La centralité de proximité [Freeman 79] est une mesure de centralité globale basée sur
l’intuition qu’un nœud occupe une position stratégique (ou avantageuse) dans un graphe s’il
est globalement proche des autres nœuds de ce graphe. Par exemple dans un réseau social,
cette mesure correspond à l’idée qu’un acteur est important s’il est capable de contacter
facilement un grand nombre d’acteurs avec un minimum d’effort (l’effort ici est relatif à la
taille des chemins). En pratique, la centralité de proximité d’un nœud est obtenue en calculant
sa proximité moyenne vis-à-vis des autres nœuds du graphe.
Soit G = (V , E ) un graphe d’ordre & représenté par sa matrice d’adjacence A . Dans le
cas où le graphe G est non-orienté, la centralité de proximité d’un nœud vi ∈ V est définie
par :
Dans le cas où le graphe G est orienté, chaque nœud vi ∈ V possède alors deux mesures
de centralité de proximité : une par rapport aux liens sortants et une par rapport aux liens
entrants. Elles sont définies respectivement par :
21
Chapitre 1 Mesures de centralité issues de l’ARS
& −1 & −1
pro
Cout ( vi ) = ; Cinpro ( vi ) =
∑ j =1 dist ( vi , v j ) ∑ j =1 dist ( v j , vi )
n n
Pour le calcul des distances entre sommets, plusieurs métriques peuvent être utilisées.
Freeman propose par exemple d’utiliser la distance géodésique (i.e. taille du chemin le plus
court) entre les nœuds. D’autres mesures de distance telle que la distance euclidienne peuvent
également être utilisées pour le calcul de la centralité de proximité.
Les figures 1.5 et 1.6 indiquent respectivement la centralité de proximité (de Freeman)
pour les nœuds des graphes jouets G1 et G2. On remarque que le nœud E est le plus important
dans le graphe G1 alors qu’il n’a que deux liens. Cela est dû au fait que le nœud E est le
moins excentré dans le graphe. Pour le graphe G2, on obtient des résultats proches de ceux de
la centralité de degré i.e. les nœuds A et B possèdent la plus forte centralité par rapport aux
liens sortants, tandis que le nœud D possède la plus forte centralité par rapport aux liens
entrants.
CPE=.58
CPE=.47 C CPS=.58
B CP=.36 G CP=.36 CPE=.54
CPS=.58 CPS=.44
A F CPE=.47
CP=.36 CP=.57 CP=.36 CPS=.32
C A E F H D H
CP=.53 CP=.53 CPE=.78
B CPS=.50 G
CPE=.44 CPE=.35
D CP=.36 I CP=.36
CPS=.50
CPS=.58 E
CPE=.44
CPS=.50
Figure 1.5 - Centralité de proximité (CP) pour les
nœuds du graphe G1 Figure 1.6 - Centralités de proximité entrante
(CPE) et sortante (CPS) pour les nœuds du
graphe G2
La centralité d’intermédiarité [Freeman 79] est une autre mesure de centralité globale
proposée par Freeman. L’intuition de cette mesure est que, dans un graphe, un nœud est
d’autant plus important qu’il est nécessaire de le traverser pour aller d’un nœud quelconque à
un autre. Plus précisément, un sommet ayant une forte centralité d’intermédiarité est un
sommet par lequel passe un grand nombre de chemins géodésiques (i.e. chemins les plus
courts) dans le graphe. Dans un réseau social, un acteur ayant une forte centralité
d’intermédiarité est un sommet tel qu’un grand nombre d’interactions entre des sommets non
adjacents dépend de lui [Borgatti and Everett 06]. Dans un réseau de communication, la
centralité d’intermédiarité d’un nœud peut être considérée comme la probabilité qu’une
information transmise entre deux nœuds passe par ce nœud intermédiaire [Borgatti and
Everett 06].
22
Chapitre 1 Mesures de centralité issues de l’ARS
CI=.24
C
B CI=0 G CI=0 CI=.17 CI=.21
Figure 1.7 - Centralités d’intermédiarité (CI) Figure 1.8 - Centralité d’intermédiarité (CI)
pour les nœuds du graphe G1 pour les nœuds du graphe G2
où g jk ( vi ) est le nombre total de chemins géodésiques entre les nœuds v j et vk qui passent
par le nœud vi , et g jk est le nombre total de chemins géodésiques entre les nœuds v j et vk .
Les figures 1.7 et 1.8 indiquent respectivement la centralité d’intermédiarité pour les
nœuds des graphes jouets G1 et G2. Nous remarquons que les nœuds A et F sont les plus
importants dans le graphe G1 ; ces deux nœuds sont en effet les plus traversés par les chemins
géodésiques entre les nœuds du graphe. Pour le graphe G2, le nœud D est celui par lequel
passe le plus grand nombre de chemins géodésiques entre les nœuds du graphe ; il possède par
conséquent la plus forte centralité. Il est également intéressant de noter pour le graphe G2, que
les nœuds E et F possèdent des centralités d’intermédiarité différentes bien qu’ils aient le
même nombre de liens entrants et de liens sortants.
La centralité d’intermédiarité est basée sur l’hypothèse que les nœuds ne communiquent
ou interagissent entre eux qu’à travers les chemins les plus courts. Certains chercheurs ont
alors proposé de modifier cette hypothèse afin de prendre en compte le fait que les nœuds
peuvent interagir en utilisant des chemins autres que les chemins géodésiques. Par exemple,
Freeman [Freeman 91] a proposé la centralité du flux d’intermédiarité qui n’utilise pas que les
chemins géodésiques mais plutôt tous les chemins indépendants entre deux nœuds i.e. les
chemins dont les ensembles d’arcs sont disjoints.
23
Chapitre 1 Mesures de centralité issues de l’ARS
est d’autant plus important qu’il est connecté à des acteurs qui sont eux même importants. Il
s’agit en fait d’une extension de la centralité du degré dans laquelle on ne donne pas le même
poids aux nœuds voisins. Pour la mise en œuvre de ce principe, Bonacich propose de
considérer la centralité d’un nœud comme étant dépendante de la combinaison linéaire des
centralités de ses nœuds voisins.
Soit G = (V , E ) un graphe d’ordre & représenté par sa matrice d’adjacence A . Dans le
cas où le graphe G est non-orienté, la centralité spectrale C spe ( vi ) d’un nœud vi ∈ V est
donnée par l’équation :
µ C spe ( vi ) = a1i C spe ( v1 ) + a2i C spe ( v2 ) + ⋯ + ani C spe ( vn ) (1.4)
Dans le cas où le graphe G est orienté, chaque nœud vi ∈ V possède alors deux mesures
de centralité spectrale : une par rapport aux liens sortants et une par rapport aux liens entrants.
Elles sont données respectivement par les équations suivantes :
µ Cout
spe
( vi ) = ai1Coutspe ( v1 ) + ai 2Coutspe ( v2 ) + ⋯ + ainCoutspe ( vn )
λCinspe ( vi ) = a1i Cinspe ( v1 ) + a2i Cinspe ( v2 ) + ⋯ + ani Cinspe ( vn )
Le calcul de la centralité spectrale d’un nœud dans un graphe (orienté ou non) nécessite
donc de résoudre un système d’équations qui peut être représenté en termes de matrices de la
manière suivante :
µ c spe = MT c spe (1.5)
où µ est un réel strictement positif, c spe est le vecteur de centralité spectrale ; M correspond
soit à la matrice d’adjacence dans le cas du calcul de la centralité entrante, soit à la transposée
de la matrice d’adjacence dans le cas du calcul de la centralité sortante (dans le cas où le
graphe est non-orienté, nous avons M = MT ).
Pour résoudre l’équation 1.5, Bonacich montre que le vecteur de centralité spectrale c spe
correspond en fait au vecteur propre dominant (ou principal) de la matrice M (d’où les
appellations de centralité du vecteur propre ou de centralité spectrale). Pour le calcul du
vecteur c spe , il est possible d’utiliser par exemple la méthode des puissances itérées qui est
particulièrement efficace lorsque la matrice M est creuse.
La centralité spectrale pour les nœuds des graphes jouets G1 et G2 est indiquée
respectivement par les figures 1.9 et 1.10. Nous remarquons que les nœuds les plus importants
dans le graphe G1 sont les nœuds A et F. Pour le graphe G2, les nœuds A et B possèdent la
plus forte centralité par rapport aux liens sortants, tandis que le nœud D possède la plus forte
centralité par rapport aux liens entrants. Mais le plus intéressant avec ce graphe est que le
nœud A est plus important que le nœud G par rapport aux liens entrants alors qu’ils ont tous
24
Chapitre 1 Mesures de centralité issues de l’ARS
CSE=.51
CSE=.26 C CSS=.46
B CS=.22 G CS=.22 CSE=.28
CSS=.48 CSS=.20
A F CSE=.16
CS=.22 CS=.45 CS=.22 CSS=.09
C A E F H D H
CS=.5 CS=.5 CSE=.62
B CSS=.40 G
CSE=.10
D CS=.22 I CS=.22 CSE=.31 CSS=.20
CSS=.48 E
CSE=.25
CSS=.28
Figure 1.9 - Centralité spectrale (CS) pour les Figure 1.10 - Centralités spectrales entrante (CSE)
nœuds du graphe G1 et sortante (CSS) pour les nœuds du graphe G2
les deux le même nombre de liens entrants (égal à un). Cela s’explique par le fait que le nœud
A est pointé par le nœud D qui est lui même plus important que le nœud E qui pointe vers G.
Afin d’illustrer les limites des quatre mesures de centralité que nous avons présentées,
considérons le graphe jouet G3 de la figure 1.11 où les différentes mesures de centralité pour
chacun des nœuds de ce graphe sont indiquées.
Notre première remarque concerne la centralité de proximité qui n’est en fait utilisable
que si le graphe est fortement connexe. Le graphe G3 n’étant pas fortement connexe, il n’est
par conséquent pas possible de calculer la centralité de proximité puisque les distances
géodésiques entre certains nœuds sont indéfinies. Par exemple, la distance entre les nœuds E
et I est indéfinie puisqu’il n’existe aucun chemin entre les deux nœuds.
Concernant la centralité d’intermédiarité, les résultats indiquent que tous les nœuds ont
une centralité nulle à l’exception du nœud C. Cela est dû au fait que le nœud C est le seul à
avoir à la fois des liens entrants et des liens sortants. D’après la définition de la centralité
d’intermédiarité, il est évident que tout nœud qui ne possède pas au moins un lien entrant et
un lien sortant aura une importance nulle.
Quant à la centralité spectrale, la figure 1.11 indique que tous les nœuds ont une
importance nulle. Ce résultat inattendu est généralement obtenu lorsque le graphe est orienté
et que certains nœuds ne possèdent qu’un seul type de liens (i.e. soit entrants soit sortants).
Ces nœuds ne peuvent alors pas contribuer au calcul de la centralité. Par exemple, les nœuds
A, F, G et H n’ont pas de liens entrants, ce qui fait qu’ils ont une centralité entrante nulle. Ces
nœuds ne vont alors pas contribuer au calcul de la centralité spectrale des nœuds qu’ils
pointent i.e. B, C, D, E et I. Ces derniers nœuds se retrouvent alors aussi avec une centralité
nulle. Le même raisonnement peut être fait pour le calcul de la centralité sortante. Notons au
passage que les valeurs et vecteurs propres d’une matrice asymétrique peuvent être complexes
contrairement aux matrices symétriques dont les valeurs et vecteurs propres sont toujours
réels [Golub and Van Loan 96].
25
Chapitre 1 Mesures de centralité issues de la RI
Finalement, parmi les quatre mesures de centralité que nous avons présentées jusque-là,
il n’y aurait que la centralité du degré qui soit adaptée aux graphes de documents car ces
derniers sont orientés et généralement non connexes (au meilleur des cas, ils peuvent être
faiblement connexes). De plus, dans un graphe de documents, les sommets ne possèdent pas
tous des liens entrants et des liens sortants. A titre d’exemple, un article scientifique ou une
page web nouvellement créés ne vont pas avoir de liens entrants au moment de leur
publication. Cependant, à la fin des années 90, un grand nombre de chercheurs se sont
penchés sur le problème du calcul de centralité dans les graphes de documents afin de
proposer d’autres mesures. Comme nous allons le voir dans la section suivante, la plupart de
ces mesures (pour ne pas dire toutes) sont des variantes de la centralité spectrale.
B F
A C E G I
D H
%œud A B C D E F G H I
Centralité de degré sortant 0.38 0 0.13 0 0 0.26 0.26 0.26 0
Centralité du degré entrant 0 0.13 0.13 0.13 0.5 0 0 0 0.38
Centralité d’intermédiarité 0 0 0.02 0 0 0 0 0 0
Centralité spectrale sortante 0 0 0 0 0 0 0 0 0
Centralité spectrale entrante 0 0 0 0 0 0 0 0 0
A la fin des années 90, plusieurs chercheurs ont envisagé d’utiliser les liens entre
documents (en plus des contenus textuels) afin d’améliorer les performances des moteurs de
recherche sur le web. La pertinence d’un document par rapport à une requête est alors
calculée en combinant la similarité du document par rapport à la requête avec la centralité du
document [Baeza-Yates and Ribeiro-Neto 99][Chakrabarti 02][Manning et al. 08]. Nous
présentons ci-dessous quelques uns des algorithmes les plus connus pour le calcul de
centralité dans les graphes de documents. Ces algorithmes sont tous basés sur l’idée que
l’importance d’un document est relative à l’importance des documents auxquels il est
connecté.
26
Chapitre 1 Mesures de centralité issues de la RI
1.3.1 PageRank
Proposé à la fin des années 90 par les deux informaticiens Brin et Page, PageRank [Brin
and Page 98] est l’un des algorithmes d’analyse de liens qui a le plus marqué le domaine de la
recherche d’information sur le web. Il a d’ailleurs été classé parmi le top 10 des algorithmes
de data mining lors de la conférence ICDM 2006 [Wu et al. 08]. C’est notamment grâce à cet
algorithme que le moteur de recherche de Google a connu le succès qu’il a aujourd’hui.
Dans sa version simplifiée, l’algorithme PageRank considère que l’importance (appelée
aussi popularité ou encore PageRank) d’une page est fonction des popularités des pages qui la
pointent (ou la citent). Plus précisément, le PageRank simplifié d’une page pi est donné
par [Zhang et al. 05] :
PRS ( p j )
PRS ( pi ) = ∑
p j ∈in ( pi ) d out ( p j )
(1.6)
où in ( pi ) représente l’ensemble des pages qui pointent vers la page pi et d out ( p j ) représente
le degré sortant de la page p j .
L’algorithme 1.1 indique les différentes étapes de calcul du PageRank simplifié. Les
étapes 1 à 2 de l’algorithme permettent de transformer la matrice d’adjacence A en une
matrice stochastique A l . Cette transformation est réalisée en normalisant les lignes de la
matrice d’adjacence A (étape 5) tel que :
aij
( al )ij = (1.7)
∑ k =1 aik
&
Le but de cette normalisation est d’atténuer l’effet des pages ayant un grand nombre de
liens sortants. En d’autres termes, cela revient à considérer que chaque page possède un seul
"vote" qui sera distribué de manière égale aux pages pointées.
Les étapes 3 à 7 de l’algorithme correspondent à l’application de la méthode des
puissances pour le calcul du vecteur propre dominant de la matrice A l T . Dans la dernière
étape, le vecteur du PageRank p est normalisé afin que la somme des PageRank de toutes les
pages soit égale à 1.
La figure 1.12 montre les résultats obtenus en appliquant l’algorithme du PageRank
simplifié avec le graphe jouet G2. La figure indique que le nœud D est le plus populaire (ou le
plus important) car il est pointé par plusieurs nœuds qui sont eux même importants. Nous
remarquons aussi que le nœud A possède un PageRank plus important que les nœuds B, F et
H bien que ces derniers aient plus de liens entrants que A. Cela s’explique par le fait que A est
pointé par un nœud (à savoir D) qui est plus important que les nœuds qui pointent vers B (C et
E), E (A et B) ou H (F et G).
27
Chapitre 1 Mesures de centralité issues de la RI
PS =.19
C
PS=.12 PS =.16
A F PS =.10
D H
PS =.23
B G
PS =.10 PS =.04
E
PS =.07
28
Chapitre 1 Mesures de centralité issues de la RI
π = PT π (1.8)
Une entrée π i du vecteur π indique la probabilité que la chaîne soit à l’état i à n’importe
quel instant. L’existence d’une distribution stationnaire unique n’est cependant garantie que si
la chaîne de Markov est irréductible et apériodique. C’est pourquoi la version simplifiée du
PageRank nécessite que la matrice d’adjacence ait ces deux propriétés. Dans le cas où ces
deux conditions ne sont pas vérifiées, le PageRank simplifié donne (en général) des résultats
contre-intuitifs comme le montre la figure 1.13. Les résultats indiqués par cette figure
s’expliquent en partie par le fait que plusieurs nœuds du graphe ne possèdent pas de liens
sortants. Ces pages, appelées aussi pages puits, posent problème au surfeur aléatoire car une
fois qu’il les visite, il ne pourra plus les quitter. Une autre raison expliquant ce résultat est que
si par exemple le surfeur aléatoire commence sa marche au nœud A, il ne pourra jamais
atteindre certains nœuds du graphe tels que F et I.
Cependant, les deux conditions d’irréductibilité et d’apériodicité n’étant que très
rarement satisfaites en pratique, Brin et Page ont alors proposé une variante du PageRank
simplifié (que nous appelons PageRank pratique) qui consiste à modifier le graphe initial afin
de le rendre irréductible et apériodique. Le PageRank pratique est en fait basé sur un nouveau
modèle de marche aléatoire dans lequel le surfeur aléatoire choisit à chaque étape :
- soit de suivre un des liens sortants de la page courante avec une probabilité égale à α .
- soit de visiter une page quelconque du graphe avec une probabilité égale à (1 − α ) .
où α , appelé paramètre d’amortissement ou facteur de zap, est un réel compris entre 0 et 1.
Lorsque α = 1 , nous remarquons que ce modèle est équivalent à celui du PageRank simplifié.
L’algorithme 1.2 décrit le processus itératif permettant de calculer le vecteur du
PageRank pratique. L’étape 3 de l’algorithme modifie la matrice d’adjacence en rajoutant des
liens aux nœuds ayant un degré sortant nul. A l’étape 5, l’algorithme construit la matrice
irréductible et apériodique G , appelée parfois matrice de Google [Langville and Meyer 06],
en rajoutant des liens (pondérés) entre tous les nœuds du graphe. La suite de l’algorithme
consiste à appliquer l’algorithme du PageRank simplifié avec la matrice G en entrée.
B PS=0 F PS=0
A C E G I
PS=1
D PS=0 H PS=0
29
Chapitre 1 Mesures de centralité issues de la RI
4. fin
5. G ← α Dl −1A + (1 − α ) 1 1& × &
&
6. p (0) ← 1 1& ×1 , t ← 1
&
7. répéter
8. p (t ) ← G T p (t −1)
9. t ← t +1
10. jusqu’à convergence
p (t )
11. p ( t ) ←
p (t )
// x 1 = ∑x
i =1
i est la norme L1 du vecteur x
1
fin
B PP=.10 F PP=.07
A C E G I
PP=.25
D PP=.10 H PP=.07
30
Chapitre 1 Mesures de centralité issues de la RI
le plus important car il est pointé par plusieurs nœuds ayant un degré d’importance non nul. Il
est par ailleurs intéressant de noter ici qu’avec le PageRank pratique, tous les nœuds auront un
PageRank différent de zéro y compris ceux qui ne possèdent pas de liens entrants.
Bien qu’initialement proposé pour l’analyse de liens hypertextes, l’algorithme PageRank
a été utilisé plus récemment pour l’analyse d’autres types de graphes notamment pour
l’analyse des références bibliographiques [Fiala et al. 08][Ma et al. 08].
Une critique que l’on peut faire à l’algorithme PageRank est la modification considérable
apportée au graphe initial, notamment en rajoutant de manière équiprobable des liens entre
tous les documents. D’autre part, le paramètre d’amortissement α peut parfois avoir une
grande influence sur les résultats obtenus comme le montrent plusieurs travaux ([Chen et al.
07] et [Maslov and Redner 08]), ce qui pose le problème du choix de la valeur de ce
paramètre.
Enfin, nous noterons que l’algorithme PageRank n’est en réalité qu’une variante de la
centralité spectrale de Bonacich, variante qui commence d’abord par modifier la matrice
d’adjacence initiale avant de calculer son vecteur propre dominant.
Dans le cadre du projet Clever [Kumar et al. 06] développé par IBM en 1998, Kleinberg
[Kleinberg 98][Kleinberg 99a] a proposé l’algorithme HITS dont l’idée est d’exploiter la
structure du web afin d’améliorer la qualité de la recherche d’information. Cependant, à la
différence de PageRank qui assigne à chaque page un seul degré d’importance, l’algorithme
HITS caractérise chaque page par deux degrés d’importance. Ces deux degrés, que Kleinberg
appelle degrés d’autorité et d’hubité, sont respectivement des mesures de centralité par
rapport aux liens entrants et aux liens sortants.
L’algorithme HITS considère que le degré d’autorité d’une page est égal à la somme des
degrés d’hubité des pages qui la pointent (ou la citent). En d’autres termes, une page est une
bonne autorité si elle est pointée par de bons hubs. Plus précisément, le degré d’autorité d’une
page pi est défini par :
A ( pi ) = ∑
p j ∈in ( pi )
H ( pj ) (1.9)
où in(pi) représente l’ensemble des pages qui pointent vers la page pi et H(pj) représente le
degré d’hubité de la page pj.
De manière similaire, HITS considère que le degré d’hubité d’une page est égal à la
somme des degrés d’autorité des pages qu’elle pointe. Cela sous-entend qu’une page est un
bon hub si elle pointe vers de bonnes autorités. Ainsi, le degré d’hubité d’une page pi est
défini par :
H ( pi ) = ∑
p j ∈out ( pi )
A( p j ) (1.10)
où out(pi) représente l’ensemble des pages pointées par la page pi et A(pj) représente le degré
d’autorité de la page pj.
31
Chapitre 1 Mesures de centralité issues de la RI
L’algorithme 1.3 présente les différentes étapes de calcul des vecteurs d’autorité et
d’hubité par HITS. L’algorithme part d’un vecteur d’autorité initial, puis effectue une
itération entre une mise à jour du vecteur h (vecteur des hubs) en utilisant le vecteur o
(vecteur des autorités) et une mise à jour du vecteur o en utilisant le vecteur h. Dans son
article de référence, Kleinberg [Kleinberg 99] parle de principe de renforcement mutuel entre
les hubs et les autorités pour décrire ce processus itératif de mise à jour des vecteurs o et h.
Kleinberg montre notamment que le vecteur d’autorité o calculé par son algorithme
correspond au vecteur propre principal de la matrice O HITS = AT A (que nous appelons
matrice des autorités de HITS), où A est la matrice d’adjacence. Il suffit en fait de remplacer
le vecteur h dans la ligne 3 par la formule de la ligne 4 pour s’apercevoir que HITS n’est rien
d’autre qu’une application de la méthode des puissances pour le calcul du vecteur propre
principal de la matrice O HITS . Le même raisonnement peut être utilisé pour montrer que le
vecteur des hubs h calculé par HITS correspond au vecteur propre principal de la matrice
H HITS = AAT (que nous appelons matrice des hubs de HITS).
La matrice O HITS (resp. H HITS ) est très proche de la matrice de co-citation [Small 73]
(resp. de couplage bibliographique [Kessler 63]) utilisée en bibliométrie. Ding et al. [Ding et
al. 02] montrent en effet que :
O HITS = M coc + Din , H HITS = M bib + Dout
où :
− M coc est la matrice de co-citation. Une entrée ( i, j ) de cette matrice indique le nombre
de fois que les documents i et j sont co-cités par d’autres documents.
− M bib est la matrice de couplage bibliographique. Une entrée ( i, j ) de cette matrice
indique le nombre de fois que les documents i et j citent le même document.
− Din est une matrice diagonale dans laquelle une entrée ( i, i ) indique le nombre de
liens entrants du document i.
32
Chapitre 1 Mesures de centralité issues de la RI
− Dout est une matrice diagonale dans laquelle une entrée ( i, i ) indique le nombre de
liens sortants du document i.
La figure 1.15 indique les degrés d’autorité et d’hubité calculés par HITS pour les nœuds
du graphe jouet G2. Concernant les degrés d’autorité, nous remarquons que le nœud D est le
plus important car il est pointé par plusieurs nœuds qui ont un fort degré d’hubité. Nous
remarquons aussi que le nœud E est plus important que le nœud H bien qu’ils aient le même
nombre de liens entrants. Cela est dû au fait que les nœuds qui pointent vers E, à savoir A et
B, ont un degré d’hubité supérieur à celui des nœuds F et G qui pointent vers H. Par rapport
aux degrés d’hubité, la figure 1.15 montre que A et B sont les meilleurs hubs : ils pointent en
effet vers plusieurs nœuds ayant un fort degré d’autorité. Notons enfin que les nœuds A et B
ont le même degré d’hubité car ils pointent vers les mêmes nœuds à savoir C, D et E.
Nous reportons sur la figure 1.16 les résultats obtenus en analysant le graphe jouet G3 en
utilisant l’algorithme HITS. Nous remarquons que certains résultats sont étonnants car le
nœud A, par exemple, a un degré d’hubité nul alors qu’il possède trois liens sortants. De
même, les nœuds B et D ont tous les deux un lien entrant et malgré cela l’algorithme HITS
leur assigne un degré d’autorité nul. Une telle situation où certains nœuds obtiennent un degré
d’autorité ou d’hubité faible (voire nul comme c’est le cas ici) alors qu’ils devraient avoir une
importance non négligeable a été mise en évidence par Lempel et Moran [Lempel and Moran
00]. Ces derniers appellent ce "défaut" de HITS : problème de l’effet TKC ("Tightly Knit
Community" ou communauté fortement connectée).
DO=.44
DO=.06 C DH=.36
DO=.14
DH=.55 DH=.34
A F DO=.24
DH=.05
D H
DO=.75
B DH=.18 G
DO=.02
DO=.15 DH=.34
DH=.55 E
DO=.38
DH=.06
Figure 1.15 – Degrés d’autorité (DO) et d’hubité (DH)
calculés par HITS pour les nœuds du graphe G2
DO=0 DO=0
B DH=0 F DH=.55
DO=0
D H DO=0
DH=0 DH=.55
Figure 1.16- Degrés d’autorité (DO) et d’hubité (DH) calculés par
HITS pour les nœuds du graphe G3
33
Chapitre 1 Mesures de centralité issues de la RI
Un autre problème lié à l’algorithme HITS concerne sa convergence. Cet aspect est
étudié en détail dans [Farahat et al. 05] où les auteurs montrent à travers plusieurs exemples
que la convergence de l’algorithme peut poser problème avec certains graphes. Farahat et al.
prouvent de plus, en se basant sur le théorème de Perron-Frobenius, que l’algorithme HITS
converge vers un vecteur d’autorité o (resp. d’hubité h) unique si et seulement si la matrice
O HITS (resp. H HITS ) est irréductible.
Par ailleurs, mentionnons qu’il est possible d’interpréter le calcul du vecteur d’autorité o
(resp. d’hubité h) effectué par HITS de la façon suivante : dans un premier temps,
l’algorithme de Kleinberg construit une matrice symétrique, en l’occurrence O HITS (resp.
H HITS ), qui préserve l’information sur les liens entrants (resp. sortants) contenue dans la
matrice d’adjacence. Dans un second temps, l’algorithme calcule la centralité spectrale de
Bonacich pour les nœuds du graphe représenté par la matrice O HITS (resp. H HITS ).
O SALSA = A cT A l , H SALSA = Al A cT
où A c est la matrice obtenue en normalisant (avec la norme L1) les colonnes non nulles de la
matrice A ; Al est la matrice obtenue en normalisant (avec la norme L1) les lignes non nulles
de la matrice A .
Sachant que la distribution stationnaire o (resp. h) de la chaîne de Markov Mo (resp. Mh )
correspond au vecteur propre principal de la matrice O SALSA (resp. H SALSA ), il est par
conséquent possible de calculer le vecteur o (resp. h) en utilisant la méthode des puissances
(sous réserve que les matrices O SALSA et H SALSA soient irréductibles).
34
Chapitre 1 Mesures de centralité issues de la RI
Lempel et Moran montrent que si la chaîne de Markov Mo est irréductible, elle possède
alors une distribution stationnaire unique o = ( o1 ,… , o& ) qui vérifie pour tout i ∈ V :
d in ( i )
oi = (1.11)
M
où d in ( i ) représente le degré entrant du nœud i.
Ils montrent par ailleurs que si la chaîne de Markov Mh est irréductible, elle possède alors
une distribution stationnaire unique h = ( h1 ,… , h& ) qui vérifie pour tout i ∈ V :
d out ( i )
hi = (1.12)
M
Dans le cas où la chaîne de Markov Mo (resp. Mh) n’est pas irréductible, c’est-à-dire que
son graphe contient plusieurs composantes connexes, Lempel et Moran proposent une
méthode simple permettant de calculer le vecteur d’autorité o (resp. d’hubité h). La méthode
consiste à appliquer l’algorithme SALSA sur chacune des composantes connexes puis à
multiplier le degré d’importance de chaque nœud par un facteur proportionnel à la taille de la
composante contenant ce nœud. Plus précisément, si le graphe de la chaîne de Markov Mo
contient l composantes connexes C1 , C2 … , Cl , le degré d’autorité oi d’un nœud i ∈ Ck est
donné par :
Ck d in ( i )
oi = (1.13)
& d in ( Ck )
Pk d out ( i )
hi = (1.14)
& d out ( Pk )
35
Chapitre 1 Mesures de centralité issues de la RI
A ( pi ) = 1
∑ H ( pj ) (1.15)
in ( pi ) p j ∈in ( pi )
où in(pi) représente l’ensemble des pages qui pointent vers la page pi et H(pj) représente le
degré d’hubité de la page pj.
- le degré d’hubité d’une page est égal à la moyenne des degrés d’autorité des pages
qu’elle pointe. En d’autres termes, une page est un bon hub si elle pointe vers de bonnes
autorités uniquement. Cela revient à pénaliser les hubs qui pointent vers de mauvaises
autorités. Plus précisément, le degré d’hubité d’une page pi est défini par :
H ( pi ) = 1
∑ A( pj ) (1.16)
out ( pi ) p j ∈out ( pi )
où out(pi) représente l’ensemble des pages pointées par la page pi et A(pj) représente le degré
d’autorité de la page pj.
En utilisant ces deux définitions des degrés d’autorité et d’hubité, nous obtenons alors
l’algorithme 1.4 qui permet de calculer les vecteurs d’autorité et d’hubité. En remplaçant le
vecteur h dans la ligne 9 par la formule de ligne 10, nous remarquons que le vecteur autorité o
calculé par cet algorithme correspond au vecteur propre principal de la matrice
O SALSA = A cT A l . De même, nous remarquons que le vecteur h calculé par cet algorithme
correspond au vecteur propre principal de la matrice H SALSA = Al A cT . Cet algorithme
nécessite toutefois que les matrices O SALSA et H SALSA soient irréductibles. Dans le cas où elles
ne le sont pas, il faudra alors appliquer l’algorithme sur chaque composante connexe puis
combiner les résultats des différentes composantes (méthode de Lempel et Moran).
La figure 1.17 indique les degrés d’autorité et d’hubité obtenus en appliquant
l’algorithme SALSA avec le graphe jouet G3. Pour ce graphe, les matrice de transition O SALSA
et H SALSA sont données par :
B C D E I
B 0.33 0.33 0.33 0 0
C
0.33 0.33 0.33 0 0
O SALSA = D 0.33 0.33 0.33 0 0
E 0 0 0 0.62 0.37
I 0 0 0 0.50 0.50
A C F G H
A 1 0 0 0 0
C
0 0.25 0.25 0.25 0.25
H SALSA = F 0 0.13 0.29 0.29 0.29
G 0 0.13 0.29 0.29 0.29
H 0 0.13 0.29 0.29 0.29
36
Chapitre 1 Mesures de centralité issues de la RI
DO=.20 DO=0
B DH=0 F DH=.23
DO=.20
D H DO=0
DH=0 DH=.23
Nous remarquons que la matrice O SALSA n’est pas irréductible. Son graphe contient en
effet deux composants connexes à savoir C1 = {B, C, D} et C2 = {E, I} . Contrairement à HITS
qui s’était focalisé sur la composante C1, SALSA attribue des degrés d’autorité à tous les
nœuds ayant au moins un lien entrant. Il assigne également un degré d’hubité à tous les nœuds
qui possèdent au moins un lien sortant. La figure 1.17 montre que le nœud E est la meilleure
37
Chapitre 1 Mesures de centralité issues de la RI
autorité et que les nœuds F, G et H sont les meilleurs hubs. Nous constatons aussi que le nœud
B, qui n’a qu’un seul lien entrant, possède un degré d’autorité plus fort que le nœud I qui a
trois liens entrants. Ce résultat est dû à la méthode utilisée par SALSA pour combiner les
degrés d’importance des différentes composantes lorsque la chaine de Markov n’est pas
irréductible. Cette méthode bien que simple n’est basée que sur la taille de la composante et
ne prend pas en compte la densité des liens au sein des composantes ; elle tend par conséquent
à favoriser les nœuds qui appartiennent à des composantes de grande taille.
Hormis le fait que l’algorithme SALSA souffre lui aussi (mais à un degré moindre que
HITS) du problème de la TKC, comme le montrent Borodin et al. [Borodin et al. 05] dans leur
étude expérimentale, la principale critique que nous pouvons faire à SALSA est le fait qu’il
soit équivalent à la centralité du degré (cf. formules 1.11 et 1.12). Or, celle-ci est une mesure
locale qui détermine l’importance d’un nœud en utilisant son voisinage immédiat uniquement.
L’algorithme SALSA n’utilise donc pas la structure globale du graphe comme c’est le cas de
HITS et PageRank.
1.3.4 HubAvg
HubAvg [Borodin et al. 01] est un autre algorithme d’analyse de liens proposé pour
résoudre le problème TKC qui caractérise l’algorithme HITS. Comme ce dernier, HubAvg est
basé sur le principe de renforcement mutuel entre les hubs et les autorités. Cependant, les
auteurs de HubAvg utilisent une définition différente que celle de Kleinberg pour la notion de
bon hub. En effet, alors que HITS considère qu’un bon hub est un nœud qui pointe vers de
bonnes autorités, dans HubAvg, un bon hub est un nœud qui pointe uniquement vers de
bonnes autorités. En d’autres termes, cette définition signifie que les hubs qui pointent vers
des nœuds ayant un faible degré d’autorité doivent être pénalisés. Plus précisément, le degré
d’hubité d’une page pi est calculé par HubAvg de la façon suivante :
1
H ( pi ) =
out ( pi )
∑
p j ∈out ( pi )
A( p j ) (1.17)
où out(pi) représente l’ensemble des pages pointées par la page pi et A(pj) représente le degré
d’autorité de la page pj. Le degré d’hubité d’une page correspond donc à la moyenne des
degrés d’autorité des pages qu’elle pointe. Le degré d’autorité d’une page, quant à lui, est
calculé de la même manière que dans l’algorithme HITS i.e. il est égal à la somme des degrés
d’hubité des pages qui pointent vers elle.
Les différentes étapes de l’algorithme HubAvg sont indiquées par l’algorithme 1.5. Nous
remarquons que l’algorithme est similaire à la fois à HITS pour l’étape de mise à jour du
vecteur d’autorité (ligne 8) et à SALSA pour l’étape de mise à jour du vecteur d’hubité (ligne
9). Notons aussi que le vecteur d’autorité o (resp. d’hubté h ) calculé par HubAvg correspond
au vecteur propre principal de la matrice AT A l (resp. Al AT ), où Al est la matrice
d’adjacence dont les lignes ont été normalisées pour que leur somme soit égale à un.
Afin de voir l’effet de la normalisation introduite dans l’algorithme HubAvg, considérons
à nouveau les graphes jouet G2 et G3 des figures 1.18 et 1.19 où sont indiqués les résultats
obtenus en appliquant l’algorithme HubAvg avec ces deux graphes. Pour le graphe G2, nous
38
Chapitre 1 Mesures de centralité issues de la RI
remarquons que les résultats de HubAvg sont différents de ceux obtenus avec l’algorithme
HITS. En effet, alors que ce dernier (cf. figure 1.15) trouve que les nœuds A et B sont plus
importants en termes de degré d’hubité que les nœuds F et G, l’algorithme HubAvg trouve le
contraire. Cette différence s’explique par le fait que les nœuds F et G qui possèdent deux liens
sortants sont moins pénalisés par HubAvg que les nœuds A et B qui possèdent trois liens
sortants. D’autre part, comme les nœuds F et G sont de meilleurs hubs que les nœuds A et B,
il en résulte que le nœud H, pointé par F et G, est plus important en termes de degré d’autorité
que le nœud E pointé par A et B.
Concernant le graphe G3, nous remarquons que HubAvg attribue au nœud C un degré
d’hubité plus fort qu’aux nœuds F, G et H alors que HITS (cf. figure 1.16) assigne moins
d’importance au nœud C en termes de degré d’hubité. N’ayant qu’un seul lien sortant, le
nœud C est en fait moins pénalisé par HubAvg que les nœuds F, G et H qui ont trois liens
sortants. De même qu’avec l’algorithme HITS, nous remarquons que l’algorithme HubAvg
semble "ignorer" les nœuds A, B et D puisqu’il leur assigne des degrés d’autorité et d’hubité
nuls. En effet, tel que défini, l’algorithme HubAvg ne gère pas le cas où le graphe associé à la
matrice AT A l (ou AA l T ) contient plusieurs composantes connexes ce qui le rend vulnérable
au problème de la TKC.
39
Chapitre 1 Bilan
DO=.37
DO=.07 C DH=.31
DO=.16
DH=.42 DH=.49
A F DO=.35
DH=.14
D H
DO=.77
B DH=.19 G
DO=.03
DO=.14 DH=.49
DH=.42 E
DO=.30
DH=.07
DO=0 DO=0
B DH=0 F DH=.48
DO=0
D H DO=0
DH=0 DH=.48
L’algorithme HubAvg possède les mêmes inconvénients que l’algorithme HITS. Ainsi, si
la matrice AT A l (ou AA l T ) n’est pas irréductible, l’existence et l’unicité de son vecteur
propre principal pose problème comme pour l’algorithme HITS. De plus, l’algorithme
HubAvg souffre lui aussi du problème de la TKC mais de manière moins importante grâce à
la normalisation utilisée lors du calcul des degrés d’hubité [Borodin et al. 05].
1.4 Bilan
Dans ce chapitre, nous avons présenté diverses définitions de la notion de centralité dans
les graphes. Nous avons commencé par la plus simple de ces définitions, à savoir la centralité
de degré, qui correspond à la taille du voisinage immédiat d’un nœud. La centralité de degré
est bien connue en bibliométrie où le degré entrant (appelé aussi nombre de citations) est
utilisé pour quantifier l’importance des publications scientifiques [Garfield 72]. Cependant,
un fort degré entrant n’est généralement pas suffisant pour repérer tous les documents
importants [Maslov and Redner 08]. En effet, nous montrerons dans le chapitre suivant que si
le graphe de documents contient plusieurs communautés (où chacune correspond à une
thématique par exemple), alors la centralité de degré favorise les documents appartenant aux
40
Chapitre 1 Bilan
communautés qui sont de grande taille et fortement connectées. La centralité de degré est en
fait une mesure locale qui ne tient pas compte de la structure globale du graphe.
Trois autres mesures de centralité prenant en compte la structure globale du graphe ont
ensuite été présentées. Il s’agit des centralités de proximité, d’intermédiarité et de vecteur
propre. Nous avons montré que ces trois mesures ne sont pas adaptées à l’analyse de graphes
de documents car ces derniers sont orientés et généralement non connexes.
Nous avons également décrit en détail les principaux algorithmes de calcul de centralité
dans les graphes de documents. L’analyse des avantages et inconvénients de ces algorithmes a
mis en évidence un problème important dont souffrent ces techniques. Il s’agit en
l’occurrence du problème de la TKC (Tightly Knit Community) qui entraine une attribution
erronée des degrés d’importance aux documents.
Par ailleurs, nous avons établi un lien entre les mesures issues de l’ARS et celles issues
de la RI. Il provient du fait que les mesures issues de la RI sont en réalité toutes basées sur le
principe de la centralité spectrale (ou de vecteur propre) introduite au début des année 1970
par Bonacich [Bonacich 72].
Notre objectif, dans le chapitre suivant, est de développer une mesure de centralité dans
les graphes de documents qui n’utilise que les liens entre documents, qui exploite la structure
globale du graphe et qui soit robuste au problème de la TKC. Nous allons ainsi proposer trois
nouveaux algorithmes de calcul de centralité qui permettent de calculer les degrés d’autorité
et d’hubité des documents tout en évitant l’effet TKC dont souffrent les précédents
algorithmes.
41
Chapitre 2 &ouveaux algorithmes pour le calcul de centralité
Dans le chapitre précédent, nous avons décrit brièvement l’effet TKC qui caractérise
l’algorithme HITS. Dans le présent chapitre, nous allons nous intéresser plus en détail à ce
problème en identifiant notamment ses différentes causes. Nous pensons en effet que le
"symptôme" TKC est un paramètre important qui doit être pris en compte par les algorithmes
de calcul de centralité.
Nous proposons dans ce chapitre trois nouveaux algorithmes de calcul de centralité dans
les graphes de documents à savoir MHITS, NHITS et DocRank. Ces algorithmes calculent
pour chaque document un degré d’autorité ainsi qu’un degré d’hubité. De plus, chaque
algorithme utilise une stratégie différente pour pallier au problème de la TKC.
Afin d’évaluer les trois algorithmes proposés, nous avons mené des expérimentations
dans lesquelles nous avons comparé onze algorithmes de calcul de centralité (y compris les
nôtres) en utilisant huit graphes de documents. Les résultats obtenus montrent l’intérêt des
algorithmes proposés et notamment de l’algorithme DocRank qui donne des résultats
largement meilleurs à ceux des autres algorithmes. De plus, un avantage non négligeable de
DocRank est qu’il possède une complexité très faible. En effet, contrairement à la plupart des
autres algorithmes qui sont basés sur le calcul de vecteurs propres (qui peut être coûteux en
temps de calcul lorsque le graphe est de grande taille), DocRank a la même complexité que la
centralité de degré.
42
Chapitre 2 L’effet TKC
L’effet TKC est sans doute l’une des principales raisons qui ont fait que l’algorithme
HITS n’a pas connu un aussi grand succès que l’algorithme PageRank. Comme ce dernier,
l’algorithme HITS a été proposé initialement en recherche d’information pour le classement
("ranking") de documents sur le web. Dans sa version "complète", HITS [Kleinberg 99a]
construit dans un premier temps un graphe de documents à partir d’une requête utilisateur
(cette étape est décrite dans la section 2.5.1), puis dans un deuxième temps, il effectue le
calcul des degrés d’autorité et d’hubité. Plusieurs chercheurs (par exemple [Borodin et al.
05][Lempel and Moran 00][Cohn and Chang 00]) ayant étudié l’algorithme HITS ont
remarqué que les documents classés comme importants ne traitent en général qu’une seule
thématique de la requête utilisateur. Pire encore, il a même été observé que dans certains cas,
HITS classe comme importants des documents qui ne sont pas du tout pertinents par rapport à
la requête initiale (problème connu sous le nom de topic drift [Bharat and Henzinger 98]).
La figure 2.1 montre le classement des 10 documents les plus importants obtenu en
appliquant l’algorithme HITS avec un graphe d’environ 5000 publications scientifiques dans
le domaine de la physique des plasmas. Pour ce même graphe, la figure 2.2 indique les 10
documents les plus populaires retournés par l’algorithme PageRank. Sans avoir à consulter les
contenus des documents, nous pouvons remarquer que les articles classés comme étant les
plus importants (en termes d’autorité) par HITS relèvent tous de la thématique « dusty
plasma » ; presque tous les documents retournés contiennent en effet ce terme dans leur titre.
Les 10 articles les plus importants selon PageRank semblent être, quant à eux, beaucoup plus
diversifiés en termes de thématiques traitées.
Figure 2.1 - Les 10 documents les plus importants d’après l’algorithme HITS
43
Chapitre 2 L’effet TKC
Figure 2.2 - Les 10 documents les plus importants d’après l’algorithme PageRank
44
Chapitre 2 L’effet TKC
1 2 3 7 8 9
4 5 6 10 11 12
(a)
3 3
4 11
3 3 3 3 2 2 3 3
5 6 10 12
3 2
(b)
Figure 2.3 - (a) Graphe jouet G1
(b) Graphe G1o (graphe d’autorité construit à partir du graphe G1)
Tableau 2.1 - Degrés d'autorité et d'hubité calculés par HITS pour les nœuds du graphe G1
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.33 0.33 0.33 0 0 0 0 0 0
Degré d’hubité 0.33 0.33 0.33 0 0 0 0 0 0 0 0 0
Cependant, l'effet TKC ne se produit pas uniquement lorsque le graphe d’autorité (ou
d’hubité) n'est pas connexe. Pour illustrer cela, considérons les graphes jouets G2 de la figure
2.4a et G3 de la figure 2.5a dont les graphes d’autorité respectifs G2o et G3o sont connexes.
Les graphes G2 et G3 diffèrent par l'absence dans ce dernier d’un lien entre les nœuds 14 et
17. Comme l'indique le tableau 2.2 (resp. le tableau 2.3) cette différence bien que légère a
néanmoins des conséquences très significatives sur les degrés d'autorité (resp. d'hubité)
attribués aux nœuds de ces deux graphes. En effet, nous remarquons qu'avec le graphe G2, les
nœuds 16, 17 et 18 obtiennent à eux trois 40% de l'autorité totale tandis que ces mêmes nœuds
n'obtiennent que 1% de l'autorité totale dans le graphe G3. Les nœuds 4, 5 et 6 totalisent quant
à eux plus de 90% de l’autorité dans le graphe G3 ! Ce "mauvais comportement" est dû au fait
que l'algorithme HITS se focalise sur un sous-graphe particulier du graphe d’autorité (ou
d’hubité) qui forme une structure appelée communauté. Nous considérerons dans ce chapitre
une communauté comme étant un sous-graphe connexe contenant beaucoup de liens internes
(i.e. des liens entre les nœuds du sous-graphe) et peu de liens externes (i.e. des liens avec des
45
Chapitre 2 L’effet TKC
1 2 3 7 8 9 12 13 14 15
4 5 6 10 11 16 17 18
(a)
3 3
4 17
3 3 3 4 3 3 4 3 3 3
5 6 10 11 16 18
3 1 2 1 3
(b)
46
Chapitre 2 L’effet TKC
1 2 3 7 8 9 12 13 14 15
4 5 6 10 11 16 17 18
(a)
3 2
4 17
3 3 3 4 3 3 4 2 2 3
5 6 10 11 16 18
3 1 2 1 3
(b)
Tableau 2.2 - Degrés d'autorité calculés par HITS pour les nœuds des graphes G2 et G3
%œud(s) 1,2,3,7,8,9,12,13,14,15 4 5 6 10 11 16 17 18
Graphe G2 0 0.14 0.14 0.17 0.04 0.04 0.17 0.14 0.14
Graphe G3 0 0.29 0.29 0.33 0.06 0.02 0.01 0 0
Tableau 2.3 - Degrés d’hubité calculés par HITS pour les nœuds des graphes G2 et G3
%œud(s) 4,5,6,10,11,16,17,18 1 2 3 7 8 9 12 13 14 15
Graphe G2 0 0.14 0.14 0.14 0.06 0.02 0.02 0.06 0.14 0.14 0.14
Graphe G3 0 0.27 0.27 0.27 0.12 0.02 0.02 0.01 0 0 0
47
Chapitre 2 L’algorithme MHITS
2.2.1 Principe
Le premier algorithme que nous proposons est une variante de l’algorithme HITS qui
traite la première cause de l’effet TKC. Le but de l’algorithme MHITS est de s’assurer que
tous les documents obtiennent un degré d’autorité et/ou d’hubité strictement positif quelque
soit la composante connexe à laquelle ils appartiennent. En effet, dans le cas où le graphe
d’autorité Go (resp. d’hubité Gh ) contient plusieurs composantes connexes, HITS n’assigne
des degrés d’autorité (resp. d’hubité) qu’aux nœuds appartenant à une seule de ces
composantes connexes. Concrètement, l’algorithme MHITS calcule les degrés d’autorité et
d’hubité des documents en appliquant les trois étapes suivantes :
ii) Calculer le vecteur propre principal xi (resp. y i ) pour chaque composante Cio (resp.
Cih ). Chaque vecteur xi (resp. y i ) est ensuite normalisé de telle sorte que ∑ j
xij = 1 (resp.
∑ j
yij = 1 ). Cette normalisation signifie que toutes les composantes possèdent une autorité
(resp. hubité) totale égale à 1.
iii) Calculer le degré d’autorité (resp. d’hubité) final de chaque nœud. Celui-ci est obtenu
en multipliant le degré d’autorité (resp. d’hubité) de chaque nœud dans la composante à
laquelle il appartient par un facteur qui reflète l’importance de cette composante. Nous avons
choisi ici de quantifier l’importance d’une composante par la proportion de nœuds du graphe
appartenant à cette composante. Cette méthode de pondérer les degrés d’importance des
nœuds est similaire à celle utilisée par Lempel et Morin [Lempel and Moran 00] dans
l’algorithme SALSA. Concernant cette pondération des composantes, on pourrait également
utiliser le nombre de liens au sein de la composante ou encore la valeur propre principale
associée au vecteur d’autorité (ou d’hubité) de la composante.
Lorsque le graphe Go (ou Gh ) est connexe, il est évident que l’algorithme MHITS est
équivalent à l’algorithme HITS. Par ailleurs, l’inconvénient majeur de l’algorithme MHITS
est qu’il ne résout pas la deuxième cause de l’effet TKC. Ainsi, si les composantes connexes
du graphe Go (resp. Gh ) contiennent plusieurs communautés, les nœuds n’appartenant pas à
la communauté "la plus importante" seront "défavorisés" car l’algorithme leur attribuera un
degré d’autorité (resp. d’hubité) très faible.
48
Chapitre 2 L’algorithme MHITS
Les différentes étapes de l’algorithme MHITS sont décrites par l’algorithme 2.1.
{C ,…, C } ← BFS ( AA )
1
h h
K
T
xk y
xk ← ; y k ← k // v 1 = ∑ vi est la norme L1 du vecteur v
xk 1 yk 1 i =1
fin
3. // Calculer le vecteur d’autorité o et d’hubité h :
o ← 0 & ×1 , h ← 0 & ×1 // 0 & ×1 est un vecteur colonne de dimension & contenant des zéros
pour k = 1… K faire
pour l = 1, … , Cko faire
j ← Cko ( l )
o j ← Cko xkl
fin
pour l = 1, … , Ckh faire
j ← Ckh ( l )
h j ← Ckh ykl
fin
fin
4. // Normalisation des vecteurs o et h :
o← o ; h← h
o1 h1
fin
49
Chapitre 2 L’algorithme MHITS
Tableau 2.4 - Degrés d'autorité et d'hubité calculés par MHITS pour les nœuds du graphe G1
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.17 0.17 0.17 0 0 0 0.18 0.13 0.18
Degré d’hubité 0.17 0.17 0.17 0 0 0 0.18 0.13 0.18 0 0 0
Hormis le fait de traiter la première cause de l’effet TKC, MHITS possède un autre
avantage par rapport à HITS concernant la convergence. La convergence de l’algorithme
HITS pose en effet problème lorsque la plus grande valeur propre de la matrice d’autorité (i.e.
matrice d’adjacence du graphe d’autorité) se répète [Farahat et al. 05]. Une telle situation est
illustrée par le graphe jouet G4 de la figure 2.6 et dont les vecteurs d’autorité et d’hubité
calculés par HITS sont indiqués par le tableau 2.5. La matrice d'autorité du graphe G4
possède deux valeurs propres : λ1 = 3 et λ2 = 3 . La valeur propre 3 est donc double, ce qui
explique les résultats "étranges" (nœuds ayant un degré d’autorité ou d’hubité négatif) du
tableau 2.5. Ces résultats sont en contradiction avec le théorème de Perron-Frobenius selon
lequel le vecteur propre principal d’une matrice symétrique définie positive (comme c’est le
cas des matrices d’autorité et d’hubité) est toujours positif.
L’algorithme MHITS quant à lui n’est pas concerné par ce problème de convergence
comme le montrent par exemple les résultats du tableau 2.6. MHITS traite en effet chaque
composante connexe du graphe d’autorité (et d’hubité) de manière indépendante.
50
Chapitre 2 L’algorithme &HITS
1 2 3 7 8 9
4 5 6 10 11 12
Tableau 2.5 - Degrés d'autorité et d'hubité calculés par HITS pour les nœuds du graphe G4
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.43 0.43 0.43 0 0 0 -0.1 -0.1 -0.1
Degré d’hubité 0.43 0.43 0.43 0 0 0 -0.1 -0.1 -0.1 0 0 0
Tableau 2.6 - Degrés d'autorité et d'hubité calculés par MHITS pour les nœuds du graphe G4
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.16 0.16 0.16 0 0 0 0.16 0.16 0.16
Degré d’hubité 0.16 0.16 0.16 0 0 0 0.16 0.16 0.16 0 0 0
Dans l’article [Kleinberg 99a], Kleinberg évoque le fait que les vecteurs propres
secondaires (par opposition au vecteur propre principal) de la matrice AT A (resp. AAT )
peuvent être utilisés pour obtenir les degrés d’autorités et d’hubité relatifs à d’autres
communautés (i.e. des communautés secondaires autres que la principale). Cette idée
proposée par Kleinberg n’est cependant pas satisfaisante en pratique car les vecteurs
d’autorité et d’huibté secondaires peuvent contenir des valeurs positives et des valeurs
négatives ce qui rend leur interprétation délicate. Le théorème de Perron-Frobenius nous dit
en effet que seul le vecteur propre principal d’une matrice symétrique définie positive est
positif. Si l’on considère le graphe G5 de la figure 2.7 et que l’on calcule les deux vecteurs
propres de la matrice d’autorité AT A associés aux deux plus grandes valeurs propres, nous
obtenons les résultats indiqués par le tableau 2.7.
51
Chapitre 2 L’algorithme &HITS
1 2 3 7 8 9 12 13 14
4 5 6 10 11 15 16
Tableau 2.7 – Premier et second vecteurs propres de la matrice G5o (matrice d’autorité associée à G5)
%œud 1,2,3,7,8,9,12,13,14 4 5 6 10 11 15 16
Premier vecteur
0 0.55 0.55 0.62 0.11 0.03 0.01 0
propre
Second vecteur
0 0.08 0.08 -0.02 -0.52 -0.63 -0.49 -0.29
propre
Nous remarquons que le premier vecteur ne contient que des valeurs positives alors que
le deuxième vecteur contient à la fois des valeurs positives et des valeurs négatives. La
présence de valeurs ayant des signes différents rend l’interprétation des vecteurs propres
secondaires difficile car cela nécessiterait de les inspecter manuellement, sachant que dans
certains cas c’est la partie négative qui est pertinente alors que dans d’autres cas c’est la partie
positive qui l’est.
Le calcul de plusieurs (K) vecteurs propres des matrices AT A et AAT revient en fait à
effectuer une décomposition en valeurs singulières (ou SVD : Singular Value Decomposition)
de la matrice d’adjacence A [Chikhi et al. 07]. Cette décomposition est donnée par [Golub
and Van Loan 96]:
A = U ± S + V± + B1 (2.1)
où : - U ± est une matrice de dimensions & × K contenant les K vecteurs propres de la matrice
d’hubité AAT . Cette matrice contient des valeurs positives et négatives.
- S + est une matrice diagonale de dimensions K × K contenant les valeurs propres par
ordre décroissant. Ces valeurs sont toujours positives car les matrices AT A et AAT sont
symétriques définies positives.
- V± est une matrice de dimensions K × & contenant les K vecteurs propres de la matrice
d’autorité AT A . Cette matrice contient des valeurs positives et négatives.
- B1 est une matrice de dimension & × & qui représente un modèle de bruit gaussien
("Gaussian noise model").
52
Chapitre 2 L’algorithme &HITS
Cette décomposition consiste en fait à trouver trois matrices U, S et V tel que la distance
euclidienne entre la matrice A et la matrice USV soit minimale [Golub and Van Loan 96].
L’équation (2.1) peut également être réécrite de la manière suivante :
A = X ± Y± + B1 (2.2)
où : - X ± = U ± ( S + )
12
est une matrice indiquant le degré d’hubité des documents dans
chacune des K communautés.
- Y± = ( S + ) V± est une matrice indiquant le degré d’autorité des documents dans
12
L’algorithme NHITS que nous proposons ici est basé sur l’idée de calculer plusieurs
vecteurs d’autorité (resp. d’hubité) puis de les combiner pour obtenir un seul vecteur
d’autorité (resp. d’hubité). Pour le calcul de plusieurs vecteurs d’autorité, nous envisageons
cette tâche comme un problème d’optimisation qui est proche de la SVD mais avec une
contrainte supplémentaire à savoir la positivité des matrices de la décomposition. Plus
précisément, nous cherchons à décomposer la matrice d’adjacence A en un produit de deux
matrices X et Y telles que :
A = X + Y+ + B 2 (2.3)
où : - X+ ∈ ℝ &+ × K et Y+ ∈ ℝ K+ × & sont des matrices positives et B 2 ∈ ℝ & × & est un modèle de
bruit gaussien.
Les matrices X et Y sont obtenues en optimisant la fonction objectif suivante :
J = min A - XY 2
(2.4)
X ≥ 0,Y ≥ 0
53
Chapitre 2 L’algorithme &HITS
d’autorité (resp. d’hubité) global est égal à la somme pondérée des K vecteurs d’autorité (resp.
d’hubité) ; chaque vecteur d’autorité (resp. d’hubité) étant pondéré par un coefficient qui
exprime l’importance de la dimension qu’il représente.
Le tableau 2.8 indique les degrés d’autorité et d’hubité des nœuds du graphe jouet G1 en
utilisant NHITS avec K=2. Nous constatons que NHITS assigne des degrés d’autorité (resp.
d’hubité) à tous les nœuds ayant des liens entrants (resp. sortants) malgré la non-connexité du
graphe d’autorité G1o .
Tableau 2.8 - Degrés d'autorité et d'hubité calculés par %HITS pour les nœuds du graphe G1
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.17 0.17 0.17 0 0 0 0.17 0.13 0.17
Degré d’hubité 0.17 0.17 0.17 0 0 0 0.17 0.13 0.17 0 0 0
Tableau 2.9 - Degrés d'autorité calculés par %HITS pour les nœuds des graphes G3
%œud(s) 1,2,3,7,8,9,12,13,14,15 4 5 6 10 11 16 17 18
Degré d’autorité 0 0.12 0.12 0.15 0.13 0.13 0.15 0.08 0.12
Tableau 2.10 - Degrés d’hubité calculés par %HITS pour les nœuds des graphes G3
%œud(s) 4,5,6,10,11,16,17,18 1,2,3 7 8,9 12 13,15 14
Degré d’hubité 0 0.11 0.09 0.09 0.09 0.11 0.08
54
Chapitre 2 L’algorithme &HITS
ykj ← ykj
kj
( X XY ) + 10
T
kj
−9
fin
pour i = 1… & et k = 1… K faire
xik ← xik
( AY ) T
ik
( XYY ) + 10
T
ik
−9
fin
jusqu’à convergence
3. // Normalisation des matrices X et Y et calcul du coefficient λ de chaque composante :
pour k = 1… K faire
λk = x.k 2 × y k . 2
// v 2
= ∑v
i =1
i
2
est la norme L2 du vecteur v
x. k
x. k =
x. k 1
y k.
yk. =
yk. 1
fin
4. // Calcul du vecteur d’autorité o et du vecteur d’hubité h :
o ← 0 & ×1 ; h ← 0 & ×1 // 0 & ×1 est un vecteur colonne de dimension n contenant des zéros
pour k = 1… K faire
o ← o + λk y k .T
h ← h + λk x.k
fin
5. // Normalisation des vecteurs o et h :
o← o ; h← h // v 1 = ∑v i est la norme L1 du vecteur v
o1 h1 i =1
fin
55
Chapitre 2 L’algorithme DocRank
2.4.1 Principe
56
Chapitre 2 L’algorithme DocRank
( ( LA ) ( LA ) )
T
( M o )ij = ij
(2.5)
∑ ( ( LA ) ( LA ) )
& T
k =1 ik
( ( AC ) ( AC ) )
T
( M h )ij = ij
(2.6)
∑ ( ( AC ) ( AC ) )
& T
k =1 ik
(∑ )
−α
( )
−α &
- L est une matrice diagonale de dimension & telle que lii = diout = a
j =1 ij
.
= (d ) = (∑ )
−α & −α
in
- C est une matrice diagonale de dimension & telle que cii i a
j =1 ji
.
- α ∈ ℝ est un paramètre de normalisation.
Théorème 1 :
Si la chaîne de Markov MCo est irréductible, alors elle possède une distribution
stationnaire unique o = ( o1 ,… , o& ) donnée par :
∑ a (d ) out −2α +1
&
i =1 ij i
oj = (2.7)
∑ (d )
& α out −2 + 2
i =1 i
où A = ( aij )i =1... & est la matrice d’adjacence et diout = ∑ k =1 aik est le nombre de liens sortants
&
j =1... &
du nœud i.
57
Chapitre 2 L’algorithme DocRank
Preuve :
Nous allons montrer que la distribution o vérifie la condition o = M oT o (i.e.
pour tout j = 1...& o j = M oT o ). ( ) j
( ( LA ) ( LA ) )
T
( M o )mj =
mj
∑ ( ( LA ) ( LA ) )
& T
k =1 mk
∑ ( LA ) ( LA )
&
i =1
=
im ij
∑ ∑ ( LA ) ( LA )
& &
k =1 i =1 im ik
∑ (a × (d ) )(a × (d ) )
& α α out − out −
i =1 im i ij i
=
∑ ∑
&
k =1 )(a ×(d
&
i =1 (a im (
× d iout )
−α
ik i
out −α
) )
∑ (a × a × (d ) ) out −2α
&
i =1 im ij i
=
∑ ( a × ( d ) × ( ∑ a ))
& −2α &
out
i =1 im i k =1 ik
∑ (a × a ×(d ) )
& −2α
out
i =1 im ij i
=
∑ (a × (d ) )
& −2α +1
out
i=1 im i
= ∑
&
& a × a × d out −2α
∑ i =1 im ij i ( ( ) )∑ &
(
a d iout
i =1 im )
−2α +1
m =1
∑ i =1 aim × di
& out −2α +1
( ( ) ) ∑ (d )
&
i =1 i
out −2α + 2
=∑
& ∑
&
i =1 (a im × aij × d iout ( )
−2α
)
∑ (d )
& −2α + 2
out
m =1
i =1 i
=
∑
&
a × d iout
i =1 ij ( )
−2α
(∑ &
m =1 im
a )
∑ (d ) out −2α + 2
&
i =1 i
∑ a × (d )
& −2α +1
out
i =1 ij i
=
∑ (d )
α & out −2 + 2
i =1 i
= oj □
58
Chapitre 2 L’algorithme DocRank
Théorème 2 :
Si la chaîne de Markov MCh est irréductible, alors elle possède une distribution
stationnaire unique h = ( h1 ,… , h& ) donnée par :
∑ a (d ) in −2α +1
&
i =1 ji i
hj = (2.8)
∑ (d )
& α in −2 + 2
i =1 i
où A = ( aij )i =1... & est la matrice d’adjacence et diin = ∑ k =1 aki est le nombre de liens sortants du
&
j =1... &
nœud i.
Preuve :
Un raisonnement similaire à celui utilisé pour prouver le théorème 1 peut être utilisé pour
montrer que h vérifie la condition h = M hT h .
59
Chapitre 2 L’algorithme DocRank
Dans le cas où la chaîne de Markov Mo (resp. Mh) n’est pas irréductible, nous montrons
qu’il est toujours possible d’utiliser le résultat du théorème 1 (resp. théorème 2).
Les vecteurs d’autorité obtenus en utilisant DocRank avec ∝=1 sur les graphes jouets G1
et G3 sont respectivement indiqués par les tableaux 2.10 et 2.11. Pour le graphe G1, DocRank
attribue 51% de l’autorité à la communauté {4,5,6} et 49% à la communauté {10,11,12}. Pour
le graphe G3, le même algorithme attribue 35.5% de l’autorité à la communauté {4,5,6}, 30%
à la communauté {10, 11} et 34.5% à la communauté {16,17,18}. Nous remarquons ainsi que
la normalisation effectuée par DocRank lui permet de distribuer l’autorité (et l’hubité) aux
nœuds appartenant à différentes communautés. Le paramètre ∝ de l’algorithme permet de
contrôler la façon avec laquelle cette distribution doit être faite.
60
Chapitre 2 Environnement d’expérimentation
Tableau 2.10 - Degrés d'autorité et calculés par DocRank (∝=1) pour les nœuds du graphe G1
%œud 1 2 3 4 5 6 7 8 9 10 11 12
Degré d’autorité 0 0 0 0.17 0.17 0.17 0 0 0 0.19 0.11 0.19
Tableau 2.11 - Degrés d'autorité calculés par DocRank (∝=1) pour les nœuds du graphe G3
%œud(s) 1,2,3,7,8,9,12,13,14,15 4 5 6 10 11 16 17 18
Degré d’autorité 0 0.10 0.10 0.15 0.15 0.15 0.17 0.06 0.11
Dans cette section, nous présentons la méthodologie utilisée pour l’évaluation des
différents algorithmes de calcul de centralité proposés dans le cadre de cette thèse. Nous
décrivons notamment les données ainsi que les mesures utilisées pour la comparaison des
différents algorithmes.
Les tableaux 2.12 et 2.13 résument les propriétés des huit graphes de documents que
nous avons utilisés pour nos différentes expérimentations. Ces huit graphes sont de nature
différente puisque quatre d’entre eux sont des graphes de pages web alors que les quatre
autres sont des graphes d’articles scientifiques.
Nous avons construit les graphes des tableaux 2.12 et 2.13 en utilisant la méthode
proposée par Kleinberg dans [Kleinberg 99a]. Celle-ci consiste à interroger un moteur de
recherche avec une requête afin de récupérer les 200 premiers documents retournés par le
moteur. Cet ensemble initial de pages web appelé "Root Set (RS)" est ensuite étendu en deux
étapes : dans la première étape (extension avant), un crawler est utilisé afin de rajouter à RS
les documents pointés par un document appartenant à RS (en limitant ce nombre à 50 par
document) ; la deuxième étape (extension arrière) consiste à rajouter au "root set" des
documents qui pointent vers des pages appartenant à RS (en limitant également ce nombre à
50 par document). La deuxième étape nécessite l’utilisation d’un moteur de recherche afin
d’avoir la liste des URL qui pointent vers une page web donnée.
Les graphes Apple, Armstrong, Jaguar et Washington ont ainsi été construits en
interrogeant le moteur de recherche Google avec des requêtes qui correspondent aux noms des
graphes. Les graphes Plasma_Physics et Solar_Wind ont quant à eux été collectés en
interrogeant la base documentaire de l’ADS en utilisant respectivement les requêtes "Plasma
physics" et "Solar wind".
Enfin, les graphes Citeseer et Cora sont des graphes d’articles scientifiques dans le
domaine de l’informatique. Ils ont été collectés et annotés par Lu et Getoor [Lu and Getoor
03] ; ils sont disponibles à l’adresse [URL 1]. Chaque document de Cora appartient à l’une
des thématiques suivantes : réseaux de neurones, algorithmes génétiques, apprentissage par
renforcement, théorie de l’apprentissage, apprentissage de règles, méthodes probabilistes, et
61
Chapitre 2 Environnement d’expérimentation
raisonnement par cas. Les documents de Citeseer appartiennent à cinq thématiques : agents,
bases de données, recherche d’information, apprentissage, et interaction homme-machine.
Tableau 2.13 – Propriétés des graphes de pages web utilisés pour les expérimentations
Tableau 2.14 - Propriétés des graphes d’articles scientifiques utilisés pour les expérimentations
62
Chapitre 2 Environnement d’expérimentation
∑ d (x )
K in
ORQ ( x ) = i =1 i
(2.9)
1+ ∑ ∑ co ( x , x )
K K
i =1 j =i +1 i j
où x est un vecteur contenant les numéros des K documents classés comme meilleurs
autorités, d in ( xi ) est le degré entrant du document xi et co ( xi , x j ) est la similarité de co-
citation [Small 73] entre les documents xi et x j . Plus la valeur de cet indice est grande
meilleure est la qualité du "ranking".
63
Chapitre 2 Environnement d’expérimentation
De manière similaire, la liste des K documents ayant le plus fort degré d’hubité sera
évaluée par l’indice HRQ (Hubs Ranking Quality) suivant :
∑ d (x )
K out
HRQ ( x ) = i =1 i
(2.10)
1+ ∑ ∑ cb ( x , x )
K K
i =1 j = i +1 i j
où x est un vecteur de dimension K contenant les numéros des documents classés comme
meilleurs hubs, d out ( xi ) est le degré sortant du document xi et cb ( xi , x j ) est la similarité de
couplage bibliographique [Kessler 63] entre les documents xi et x j . Plus la valeur de cet
indice est grande, meilleure est la qualité du "ranking".
La deuxième mesure que nous proposons permet de mesurer la diversité thématique au
sein de la liste des K documents les plus importants. Cette mesure nécessite toutefois de
disposer d’informations concernant la thématique de chaque document (ces informations sont
aussi dites externes). Pour l’évaluation de la diversité thématique au sein de la liste des K
documents ayant le plus fort degré d’autorité, nous proposons l’indice TDO (Topic Diversity
of Authorities) défini par :
T
ci c
TDO ( c ) = −∑ log i (2.11)
i =1 K K
où c est un vecteur de dimension T tel que chaque entrée ci de ce vecteur indique le nombre
de documents (parmi K) appartenant à la thématique numéro i. Il s’agit en fait d’une entropie
qui vaut 0 si les K documents appartiennent à la même thématique. Plus la valeur de cet indice
est grande plus il y a de thématiques dans la liste des K meilleures autorités.
Pour l’évaluation de la diversité thématique dans la liste des K documents ayant le plus
fort degré d’hubité, nous proposons l’indice TDH (Topic Diversity of Hubs) défini par :
T
ci c
TDH ( c ) = −∑ log i (2.12)
i =1 K K
où c est un vecteur de dimension T tel que chaque entrée ci de ce vecteur indique le nombre
de documents hubs (parmi K) appartenant à la thématique numéro i. Il s’agit en fait d’une
entropie qui vaut 0 si les K documents appartiennent à la même thématique. Plus la valeur de
cet indice est grande plus il y a de thématiques dans la liste des K meilleurs hubs.
Les indices ORQ et HRQ permettent de mesurer l’effet TKC sans utiliser d’informations
externes tandis que les critères TDO et TDH permettent de mesurer la diversité thématique en
utilisant des informations additionnelles concernant la thématique de chaque document.
Lors de nos expérimentations, nous avons comparé les onze algorithmes suivants :
DEG (centralité de degré, équivalente à DocRank avec α = 0.5 ) – HITS – PageRank –
SALSA – HubAvg – MHITS – NHITS_10 (NHITS avec K = 10 ) – NHITS_20 ( K = 20 ) –
DocRank_0 (DocRank avec α = 0 ) – DocRank_1 ( α = 1 ) – DocRank_15 ( α = 1.5 ).
64
Chapitre 2 Résultats expérimentaux
Pour chacun des algorithmes étudiés et pour chaque graphe de documents, nous donnons
la liste des dix documents ayant le plus fort degré d’autorité, ainsi que la liste des dix
documents ayant le plus fort degré d’hubité (voir tableaux 2.15 à 2.28). Nous reportons
également pour chaque algorithme, les valeurs des mesures ORQ@10 (ORQ avec K=10),
ORQ@20, HRQ@10 et HRQ@20. Cependant, le nombre de résultats étant important, nous
présentons dans cette section uniquement les listes des 10 documents ayant le plus fort degré
d’autorité retournées par HITS, PageRank et DocRank_1. Les listes (des meilleurs autorités et
des meilleurs hubs) retournées par les autres algorithmes sont reportées dans l’annexe B.
Sur le plan qualitatif, nous constatons que :
- HITS se focalise toujours sur une seule communauté (ou thématique). Cette thématique
est souvent peu pertinente ou très générale par rapport à la requête qui a permis de construire
le graphe de documents ; on parle alors de "topic drift" ou de "topic generalization". C’est le
cas par exemple des résultats obtenus avec le graphe Armstrong où les documents ayant les
plus forts degrés d’autorité sont des sites de sport (Nhl, Nba, etc.). La liste des dix meilleurs
hubs retournée par HITS nous permet d’avoir une explication pour ces résultats : plusieurs de
ces hubs parlent d’un joueur de hockey professionnel qui s’appelle Derek Armstrong.
- PageRank donne de meilleurs résultats que l’algorithme HITS puisque des documents
pertinents et traitant différentes thématiques sont présents dans la liste des dix meilleures
autorités. Mais PageRank classe certains documents comme étant importants alors qu’ils ne
sont pas pertinents par rapport à la requête initiale. Les résultats avec les graphes Armstrong,
Jaguar et Washington illustrent bien cette situation où l’on retrouve dans la liste des
meilleures autorités les sites du logiciel MediaWiki et de l’organisation
WikiMediaFoundation.
- DocRank ne souffre pas de l’effet TKC puisque la liste des meilleures autorités qu’il
calcule contient des documents pertinents et appartenant à différentes thématiques. Par
exemple pour le graphe Armstrong, on retrouve une page sur le musicien Louis Armstrong, la
page officielle du comté d’Armstrong aux Etats-Unis ou encore une page sur le cycliste Lance
Armstrong.
D’un point de vue quantitatif, nous constatons que l’algorithme HITS obtient dans la
plupart des cas les plus faibles valeurs d’ORQ et d’HRQ. La simple centralité de degré obtient
de meilleurs résultats que HITS. PageRank obtient dans tous les cas des résultats largement
meilleurs que ceux de HITS ; dans certains cas il est aussi meilleur que la centralité de degré.
L’algorithme NHITS permet d’obtenir de meilleurs résultats que HITS mais ses performances
restent toutefois bien en-dessous de celles de PageRank. DocRank quant à lui réalise les
meilleures performances dans le sens où les documents qu’il classe comme étant importants
ont à la fois beaucoup de liens et appartiennent à des communautés différentes. Cette dernière
propriété lui permet de se distinguer de la centralité de degré qui ne tient compte que du
nombre de liens.
65
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme URL de liens de liens
d’autorité
entrants sortants
0.0087516 http://www.xbox360fanboy.com 279 120
0.0087142 http://www.secondlifeinsider.com 271 121
0.0087108 http://www.cssinsider.com 251 47
0.0086881 http://www.dsfanboy.com 257 121
0.0086872 http://www.bbhub.com 253 116
HITS 0.0086849 http://www.pspfanboy.com 270 116
0.008683 http://www.ps3fanboy.com 254 116
0.0086821 http://www.nintendowiifanboy.com 254 121
0.0086768 http://www.wowinsider.com 252 116
0.0086758 http://www.droxy.com 251 121
0.029706 http://www.download.com/itunes-for-windows/... 46 12
0.015402 http://www.versiontracker.com 71 1
0.014821 http://www.macfixit.com 76 1
0.013073 http://www.apple.com 280 0
0.011134 http://store.apple.com 47 0
PageRank 0.010116 http://www.macworld.com 122 7
0.0092659 http://www.mac.com 57 1
0.0074745 http://www.imaconlinepoker.com 3 1
0.0071086 http://www.macrumors.com In:98 Out:10 98 10
0.0071011 http://www.macpokeronline.com In:9 Out:1 9 1
0.041252 http://www.apple.com 280 0
0.017196 http://www.tuaw.com 351 157
0.013126 http://www.mac.com 57 1
0.012662 http://www.engadget.com 319 130
0.012131 http://www.apple-history.com 114 0
DocRank1 0.011356 http://www.macworld.com 122 7
0.011272 http://www.appleinsider.com 117 12
0.011255 http://www.download.com/itunes-for-windows/... 46 12
0.01118 http://www.macrumors.com 98 10
0.010859 http://developer.apple.com/wwdc In:84 Out:0 84 0
Tableau 2.15 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Apple
66
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme URL de liens de liens
d’autorité
entrants sortants
0.02958 http://www.nhl.com 11 0
0.029067 http://www.nba.com 8 0
0.02891 http://www.golfdigest.com 7 0
0.028754 http://www.nbcolympics.com/index.html?qs=pt=espn 6 0
0.028754 http://espnsportsfigures.com 6 0
HITS 0.028754 http://www.espnbooks.com 6 0
0.028754 http://espnzone.com 6 0
0.028754 http://joinourteam.espn.com/joinourteam 6 0
0.028754 http://www.wnba.com 6 0
0.028754 http://www.jayski.com 6 0
0.024714 http://www.mediawiki.org 56 1
0.023196 http://wikimediafoundation.org 49 1
0.022289 http://www.livestrong.org 64 2
0.016661 http://www.rdale.k12.mn.us/ahs 51 1
0.014649 http://www.store-laf.org 10 1
PageRank 0.014279 http://www.schoolidentity.com/schoolid/store.html... 1 1
0.01018 http://www.livestrongarmy.org 3 2
0.0095567 http://www.sanbornwebdesigns.com 3 1
0.0095567 http://www.glassart.biz 3 1
0.0078046 http://www.thepaceline.com 56 8
0.019575 http://www.satchmo.net 100 4
0.017716 http://www.armstrongcounty.com 58 2
0.017417 http://www.armstrong.com 63 3
0.017002 http://www.armstronggarden.com 51 1
0.016973 http://www.joearmstrong.com 50 1
DocRank1 0.016886 http://www.armstrongmold.com 50 0
0.016722 http://www.armstrongtools.com 51 0
0.01651 http://www.livestrong.org 64 2
0.016492 http://www.armstrongglass.com 52 4
0.016488 http://www.livestrong.org/site/c.jvKZLbMRIsG/... 56 0
Tableau 2.17 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Armstrong
67
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme URL de liens de liens
d’autorité
entrants sortants
0.0073099 http://www.cssinsider.com 170 78
0.0072756 http://www.joystiq.com 175 121
0.0072744 http://www.brianalvey.com 172 2
0.007272 http://www.calacanis.com 171 4
0.0072699 http://www.thediabetesblog.com 170 133
HITS 0.0072694 http://www.wowinsider.com 170 133
0.0072667 http://www.thecardioblog.com 169 133
0.0072661 http://www.ps3fanboy.com 169 133
0.0072661 http://www.pspfanboy.com 169 133
0.0072655 http://www.cinematical.com 172 148
0.019909 http://www.mediawiki.org 61 2
0.015637 http://www.oreillylearning.com 36 4
0.010475 http://www.jaguars.com 55 5
0.0098033 http://wikimediafoundation.org 40 1
0.009027 http://wikimediafoundation.org/wiki/privacy_policy 22 1
PageRank 0.0090211 http://www.flickr.com/photos/ableman/sets/72157... 46 46
0.0085951 http://www.jag-lovers.org 146 4
0.0072018 http://www.jagweb.com 72 4
0.0056405 http://www.weblogsinc.com 139 67
0.0053051 http://www.jcna.com 115 1
0.02085 http://www.jag-lovers.org 146 4
0.018696 http://www.jaguar.com 119 0
0.017324 http://www.flickr.com/photos/ableman/sets/72157... 46 46
0.012429 http://www.jcna.com 115 1
0.011683 http://www.apple.com/macosx 62 0
DocRank1 0.010454 http://www.mediawiki.org 61 2
0.010148 http://www.jaguars.com 55 5
0.0094735 http://www.catdriver.com 81 0
0.009247 http://www.apple.com 56 0
0.0090213 http://www.jagbits.com 73 7
Tableau 2.19 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Jaguar
68
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme URL de liens de liens
d’autorité
entrants sortants
0.027657 http://www.redskins.com 115 8
0.025124 http://www.denverbroncos.com 36 1
0.025102 http://www.sf49ers.com 36 0
0.025059 http://www.chicagobears.com 36 1
0.025035 http://www.neworleanssaints.com 35 1
HITS 0.025035 http://www.stlouisrams.com 35 0
0.025034 http://www.seahawks.com 50 0
0.024962 http://www.steelers.com 39 0
0.024742 http://www.buffalobills.com 35 0
0.024724 http://www.chargers.com 36 0
0.019436 http://www.mediawiki.org 102 2
0.010539 http://www.usa.gov 56 0
0.010256 http://www.parks.wa.gov 82 2
0.0098836 http://wikimediafoundation.org 88 1
0.009319 http://wikimediafoundation.org/wiki/Privacy_policy 65 1
PageRank 0.0078055 http://www.washingtonpost.com 203 38
0.0062546 http://www.tvw.org/index.cfm 14 0
0.0059141 http://www.lib.washington.edu 49 3
0.0048118 http://www.washingtonwine.org 56 4
0.0047809 http://www.k12.wa.us 73 4
0.013254 http://www.washingtonpost.com 203 38
0.011511 http://access.wa.gov 188 0
0.011337 http://www.washington.org 84 5
0.010936 http://www.worldtimeserver.com/current_time_in... 48 8
0.010817 http://geo.craigslist.org/iso/us/wa 48 1
DocRank1 0.010374 http://www.imdb.com/name/nm0000243 48 1
0.01029 http://www.flickr.com/photos/tags/washington 48 8
0.010115 http://www.washingtoncountytn.com 50 3
0.0099007 http://www.missingkids.com/precreate/WA.html 53 0
0.009853 http://www.washingtonwine.org 56 4
Tableau 2.21 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Washington
69
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme Titre de liens de liens
d’autorité
entrants sortants
0.067149 Dust-acoustic waves in dusty plasmas 143 7
0.046614 Dusty plasmas in the solar system 107 26
0.044212 Laboratory observation of the dust-acoustic wave mode 86 5
0.034683 Plasma crystal: Coulomb … in a dusty plasma 100 4
0.033738 Direct observation of Coulomb … dusty plasmas 97 0
HITS 0.028541 Dust ion-acoustic wave 59 2
0.026343 Cosmic Dusty Plasmas 70 58
0.023738 The electrostatics of a dusty plasma 68 9
0.021574 Laboratory studies of waves and … in dusty plasmas 53 34
0.020679 Condensed Plasmas under Microgravity 66 0
0.0047334 Centrifugally driven diffusion of Iogenic plasma 11 1
0.0045094 Factors governing the ratio of inward to … 4 1
0.0044475 Helical microtubules of graphitic carbon 37 0
0.0043543 N-dependence in the classical one-component … 50 0
0.0040362 A General Formula for the Estimation of Dielectro… 81 0
PageRank 0.0038163 Ionization Equilibrium and Radiative Cooling … 75 23
0.0036043 Radiative cooling of a low-density plasma 69 16
0.0035877 A survey of the plasma electron environment of Jupit... 14 3
0.0033341 Strong turbulence of plasma waves 50 0
0.0033016 A General Theory of the Plasma of an Arc 50 0
0.0092894 Plasma perspective on strong field multiphoton… 53 0
0.0091347 Plasma Losses by Fast Electrons in Thin Films 50 0
0.0090982 Interaction of "Solitons" in a Collisionless Plasma… 50 0
0.0081908 The ULYSSES solar wind plasma experiment 51 0
0.0079346 Fast-wave heating of a two-component plasma 50 0
DocRank1 0.0078562 Plasma spectroscopy 64 0
0.0076682 SWE, A Comprehensive Plasma Instrument for … 56 2
0.0076624 Plasma source ion-implantation technique for … 50 7
0.0076033 Random Phasing of High-Power Lasers for Uniform… 51 0
0.0075752 CLOUDY 90: Numerical Simulation of Plasmas … 54 9
Tableau 2.23 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Plasma_Physics
70
Chapitre 2 Résultats expérimentaux
%ombre %ombre
Degré
Algorithme Titre de liens de liens
d’autorité
entrants sortants
0.010016 Transition region, corona, and solar wind in coronal… 105 31
0.0094714 UVCS/SOHO Empirical … in the Solar Corona 106 7
0.0088182 Spectroscopic Constraints … Polar Solar Corona … 92 23
0.0084365 Wave heating and acceleration … ions by cyclotron… 87 6
0.0082958 Two-Fluid Model for Heating of the Solar Corona … 77 32
HITS 0.0080378 Heating and cooling … cyclotron waves … 64 39
0.0075321 On the preferential acceleration and heating of … ions 71 14
0.0074118 Ion Cyclotron Wave Dissipation in the Solar Corona:… 63 32
0.0074003 Transition region, corona, and solar wind in coronal… 72 13
0.0073041 An Empirical Model of a Polar Coronal Hole at … 84 21
0.012919 Plasma waves associated with energetic particles… 56 3
0.0077485 Upstream particles observed in the earth's foreshock… 7 2
0.0075253 Upstream particle spatial gradients and plasma waves 8 2
0.0065994 Bi-directional streaming of solar wind electrons … 28 0
0.0052161 Magnetic loop behind an interplanetary shock… 122 1
PageRank 0.0050967 Solar wind protons - Three-dimensional velocity… 109 2
0.0050043 Dynamics of the Interplanetary Gas and Magnetic… 147 2
0.0047329 Interplanetary dynamical processes. 125 0
0.0043107 Microinstabilities upstream of the earth's bow shock -... 2 1
0.0042364 Measurement of the rugged invariants of … 152 8
0.011246 Abundances of the elements - Meteoritic and solar 66 0
0.0077556 The Angular Momentum of the Solar Wind 92 3
0.0058943 Plasma waves associated with energetic particles … 56 3
0.005427 Introduction to the solar wind 54 0
0.005193 Solar Wind Electron Proton Alpha Monitor … 107 32
DocRank1 0.0050014 Coronal Expansion and Solar Wind 106 0
0.0048544 The ULYSSES solar wind plasma experiment 103 0
0.0047523 Dynamics of the Interplanetary Gas and Magnetic … 147 2
0.0047428 Energy coupling between the solar wind and the … 81 0
0.0046232 Propagation of cosmic rays in the solar wind. 59 0
Tableau 2.25 – Liste des 10 documents ayant le plus fort degré d’autorité dans le graphe Solar_Wind
71
Chapitre 2 Résultats expérimentaux
72
Chapitre 2 Résultats expérimentaux
Les tableaux 2.29 et 2.30 indiquent les résultats de la diversité thématique en utilisant les
graphes Cora et Citeseer. Nous constatons clairement que l’algorithme HITS est celui qui
souffre le plus de l’effet TKC et que l’algorithme DocRank avec α ≥ 1 réussit à faire ressortir
des documents appartenant à diverses communautés (ou thématiques). Lorsque α < 0.5 nous
remarquons que les résultats obtenus sont conformes à l’interprétation du paramètre α que
nous avons donnée dans la section 2.4.2 à savoir que DocRank favorise l’effet TKC.
73
Chapitre 2 Bilan
2.7 Bilan
Nous avons mis l’accent, dans ce chapitre, sur le fait que le phénomène TKC représente
un sérieux problème pour de nombreux algorithmes de calcul de centralité. Hormis
l’algorithme PageRank qui est assez robuste à l’effet TKC, nous avons remarqué que la
majorité des algorithmes de calcul de centralité existants sont très vulnérables à ce symptôme.
Dans le but de pallier à ce problème, nous avons proposé trois algorithmes fondés sur des
principes différents. L’évaluation expérimentale de nos algorithmes a montré les très bonnes
performances de l’algorithme DocRank.
Dans la deuxième partie de cette thèse, nous allons nous intéresser à la notion de
communauté de manière plus détaillée. Nous abordons notamment la problématique de
l’identification de structures de communautés (ISC) dans les graphes de documents.
74
Chapitre 3 Etat de l’art sur l’ISC
Les réseaux complexes (ou graphes de terrain) possèdent plusieurs caractéristiques qui
les distinguent des graphes aléatoires (tels que les graphes d’Erdös-Rényi). L’organisation des
nœuds de ces réseaux en groupes appelés communautés est une des propriétés les plus
importantes des réseaux complexes. Intuitivement, une communauté est un ensemble de
nœuds dans lequel il y a une forte concentration de liens par rapport au nombre de connexions
avec les autres nœuds du graphe. Ces dernières années, en particulier, depuis l’article de
référence de Girvan et Newman [Girvan and Newman 02], l’identification de telles structures
a suscité l’intérêt d’un grand nombre de chercheurs dans diverses disciplines, notamment avec
l’entrée en jeu des physiciens et des mathématiciens. Depuis, une panoplie de techniques a été
proposée et de nouvelles méthodes continuent d’apparaître régulièrement. Ceci étant, nous
pouvons dire que l’ISC est un domaine vaste et interdisciplinaire auquel contribuent plusieurs
communautés.
Après une présentation des différentes définitions de la notion de communauté, nous
abordons le problème de l’identification de structures de communautés en décrivant les
principales approches existantes. Les techniques d’ISC peuvent être classées de différentes
façons. Dans le cadre de cette thèse, nous les avons regroupées en deux catégories à savoir les
approches génératives (basées sur un modèle génératif) et les approches non génératives. Ces
dernières seront d’abord présentées de manière succincte alors que les premières feront
ensuite l’objet d’une étude plus détaillée. Enfin, en utilisant un certain nombre de critères que
nous avons établis, nous analysons l’adéquation des différentes techniques exposées pour
l’identification de communautés dans les graphes de documents.
75
Chapitre 3 &otion de communauté et problème de l’ISC
Dans l’édition 2010 du dictionnaire Larousse, le mot communauté est défini par :
76
Chapitre 3 &otion de communauté et problème de l’ISC
un chemin entre tous les nœuds du graphe quelque soit sa longueur et en ignorant l’orientation
des arêtes. Dans le cas où le graphe à analyser contient plusieurs composantes connexes (i.e.
n’est pas connexe), il faudra alors considérer chaque composante comme étant un graphe à
part entière et rechercher des communautés dans chacune de ces composantes. Cependant,
pour des raisons de simplification, nous considérons tout au long de cette thèse, que les
graphes étudiés sont connexes. De plus, dans les définitions suivantes nous considérons que
les graphes sont non-orientés.
Une des premières définitions de la notion de communauté a été proposée par Luce et
Perry [Luce and Perry 49] dans le cadre de leurs travaux sur l’analyse des réseaux sociaux. Ils
ont ainsi proposé le terme clique pour faire référence à un groupe composé d’au moins trois
personnes qui se connaissent toutes. Ce terme a ensuite été repris en théorie des graphes pour
désigner un sous-graphe complet i.e. un ensemble de sommets deux-à-deux adjacents. La
figure 3.1 illustre des exemples de cliques. Sur cette figure, C1 et C3 sont des cliques ; C2
n’est par contre pas une clique car ses nœuds ne sont pas tous connectés.
C1 C2 C3
Figure 3.1 – Exemple d’un graphe contenant deux cliques (C1 et C3)
- n-clique : c’est un sous-graphe maximal tel que la distance géodésique entre chaque
couple de ses sommets est inférieure ou égale à n [Alba 73].
- n-clan : c’est une n-clique dont le diamètre est inférieur ou égal à n [Mokken 79].
77
Chapitre 3 &otion de communauté et problème de l’ISC
Afin d’illustrer ces différentes notions, considérons le graphe de la figure 3.2. Ce graphe
contient entre autres les structures suivantes :
• Trois cliques : {1,2,3,4}, {2,4,5}, {5,6,8}.
• Quatre 2-cliques : {1,2,3,4,5}, {2,4,5,6,8}, {5,6,7,8,9}, {6,7,8,9,10}.
• Trois 2-clans : {1,2,3,4,5}, {2,4,5,6,8}, {6,7,8,9,10}.
• Cinq 2-clubs : {1,2,3,4,5}, {2,4,5,6,8}, {5,6,7,8}, {5,6,8,9}, {6,7,8,9,10}.
• Un 3-core : {1,2,3,4}
• Trois 2-plex : {1,2,3,4,5}, {2,4,5,6,8}, {6,7,8,9,10}.
1 2 6 7
5 10
3 4 8 9
i∈C
i
out
78
Chapitre 3 &otion de communauté et problème de l’ISC
Une autre définition de la notion de communauté est celle d’un groupe de sommets (ou
de points) qui sont à la fois fortement similaires entre eux et faiblement similaires aux
sommets appartenant aux autres groupes [Fortunato 10]. Cette définition, équivalente à celle
d’un cluster en statistiques et en fouille de données, repose sur l’utilisation d’une mesure de
proximité adaptée au type des objets à regrouper. En pratique, cette mesure de proximité peut
correspondre soit à une mesure de similarité, soit à une mesure de distance. La littérature sur
le clustering contient un grand nombre de travaux sur les mesures de similarité et de distance ;
nous présentons ici celles qui sont les plus utilisées.
C1 C2 C3
Figure 3.3 – Exemple de graphe contenant une communauté faible (C1) et
une communauté forte (C3)
Dans le cas où les objets à comparer peuvent être représentés sous forme de vecteurs à n
dimensions sur un espace euclidien, on peut alors utiliser des mesures de proximité entre
vecteurs telles que la distance euclidienne ou la similarité du cosinus définies respectivement
par [Xu and Wunsch 08] :
n
d euc ( x, y ) = ∑( x − y )
2
i i (3.1)
i =1
79
Chapitre 3 &otion de communauté et problème de l’ISC
yt ⋅ x
scos ( x, y ) = (3.2)
x y
n n
où x, y ∈ ℝ n et x = ∑x
i =1
i
2
, y = ∑y
i =1
i
2
sont les normes L2 des vecteurs x et y
respectivement.
Si l’on considère par contre que chaque objet est représenté par l’ensemble de ses
attributs (par exemple un sommet sera représenté par l’ensemble des sommets qui lui sont
adjacents), le calcul de la proximité entre deux objets peut dans ce cas être fait en utilisant des
mesures telles que l’indice (ou similarité) de Jaccard défini par [Xu and Wunsch 08] :
Ax ∩ Ay
s jac ( x, y ) = (3.3)
Ax ∪ Ay
Il est également possible d’utiliser des mesures de proximité issues de la théorie des
graphes telle que la distance du plus court chemin, appelée aussi distance géodésique. Cette
métrique est définie comme étant le nombre minimal de liens qu’il faut traverser pour aller
d’un sommet à un autre [West 00]. Une mesure de similarité alternative, très utilisée pour le
partitionnement de graphes, est celle du nombre de chemins indépendants entre deux nœuds.
Elle correspond au nombre minimal de sommets qu’il faut supprimer afin de séparer les deux
nœuds [West 00].
En se basant sur le principe de la marche aléatoire (cf. section 1.3.1), plusieurs
chercheurs ont proposé des mesures de distance entre deux sommets dans un graphe. Par
exemple dans [Zhou et al. 07], les auteurs proposent d’utiliser comme mesure de distance le
nombre moyen de pas aléatoires nécessaires pour faire un aller-retour entre deux sommets.
Les auteurs appellent cette mesure le "average commute time", c’est-à-dire le temps moyen
d’un aller-retour entre deux sommets.
Une définition plus récente de la notion de communauté est basée sur l’utilisation d’une
fonction de qualité. Cette famille de définitions a d’ailleurs reçu l’attention d’un grand
nombre de chercheurs depuis la publication en 2004 d’un article par Newman et Girvan
[Newman and Girvan 04]. Une fonction de qualité est une fonction qui associe à un sous-
graphe S une valeur quantifiant le fait que S correspond à une communauté.
Suite à l’article de référence de Newman, plusieurs fonctions de qualité ont été proposées
par les chercheurs. Nous allons cependant nous contenter ici de présenter celle introduite par
Newman connue sous le nom de la modularité. Celle-ci repose sur l’idée qu’un sous-graphe
forme une communauté si la distribution des liens entre ses nœuds n’est pas due au hasard.
Plus précisément, la modularité mesure la divergence de la distribution des liens dans le sous-
graphe par rapport à la distribution des liens dans un graphe aléatoire qui ne contient pas de
80
Chapitre 3 &otion de communauté et problème de l’ISC
où d S est égale à la somme des degrés des nœuds appartenant à S . Le premier terme de la
formule 1.1 correspond à la proportion de liens entre les nœuds du sous-graphe S, tandis que
le deuxième terme correspond à la proportion de liens dans un graphe aléatoire ayant la même
taille et la même distribution des degrés que S.
Les fonctions de qualité et en particulier la modularité sont généralement utilisées pour
estimer la qualité d’une partition des sommets d’un graphe en communautés. Dans cette
optique, la modularité associée à une partition P = ( C1 ,… , Ck ) est égale à la somme de la
modularité des communautés qui la composent i.e. :
2
k EC d
k
Q( P ) = ∑ Q ( Ci ) = ∑ i − i
C
i =1 i =1 M 2M
Cette formule peut également être réécrite de la manière suivante :
& &
aij di d j
Q ( P ) = ∑∑ − δ ( ci , c j ) (3.5)
i =1 j =1 2 M 4M 2
81
Chapitre 3 &otion de communauté et problème de l’ISC
signifie que la partition P1 est meilleure que P2 et que cette dernière ne correspond pas à une
structure de communautés.
La modularité a été initialement proposée par Newman comme solution au problème
suivant : étant données K partitions des sommets d’un graphe où chaque partition contient un
nombre différent de communautés, quelle est la meilleure de ces K partitions ? La modularité
semblait alors être une réponse très prometteuse à ce problème (qui était jusque-là sans
solution satisfaisante) jusqu’à ce que Fortunato et Barthélemy [Fortunato and Barthélemy 07]
remettent en cause ce principe de sélection de la meilleure partition en se basant sur la
modularité. Ils montrent en effet que la modularité favorise les partitions en communautés de
grande taille. Autrement dit, cela signifie que si le graphe contient plusieurs communautés et
que certaines de ces communautés sont de petite taille, la modularité tend à favoriser les
partitions où les petites communautés ont été regroupées. Fortunato et Barthélemy montrent
plus précisément que pour un graphe contenant L liens, la modularité favorise les partitions
composées de communautés ayant au moins L 2 liens, même si le graphe contient en
réalité des communautés ayant un nombre de liens inférieur à L 2.
A C E G
B D F H
82
Chapitre 3 Approches non génératives pour l’ISC
1 2 6 7
3 4 8 9
C1 C2
C3 C4
Figure 3.5 – Exemple de graphe contenant deux communautés fortes (C1 et C2)
et deux communautés faibles (C3 et C4)
Nous mettons dans cette catégorie toutes les approches qui ne sont pas basées sur un
modèle génératif. A leur tour, ces algorithmes peuvent être classés en plusieurs catégories.
Diverses classifications ont été proposées dans la littérature. Elles sont issues de deux
domaines différents. La classification non supervisée (ou clustering) de données et le
partitionnement de graphes.
83
Chapitre 3 Approches non génératives pour l’ISC
K
J K −moy = ∑ ∑ d (x ,c ) i k (3.7)
k =1 i:i∈Gk
{
G j ( 0 ) ← vi ∈ V | d ( a.i , c j ) = min d ( a.i , cl )
l =1,…, l
}
3. Calculer les centroïdes c1 , … , c K des nouveaux groupes
1
cj ←
G j( )
0 ∑ (0)
a. m
vm ∈G j
7. t ← t +1
8. Si l’algorithme n’a pas convergé alors aller à l’étape 5
9. Retourner la partition P ( t )
fin
84
Chapitre 3 Approches non génératives pour l’ISC
- le lien moyen (average link) : la distance entre deux clusters X et Y est égale à la
moyenne des distances entre les objets de ces deux clusters i.e.
1
d avg ( X , Y ) =
X Y
∑
x∈X , y∈Y
d ( x, y ) (3.9)
- le lien maximum (complete link) : la distance entre deux clusters X et Y est égale à la
plus grande distance entre deux objets de ces deux clusters i.e.
d max ( X , Y ) = max d ( x, y ) (3.10)
x∈X , y∈Y
Méthode descendante
Méthode ascendante
85
Chapitre 3 Approches non génératives pour l’ISC
fin
86
Chapitre 3 Approches non génératives pour l’ISC
étudiées par les chercheurs dans le cadre du partitionnement de graphes [Aggarwal and Wang
10]. La matrice de Laplace L d’un graphe non-orienté G, représenté par sa matrice
d’adjacence A, est définie par :
d ( vi ) si i = j
lij = −1 si i ≠ j et aij = 1 (3.11)
0 sinon
où d ( vi ) est le degré du nœud vi. Donetti et Munoz montrent que la projection des objets sur
le nouvel espace permet de faire un "pré-regroupement" des nœuds similaires, ce qui permet
d’obtenir de meilleurs indices de proximité.
87
Chapitre 3 Approches non génératives pour l’ISC
fin
L’utilisation de la modularité comme fonction objectif à optimiser est une idée qui a été
explorée par plusieurs chercheurs. Le but étant de trouver parmi toutes les partitions possibles
celle qui possède la meilleure modularité. Newman [Newman 04] par exemple a proposé un
algorithme glouton d’optimisation de la modularité. Il s’agit d’un algorithme de classification
hiérarchique ascendante où à chaque itération, l’algorithme réalise la fusion des communautés
(ou clusters) qui permet d’augmenter le plus (ou de diminuer le moins) la modularité.
Pons et Latapy [Pons and Latapy 05][Pons 07] ont proposé un algorithme de
classification hiérarchique ascendante dans lequel le calcul des distances entre les nœuds (ou
objets) repose sur le principe de la marche aléatoire. Plus précisément, la distance entre deux
nœuds i et j est exprimée par la différence entre le comportement de deux marcheurs
aléatoires commençant respectivement aux nœuds i et j et effectuant une marche de longueur
fixe. Pour le calcul de proximité entre deux communautés, Pons et Latapy généralisent la
distance proposée pour les nœuds à des ensembles de nœuds (i.e. des communautés). Une
fonction de qualité basée sur la similarité des nœuds est utilisée à la fin pour le choix de la
meilleure partition (i.e. meilleure structure de communautés).
En se basant sur une nouvelle définition par émergence des communautés, Bennouas
[Bennouas 05] et Bouklit [Bouklit 06] ont proposé deux modèles (gravitationnel et
intentionnel) pour la détection de communautés dans les graphes du web. Leurs modèles
considèrent que les pages web (ou objets à regrouper) représentent des particules et que les
liens représentent des forces gravitationnelles. L’identification de communautés se fait de
89
Chapitre 3 Approches génératives pour l’ISC
L’utilisation des modèles génératifs pour l’ISC est un axe de recherche qui a été peu
exploré par rapport aux approches classiques telles que les méthodes hiérarchiques ou encore
celles basées sur la modularité de Newman. Il existe d’ailleurs de nombreux travaux de
synthèse sur les approches non génératives pour l’ISC (par exemple [Schaeffer 07], [Porter et
al. 09] ou [Fortunato 10]) contrairement aux approches génératives dont le domaine semble
moins bien cerné. C’est pourquoi nous avons essayé de regrouper dans cette partie de la thèse
les principaux modèles génératifs existants pour l’ISC. Nous avons également tenu à les
présenter de manière détaillée et homogène (pour la notation) afin de faciliter leur
compréhension. Pour chacun des modèles, nous décrivons son processus génératif, sa
représentation graphique ainsi que l’algorithme d’estimation de ses paramètres.
Avant de présenter les modèles génératifs existants pour l’ISC, nous décrivons d’abord
les principales notions nécessaires à la compréhension de ce type de modèles. Le lecteur
familier avec la théorie des probabilités et les modèles génératifs pourra cependant passer
directement à la section 3.3.2. Nous invitons par ailleurs le lecteur souhaitant approfondir ses
connaissances sur les modèles génératifs à consulter l’excellent ouvrage de référence de
Christopher Bishop [Bishop 07].
Un modèle génératif suppose que les données observées (images, textes, graphes, etc.)
sont le produit ou le résultat d’un processus aléatoire [Bishop 07]. Un modèle génératif est
composé de deux parties. La première partie est un modèle probabiliste qui se présente sous la
forme d’une distribution paramétrique décrivant le processus par lequel ont été générées les
données. Cette modélisation consiste à utiliser des variables aléatoires et à définir des liens de
dépendance entre ces variables. Les liens entre variables, appelés aussi liens de causalité,
traduisent les hypothèses sur lesquelles est basé le modèle. Une représentation graphique du
modèle est souvent utilisée pour faciliter sa lecture et sa compréhension ; on parle aussi dans
ce cas de modèle graphique. Quant à la deuxième partie, elle correspond à une méthode
d’estimation qui calcule les valeurs optimales des paramètres du modèle. Une telle méthode
permet d’apprendre de manière automatique les paramètres du modèle à partir des données.
Afin d’illustrer le principe des modèles génératifs, nous allons utiliser deux modèles
jouets M1 et M2. Nous supposons que l’ensemble des données observées
D = { x1 ,… , x& } correspond à un ensemble de & nombres entiers compris entre 1 et M.
90
Chapitre 3 Approches génératives pour l’ISC
Dans le modèle M1, les nombres observés sont supposés être générés par une seule
distribution multinomiale. Cette dernière est généralement utilisée pour modéliser des
variables à valeurs discrètes. Pour notre exemple, le nombre de valeurs possibles étant égal à
M, la distribution multinomiale peut être vue comme un dé à M faces tel que la probabilité de
chaque face est donnée par un paramètre de la distribution. Le modèle M1 suppose donc que
l’ensemble D est le résultat de & tirages indépendants selon une loi multinomiale i.e.
X ~ Mult ( & , (π 1 ,… , π M ) ) où π est un vecteur de paramètres tel que ∑
M
m =1
π m = 1.
La figure 3.7a est une représentation graphique du modèle M1 dans laquelle les variables
aléatoires sont représentées par des cercles (appelés aussi des nœuds) et les paramètres du
modèle par des points. La figure 3.7b est une représentation plus compacte du modèle M1 où
les & variables X1,.., X& sont représentées par un rectangle contenant un seul nœud X ainsi
qu’une inscription du nombre & au bas de ce rectangle.
π π
X1 … X& X
&
(a) (b)
Figure 3.7 - (a) Représentations graphique standard du modèle M1 ; (b) Représentation
graphique compacte du modèle M1
p ( X = m ;π ) = π m (3.13)
Le modèle M1 est basé sur l’hypothèse que les nombres {xi} sont indépendants les uns
des autres. La probabilité de l’ensemble des données observées D, appelée aussi
vraisemblance des données, est alors :
p ( D ; π ) = p ( x1 , …, x& ; π )
= Mult ( X ; M , π )
M
&!
∏ p ( X = m ;π ) m
&
= (3.14)
∏ m=1 & m ! m=1
M
M
&!
= ∏ π m&m
∏ m=1 & m ! m=1
M
91
Chapitre 3 Approches génératives pour l’ISC
92
Chapitre 3 Approches génératives pour l’ISC
π µ
Z X
&
a été généré par K distributions multinomiales différentes, c’est-à-dire que chaque nombre a
été généré par un dé parmi K. Le processus génératif du modèle M2 est donc :
Pour n = 1,… , &
1. Choisir un dé Z n ~ Mult (1, (π 1 ,… , π K ) ) où π est un vecteur de paramètres tel que
∑ k =1π k = 1.
K
(
2. Conditionnellement à Zn, tirer un nombre xn ~ Mult 1, ( µ1Zn ,… , µ MZn ) où µ est )
une matrice de paramètres de dimension K × M telle que ∀k ∈ {1,… , K } , ∑ m =1 µ mk = 1 .
M
{
Θ = (π k )k =1,…, K , ( µmk )m=1,…, M
k =1,…, K
}
La représentation graphique de ce modèle est donnée par la figure 3.8. Les variables {Zn}
sont représentées par des cercles/nœuds grisés pour indiquer qu’il s’agit de variables non
observables (ou cachées) ; le dé ayant servi à générer un nombre donné est une information
inconnue. Ce modèle est basé sur les hypothèses suivantes :
i) La distribution jointe d’un nombre xi et du dé zi qui a servi a son tirage :
p ( X = xi , Z = zi ; Θ ) = p ( Z = zi ; Θ ) p ( X = xi | Z = zi ; Θ )
(3.19)
= π zi µ xi zi
ii) Les nombres observés { xi } sont tirés de manière indépendante les uns des autres, d’où
une vraisemblance de l’ensemble D égale à :
L = p ( ( x1 ,… , x& ) ; Θ )
&
= ∏ p ( X = xi ; Θ )
i =1
M
= ∏ p ( X = m ; Θ)
&m
(3.20)
m =1
&m
M
K
= ∏ ∑ p ( X = m, Z = k ; Θ )
m =1 k =1
&m
M
K
= ∏ ∑ π k µmk
m =1 k =1
93
Chapitre 3 Approches génératives pour l’ISC
où &m est le nombre de fois que l’entier m a été observé. Le passage de la ligne 3 à la ligne 4
dans 1.11 a été fait en utilisant la règle de la somme. Celle-ci indique que [Bishop 07] :
∑ p ( A, B ) si B est une variable discrète
p ( A) = B
∫ p ( A, B ) dB si B est une variable continue
Pour le passage de la ligne 4 à la ligne 5, nous avons utilisé la formule 1.10.
La log-vraisemblance des données est alors égale à :
M
K
LL = ∑ & m log ∑ (π k µ mk ) (3.21)
m =1 k =1
Cette log-vraisemblance possède une forme plus complexe que celle associée au modèle
M1. Il n’est en effet pas possible de l’optimiser car le log est "bloqué" par la somme et ne peut
simplifier sa forme. Cela nous donne une expression de la log-vraisemblance qui ne peut
généralement pas être optimisée de manière analytique [McLachan and Krishnan 97]. Pour
résoudre ce problème, Dempster et al. [Dempster et al. 77] ont proposé l’algorithme EM
(Expectation Maximization) permettant d’estimer les paramètres d’un modèle contenant des
variables cachées. Cet algorithme est basé sur la décomposition suivante de la log-
vraisemblance des données observées [Bishop 07] :
log p ( D ; Θ ) = LB ( q (.) ; Θ ) + KL ( q (.) || p (. | D ; Θ ) ) (3.22)
où
p ( D, Z ; Θ )
LB ( q (.) ; Θ ) = ∑ q ( Z ) log
Z q(Z )
et
p ( Z | D ; Θ)
KL ( q (.) || p (. | D ; Θ ) ) = −∑ q ( Z ) log
Z q(Z )
KL ( q || p ) est appelée la divergence de Kullback-Leibler. C’est une distance entre deux
distributions de probabilité : sa valeur est comprise entre 0 et 1 et est égale à 0 lorsque q = p .
LB est une borne inférieure à la log-vraisemblance qui égale cette dernière lorsque
KL ( q || p ) = 0 . Intuitivement, il suffit de choisir la distribution q ( Z ) tel que :
q ( Z ) = p ( Z | D ; Θ) (3.23)
94
Chapitre 3 Approches génératives pour l’ISC
( ( ) )
LB p Z | D ; Θold ; Θ = ∑ p ( Z | D ; Θ ) log p ( D, Z ; Θ ) + cst
Z
= E Z log p ( D, Z ; Θ ) + cst
qui est plus simple à optimiser que la log-vraisemblance. EZ désigne l’espérance par rapport
aux variables cachées {Z i } conditionnellement aux données observées. La distribution
p ( D, Z ; Θ ) est appelée vraisemblance des données complètes (i.e. celle des données
observées et des valeurs des variables cachées) par opposition à la distribution p ( D ; Θ ) qui
est appelée vraisemblance des données incomplètes (i.e. celle des données observées
uniquement). L’algorithme EM consiste à initialiser les paramètres du modèle par des valeurs
initiales puis à appliquer de manière itérative les deux étapes suivantes : (i) l’étape E
(Expectation), dans laquelle il calcule une borne inférieure à la log-vraisemblance qui est
égale à l’espérance de la log-vraisemblance des données complètes (d’où le nom de cette
étape) ; (ii) l’étape M (Maximization), dans laquelle la borne inférieure est maximisée pour
trouver les valeurs des paramètres qui maximisent la log-vraisemblance [McLachan and
Krishnan 97]. L’arrêt de l’algorithme peut se faire par exemple lorsque l’augmentation de log-
vraisemblance entre deux itérations consécutives est inférieure à un certain seuil ou bien
lorsqu’un nombre d’itérations maximal est atteint. Notons également que le maximum calculé
par l’algorithme EM est un maximum local et non pas global. La qualité de la solution
trouvée par l’algorithme dépend en effet des valeurs initiales des paramètres du modèle.
En revenant à l’exemple du modèle M2 et en supposant que l’on connaît le dé qui a servi
au tirage de chacun des nombres xi, la log-vraisemblance des données complètes est :
LLC = log ( D, Z ; Θ )
&
= ∑ log p ( X = xn , Z = zn ; Θ )
n =1
& (3.24)
= ∑ 1{xn =m , zn = k} log p ( X = m, Z = k ; Θ )
n =1
& M K
= ∑∑∑ 1{xn =m , zn = k} log (π k µmk )
n =1 m =1 k =1
1 si F est vrai ;
1F =
0 sinon
En supposant que les paramètres du modèle sont connus et fixés à des valeurs Θold, la
distribution a posteriori des variables cachées p ( Z | D ; Θold ) est obtenue en appliquant la
formule de Bayes :
95
Chapitre 3 Approches génératives pour l’ISC
(
p D, Z ; Θold )
(
p Z | D ;Θ old
)=
(
p D ; Θold )
=
∏
&
i =1 (
p X = xi , Z = zi ; Θold )
∏
&
i =1 (
p X = xi ; Θ old
) (3.25)
=∏
&
(
p X = xi , Z = zi ; Θ old
)
i =1 (
p X = xi ; Θ old
)
&
(
= ∏ p Z = zi | X = xi ; Θold )
i =1
Nous remarquons que la distribution jointe a posteriori des variables cachées peut être
factorisée en un produit des probabilités a posteriori de chaque variable cachée. Cela indique
que les variables Zi sont indépendantes les unes des autres conditionnellement aux données
observées. Pour k = 1,… , K , m = 1,… , M , cette distribution est alors donnée par :
ωkm = p ( Z = k | X = m ; Θold )
=
(
p X = m, Z = k ; Θold ) (3.26)
(
p X = m ;Θ old
)
π kold µmk
old
=
∑
K
t =1
π told µ mtold
Q = E Z LLC
& M K
= E Z ∑∑∑ 1{xn =m , zn =k } log (π k µmk )
n =1 m =1 k =1
& M K
= ∑∑∑ 1{xn =m} E Zn 1{zn =k } log (π k µmk )
n =1 m =1 k =1
& M K (3.27)
(
= ∑∑∑ 1{xn = m} p Z n = k | X n = m ; Θold log (π k µmk ) )
n =1 m =1 k =1
& M K
= ∑∑∑ 1{xn =m} ωkm log (π k µ mk )
n =1 m =1 k =1
M K
= ∑∑ & mωkm log (π k µ mk )
m =1 k =1
où &m est le nombre d’occurrences de l’entier m (i.e. le nombre de fois qu’il a été observé). Le
passage de la ligne 3 à la ligne 4 dans 1.18 a été fait en utilisant la propriété que l’espérance
de la fonction indicatrice 1F est égale à la probabilité de F (cf. définition de la fonction
indicatrice).
96
Chapitre 3 Approches génératives pour l’ISC
M K
K
M K
H = ∑∑ & mωkm log (π k µ mk ) + λ 1 − ∑ π k + ∑ σ m 1 − ∑ µ km (3.28)
m =1 k =1 k =1 m =1 k =1
& mωkm
µkm
new
= (3.30)
∑ t =1 &mωtm
K
Comme nous allons le voir dans la suite, il existe parfois des cas où la distribution a
postériori des variables cachées p ( Z | D ; Θ ) ne peut être calculée. Cela arrive en général
lorsque les variables Zi ne sont pas indépendantes les unes des autres. Dans ce cas, il devient
alors nécessaire de recourir à des techniques qui permettent de calculer une distribution
approchée de la distribution a posteriori. Il existe deux familles de méthodes pour arriver à
cette fin [Bishop 07]: les méthodes stochastiques et les méthodes déterministes. Pour la
première famille, la méthode la plus connue est celle de Monté-Carlo qui consiste à faire de
l’échantillonnage. Concernant la deuxième famille, l’inférence variationnelle est sans doute la
méthode la plus emblématique. Nous l’utiliserons dans la suite de cette thèse. L’inférence
variationnelle part de la décomposition de la log-vraisemblance en deux termes : une borne
inférieure et une divergence de Kullback-Leibler. Le principe de l’inférence variationnelle est
de chercher une distribution paramétrique q(Z) qui soit une bonne approximation de la
distribution a posteriori p(Z|D). L’inférence variationnelle suppose alors que la distribution
q(Z) peut être factorisée de telle sorte que :
&
q ( Z ) = ∏ q ( Zi ) (3.31)
i =1
97
Chapitre 3 Approches génératives pour l’ISC
Newman et Leicht [Newman and Leicht 07] ont récemment proposé un modèle
probabiliste pour l’identification de structures de communautés. Il s’agit d’un modèle
similaire au modèle de mélange de multinomiales (multinomial mixture model) utilisé par
Nigam et al. [Nigam et al. 00] dans le cadre d’une application de classification supervisée de
textes. En raison de sa simplicité et de ses bonnes performances, le modèle de mélange de
multinomiales a reçu beaucoup d’attention de la part des chercheurs dans le domaine de la
fouille de textes. A titre d’exemple, la thèse de Rigouste [Rigouste 06] est consacrée à l’étude
de ce modèle dans un contexte de classification non supervisée (ou clustering) de données
textuelles.
Le modèle de Mélange de Newman et Leicht (MNL) est un modèle génératif de graphes
qui considère qu’un sommet comme est un ensemble de liens (vers d’autres sommets), et que
cet ensemble de liens est déterminé par la communauté à laquelle appartient ce sommet. Le
modèle MNL suppose ainsi que les & sommets d’un graphe G représenté par sa matrice
d’adjacence A sont générés par le processus suivant :
3. Pour j = 1… & n , générer un lien entre le nœud courant (i.e. le nœud i) et le nœud snj.
Θ = (π k )k =1,…, K , ( µ jk ) j =1,…, &
k =1,…, K
La figure 3.9 indique la représentation graphique du modèle MNL. Ce modèle est basé
sur les hypothèses suivantes :
98
Chapitre 3 Approches génératives pour l’ISC
α β
C S
&L
&
p ( si | C = ci ; Θ ) = p ( si1 , …, si&i | C = ci ; Θ )
(
= Mult S ; & i , µ.ci )
&i
∏ p(S = s )
&i !
= | C = ci ; µ.ci (3.33)
∏ j =1 Aij
&i ij
j =1
&
∏ p(S = j | C = c )
&i ! Aij
= ; µ.ci
∏
&i i
j =1
Aij j =1
&
= & i !∏ µ jci
Aij
j =1
j =1
iii) Les sommets observés {si } sont indépendants les uns des autres, d’où une log-
vraisemblance du graphe observé égale à :
LL = log p ( ( s1 ,… , s& ) ; Θ )
&
= ∑ log p ( si ; Θ )
i =1
& K
(3.35)
= ∑ log ∑ p ( si , C = k ; Θ )
i =1 k =1
& K &i
A
= ∑ log ∑ π k ∏ µ jk ij + cst
i =1 k =1 j =1
99
Chapitre 3 Approches génératives pour l’ISC
ωki = p ( C = k | S = i ; Θold )
=
(
p S = i, C = k ; Θold ) (3.37)
) (
p S = i ;Θ old
π ∏ (µ )
& Aij
old old
k j =1 jk
=
∑ π ∏ (µ )
K old & old Aij
t =1 t j =1 jt
& K &
Q = EC ∑∑ 1{ci = k} log π k + ∑ Aij logµ jk
i =1 k =1 j =1
& K &
= ∑∑ ECi 1{ci = k} log π k + ∑ Aij logµ jk
i =1 k =1 j =1 (3.38)
& K &
(
= ∑∑ p C = k | S = i ; Θold ) log π k + ∑ Aij logµ jk
i =1 k =1 j =1
& K &
= ∑∑ ωki log π k + ∑ Aij logµ jk
i =1 k =1 j =1
Si l’on suppose maintenant que la distribution a posteriori des communautés est connue,
les paramètres π et µ qui maximisent Q à chaque itération de l’algorithme EM sont obtenus en
maximisant le lagrangien suivant :
& K & K
K &
H = ∑∑ ωki log π k + ∑ Aij log µ jk + λ 1 − ∑ π k + ∑ σ k 1 − ∑ µ jk (3.39)
i =1 k =1 j =1 k =1 k =1 j =1
100
Chapitre 3 Approches génératives pour l’ISC
∑ π k = 1 et ∀k ∈ {1, … , K } , ∑ j =1 µ jk = 1 .
K &
k =1
&
πk = 1
&∑
ω ki (3.40)
i =1
Cette expression signifie que la probabilité a priori d’une communauté k est proportionnelle
au nombre de nœuds appartenant à cette communauté.
∑ Aω
&
µ jk
ij ki
= i =1
(3.41)
∑ ∑ Aω
& &
i =1 j =1 ij ki
Les différentes étapes d’estimation des paramètres du modèle MNL sont décrites par
l’algorithme 3.5.
101
Chapitre 3 Approches génératives pour l’ISC
4. ωki ←
∑ t =1 t ∏ j =1 ( jt )
K & Aij
π µ
5. fin
// Etape M de l’algorithme
6. pour k = 1… K faire
&
7. πk ← 1 ∑ω ki
& i =1
∑ Aω
&
µ jk
ij ki
9. ← i =1
∑ ∑ Aω
& &
i =1 j =1 ij ki
10. fin
11. fin
12. jusqu’à convergence
fin
3.3.3 Approches basées sur le modèle PLSA (Probabilistic Latent Semantic Analysis)
PLSA est un modèle probabiliste proposé par Hofmann [Hofmann 01] pour l’analyse de
données de co-occurrence. Bien qu’utilisé initialement pour la classification non supervisée
de textes, le modèle PLSA a trouvé de nombreuses autres applications telles que la recherche
d’information [Hofmann 99] ou les systèmes de recommandation [Popescul et al. 01]. PLSA a
été employé notamment pour l’identification de structures de communautés dans les graphes ;
il est en effet à la base de deux modèles d’ISC à savoir PHITS et SPAEM. Nous présentons
ci-dessous chacun de ces deux modèles.
102
Chapitre 3 Approches génératives pour l’ISC
Dans [Cohn and Chang 00], les auteurs présentent le modèle PHITS comme une
alternative à l’algorithme HITS (cf. chapitre 1) pour le calcul de centralité dans les graphes de
documents. Ils montrent que leur modèle est capable de trouver des ensembles d’autorités et
de hubs qui peuvent être interprétés "plus facilement" que ceux calculés par l’algorithme
HITS. PHITS calcule les ensembles d’autorités et de hubs en commençant d’abord par
identifier la structure de communautés contenue dans le graphe de documents, puis en se
basant sur cette structure, il attribue à chaque document des degrés d’autorité et d’hubité.
PHITS est toutefois un modèle très peu connu dans le domaine de l’identification de
structures de communautés. Nous pensons que cela est dû au fait qu’il soit présenté dans un
contexte de calcul de centralité et non pas d’identification de communautés.
Il existe deux versions différentes du modèle PLSA : une version symétrique et une
version asymétrique. PHITS est un modèle génératif de graphes basé sur la version
asymétrique de PLSA. A la différence du modèle MNL qui est un modèle génératif des
sommets, PHITS est plutôt un modèle génératif des liens entre sommets. Le modèle PHITS
suppose que les M liens d’un graphe G d’ordre & représenté par sa matrice d’adjacence A
sont générés par le processus suivant :
- Pour m = 1 à M faire :
1. Choisir un nœud source xm ∼ Mult (1,(π 1 ,… , π & ) ) où π est un vecteur de paramètres
&
tel que ∑π
i =1
i = 1.
(
2. Conditionnellement à xm, choisir une communauté cm ∼ Mult 1, ( µ1xm ,… , µ Kxm ) où µ )
K
est une matrice de paramètres de dimension K × & telle que ∀i ∈ {1,… , & } , ∑ µ ki = 1 .
k =1
La figure 3.10 indique la représentation graphique du modèle PHITS. Ce modèle est basé
sur les hypothèses suivantes :
103
Chapitre 3 Approches génératives pour l’ISC
p ( X = xm , Y = ym , C = cm ; Θ ) = p ( X = xm ; Θ ) p ( C = cm | X = xm ; Θ )
p (Y = ym | C = cm ; Θ ) (3.42)
= π xm µcm xm φ ym cm
ii) Les liens observés {( x m , ym )} sont indépendants les uns des autres. La log-
vraisemblance du graphe observé est donc :
LL = log p ( ( x1 , y1 ) ,… , ( xM , yM ) ; Θ )
M
= ∑ log p ( X = xm , Y = ym ; Θ )
m =1
M K (3.43)
= ∑ log ∑ p ( X = xm , Y = ym , C = k ; Θ )
m =1 k =1
M K
= ∑ log ∑ π xm µkxm φ ym k
m =1 k =1
( )
La quantité LL ne pouvant être maximisée directement en raison de la présence de
variables latentes, il est nécessaire de recourir à l’algorithme EM pour l’estimation des
paramètres de ce modèle.
(
LLC = log p ( ( x1 , y1 , c1 ) ,… , ( xM , yM , cM ) ; Θ ) )
M
= ∑ log p ( X = xm , Y = ym , C = cm ; Θ ) (3.44)
m =1
M & & K
= ∑∑∑∑ 1{xm =i , ym = j ,cm = k} ( log π i + log µki + log φ jk )
m =1 i =1 j =1 k =1
π µ φ
X C Y
104
Chapitre 3 Approches génératives pour l’ISC
ωkij = p ( C = k | X = i, Y = j ; Θold )
=
(
p X = i, Y = j , C = k ; Θold ) (3.45)
(
p X = i, Y = j ; Θ old
)
µkiold φ jkold
=
∑
K
t =1
µtiold φ jtold
M & & K
Q = EC ∑∑∑∑ 1{ xm =i , ym = j ,cm = k } ( log π i + log µ ki + log φ jk )
m =1 i =1 j =1 k =1
M & & K
= ∑∑∑∑ 1{ xm =i , ym = j} ECm 1{cm = k } ( log π i + log µ ki + log φ jk ) (3.46)
m =1 i =1 j =1 k =1
& & & & K
= ∑∑ Aij log π i + ∑∑∑ Aijωkij ( log µ ki + log φ jk )
i =1 j =1 i =1 j =1 k =1
Les nouveaux paramètres Θ qui maximisent cette espérance sont obtenus en maximisant
le lagrangien suivant :
& & & & K
&
H = ∑∑ Aij log π i + ∑∑ Aij ∑ ωkij ( log µki + log φ jk ) + λ 1 − ∑ π i
i =1 j =1 i =1 j =1 k =1 i =1
(3.47)
&
K
K &
+ ∑ σ i 1 − ∑ µki + ∑ ζ k 1 − ∑ φ jk
i =1 k =1 k =1 j =1
Cela signifie que la probabilité a priori d’un nœud i est proportionnelle au nombre de liens
sortants que possède ce nœud.
Les équations de ré-estimation de µki et φ jk sont obtenues en résolvant respectivement les
équations ∂H = 0 et ∂H = 0 :
∂µ ki ∂φ jk
∑
&
j =1 ij
A ωkij
µki = (3.49)
∑
&
A
j =1 ij
105
Chapitre 3 Approches génératives pour l’ISC
∑ Aω
&
φ jk i =1 ij kij
= (3.50)
∑ ∑ Aω
& &
i =1 t =1 ij kit
L’algorithme EM complet pour l’estimation des paramètres du modèle PHITS est décrit
par l’algorithme 3.6.
∑ Aω
&
φik l =1 li kli
11. =
∑ ∑ Aω
& &
l =1 t =1 li klt
12. fin
13. jusqu’à convergence
fin
106
Chapitre 3 Approches génératives pour l’ISC
En se basant sur la version symétrique du modèle PLSA, Ren et al. [Ren et al. 09] ont
proposé récemment le modèle SPAEM pour l’identification de structures de communautés
dans les graphes non-orientés. Le modèle SPAEM suppose que les M arêtes d’un graphe G
d’ordre & représenté par sa matrice d’adjacence A sont générées par le processus suivant :
- Pour m = 1 à M faire :
1. Choisir une communauté cm ~ Mult (1, (π 1 ,… , π K ) ) où π est un vecteur de paramètres
K
tel que ∑π
k =1
k = 1.
(
2. Conditionnellement à cm, choisir un nœud xm ~ Mult 1, ( µ1cm ,… , µ &cm ) où µ est une )
&
matrice de paramètres de dimension & × K telle que ∀k ∈ {1,… , K } , ∑ µik = 1 .
i =1
{
Θ = (π k )k =1,…, K , ( µik )i =1,…, &
k =1,…, K
}
La représentation graphique du modèle SPAEM est indiquée par la figure 3.11. Ce
modèle est basé sur les hypothèses suivantes :
i) La distribution jointe d’une arête {( xm , ym )} et de sa communauté cm est :
p ( X = xm , Y = ym , C = cm ; Θ ) = p ( C = cm ; Θ ) p ( X = xm | C = cm ; Θ ) p (Y = ym | C = cm ; Θ )
(3.51)
= π cm µ xmcm µ ymcm
ii) Les arêtes observées {( x m , ym )} sont indépendantes les unes des autres. La log-
vraisemblance du graphe observé est donc :
LL = log p ( ( x1 , y1 ) ,… , ( xM , yM ) ; Θ )
M
= ∑ log p ( X = xm , Y = ym ; Θ )
m =1
M K (3.52)
= ∑ log ∑ p ( X = xm , Y = ym , C = k ; Θ )
m =1 k =1
M K
(
= ∑ log ∑ π k µ xm k µ ym k
m =1 k =1
)
107
Chapitre 3 Approches génératives pour l’ISC
X C Y
Comme pour l’algorithme PHITS, l’estimation des paramètres du modèle SPAEM doit
être réalisée en utilisant l’algorithme EM. La log-vraisemblance des données complètes est :
LLC = log p ( ( x1 , y1 , c1 ) ,… , ( xM , yM , cM ) ; Θ )
M
= ∑ log p ( X = xm , Y = ym , C = cm ; Θ )
m =1
M & & K (3.53)
= ∑∑ ∑ ∑ 1{ xm =i , ym = j ,cm = k }
log p ( X = i, Y = j , C = k ; Θ )
m =1 i =1 j =i +1 k =1
M & & K
= ∑∑ ∑ ∑ 1{ xm =i , ym = j ,cm = k } ( log π k + log µik + log µ jk )
m =1 i =1 j =i +1 k =1
La distribution a posteriori des variables latentes (i.e. des communautés) est obtenue en
appliquant la formule de Bayes. Pour i = 1… & , j = 1… & , k = 1… K , cette distribution est
donnée par :
ωkij = p ( C = k | X = i, Y = j ; Θold )
=
(
p X = i, Y = j , C = k ; Θold ) (3.54)
(
p X = i, Y = j ; Θold )
π k µik µ jk
=
∑
K
t =1
π t µit µ jt
108
Chapitre 3 Approches génératives pour l’ISC
M & & K
Q = EC ∑∑ ∑ ∑ 1{xm =i , ym = j ,cm = k } ( log π k + log µik + log µ jk )
m =1 i =1 j =i +1 k =1
M & & K
= ∑∑ ∑ ∑ 1{ ECm 1{cm = k } ( log π k + log µik + log µ jk )
m =1 i =1 j = i +1 k =1
xm = i , ym = j}
(3.55)
M & & K
= ∑∑ ∑ ∑ 1{ xm = i , ym = j} (
p C = k | X = i, Y = j ; Θold ) ( log π k + log µik + log µ jk )
m =1 i =1 j = i +1 k =1
& & K
=∑ ∑ ∑ A ω ( log π
i =1 j =i +1 k =1
ij kij k + log µik + log µ jk )
La somme sur la variable j commence par la valeur i+1 pour ne pas que les liens soient
considérés deux fois ; la matrice d’adjacence A étant symétrique, nous avons : Aij = Aji . De
plus la variable j commence par la valeur i + 1 et non pas i car le modèle suppose que le
graphe observé ne contient pas de boucles.
Le lagrangien à maximiser pour obtenir nouvelles valeurs des paramètres Θ est :
& & K
H =∑ ∑ ∑ A ω ( log π
i =1 j = i +1 k =1
ij kij k + log µik + log µ jk )
(3.56)
K
K &
+ λ 1 − ∑ π i + ∑ σ k 1 − ∑ µik
k =1 k =1 i =1
Cela signifie que la probabilité a priori d’une communauté k est proportionnelle au nombre de
nœuds appartenant à cette communauté.
∑
&
j = i +1
Aijωkij
µik = (3.58)
∑ ∑
& &
l =1
Aω
j =l +1 ij klj
L’algorithme 3.7 décrit les différentes étapes d’estimation des paramètres du modèle
SPAEM.
109
Chapitre 3 Approches génératives pour l’ISC
Les SBM sont les modèles génératifs les plus connus dans le domaine de l’identification
de structures de communautés dans les réseaux sociaux. Ils ont été introduits comme une
extension des modèles en blocs (Block Models) classiques [Anderson et al. 92][Wasserman
and Faust 94]. Ces derniers ont pour but d’identifier dans un réseau social les groupes
d’acteurs possédant les mêmes caractéristiques. Ils sont basés sur le principe de l’équivalence
structurelle entre deux acteurs : deux acteurs i et j sont dits structurellement équivalents si et
seulement si ils ont le même voisinage immédiat i.e. ils interagissent avec les mêmes acteurs.
Cette définition de l’équivalence entre deux acteurs est assez contraignante puisqu’il suffit
qu’il y ait une seule différence entre les connexions des nœuds pour que les deux nœuds ne
soient plus équivalents. Or, en pratique, deux nœuds peuvent être équivalents sans avoir
exactement les mêmes liens. Pour prendre en compte cette idée, Holland et al. ont proposé la
110
Chapitre 3 Approches génératives pour l’ISC
notion d’équivalence stochastique qui suppose que deux nœuds peuvent être équivalents
même s’ils n’ont pas exactement les mêmes liens. Il s’agit en fait d’une équivalence beaucoup
plus souple et qui peut par conséquent être utilisée avec des réseaux réels.
Novicky et Snijders [Nowicki and Snijders 01] ont proposé un SBM général permettant
d’identifier des communautés dans différents types de graphes (orientés/non-orientés,
signés/non-signés, graphes simples/multigraphes). Nous présentons ici une version de ce
SBM pour des graphes simples, orientés et sans boucles.
Le modèle SBM suppose que les liens d’un graphe G d’ordre & représenté par sa matrice
d’adjacence A sont générés par le processus suivant :
1. Pour chaque sommet i, i = 1,… , & faire :
i. Choisir une communauté ci ~ Mult (1, (π 1 ,… , π K ) ) où π est un vecteur de paramètres
K
tel que ∑π
k =1
k = 1.
i. Conditionnellement à ci et cj, tirer une relation rij ~ Bern rij ; µci c j ( ) où µ est une
matrice de paramètres de dimension K × K , appelée aussi matrice des blocs.
ii. Si rij = 1 alors générer un lien entre le nœud i et le nœud j.
La figure 3.12 indique la représentation graphique du modèle SBM. Ce modèle est basé
sur les hypothèses suivantes :
π
Ci Cj
µ Rij
( i, j ) ∈ {1,… , & }
2
111
Chapitre 3 Approches génératives pour l’ISC
i) Les communautés {ci } des sommets sont indépendantes les unes des autres i.e.
p ( C ; Θ ) = p ( ( c1 ,… , c& ) ; Θ )
&
= ∏ p ( C = ci ; Θ ) (3.59)
i =1
&
= ∏ π ci
i =1
ii) Les relations (présence ou absence de lien) {rij } entre les nœuds sont indépendantes
les unes des autres lorsque la communauté de chaque nœud est connue i.e.
(3.60)
( )
& &
= ∏∏ Bern Aij ; µci c j
i =1 j ≠i
( )
& & 1− Aij
= ∏∏ µci c j 1 − µci c j
Aij
i =1 j ≠i
Cette quantité ne peut être calculée ou maximisée analytiquement car elle contient une
somme de K& éléments. De plus, l’algorithme EM ne peut pas être utilisé ici car la distribution
a posteriori des variables cachées (i.e. des communautés) ne peut non plus être calculée. En
effet, celle-ci est donnée par :
P ( C | R ; Θ ) = P ( C1 ,… , C& | R ; Θ )
et ne peut être factorisée en un produit de distributions indépendantes comme c’est le cas pour
les modèles MNL et PLSA. Cela est dû au fait que les variables cachées {Ci} ne sont plus
indépendantes lorsque les variables {Rij} sont observées. Si l’on considère par exemple le cas
d’une relation Rij et de deux variables cachées Ci et Cj, la probabilité a postériori des variables
Ci et Cj est :
112
Chapitre 3 Approches génératives pour l’ISC
P ( Ci , C j , Rij )
P ( Ci , C j | Rij ) =
P ( Rij )
P ( Ci ) P ( C j ) P ( Rij | Ci , C j )
=
P ( Rij )
≠ P ( Ci | Rij ) P ( C j | Rij )
Cela revient à faire l’hypothèse que les variables {Ci} sont indépendantes. Une fois la
forme de la distribution q choisie, l’étape suivante est de déterminer les paramètres de
chacune des distributions q(Ci). D’après la théorie de l’inférence variationnelle, nous avons
[Bishop 07] :
i =1 j ≠i k =1 l =1
i j
i =1 k =1
( )
& K K K
= 2 × ∑∑∑ 1{ci = k} EC j 1{c =l} log µklij (1 − µkl ) ij + ∑ 1{ci = k} log π k + cst
A 1− A
j ≠ i k =1 l =1
j
k =1
( )
K & K
= ∑ 1{ci =k } 2 × ∑∑ ω jl log µklij (1 − µkl ) ij + log π k + cst
A 1− A
k =1 j ≠ i l =1
( ) + log π
& K
log ωik = 2 × ∑∑ ω jl log µ klij (1 − µkl )
A 1− Aij
k (3.64)
j ≠ i l =1
113
Chapitre 3 Approches génératives pour l’ISC
on obtient :
K
q ( Ci ) ∝ ∏ ωik
1{c =k}
i
(3.65)
k =1
( )
& K 2×ω jl
(1 − µkl )( )
1− Aij
ωik ∝ π k ∏∏ µkl
Aij
(3.66)
j ≠ i l =1
∑ ∑
& &
i =1 j =1
ωik ω jl Rij
µkl = (3.68)
∑ ∑
& &
i =1
ω ω
j =1 ik jl
L’algorithme d’estimation des paramètres du modèle SBM est donné par l’algorithme
3.8.
Dans la littérature sur l’identification de communautés, il existe plusieurs variantes du
modèle SBM général que nous avons présenté dans cette section. Par exemple, Hastings
[Hastings 06] a proposé un SBM qui suppose l’existence de deux types de liens entre les
nœuds : soit des liens entre des nœuds de la même communauté, soit des liens entre des
nœuds appartenant à des communautés différentes. Concrètement, il s’agit d’un SBM pour
lequel la matrice des blocs π est telle que :
P in si i = j
π ij = out
P sinon
où P in , P out ∈ [ 0,1] sont des probabilités indiquant respectivement la probabilité d’un lien
entre deux nœuds de la même communauté et la probabilité d’un lien entre deux nœuds
appartenant à des communautés différentes. Ces deux probabilités ne sont toutefois pas
estimées par le modèle mais doivent plutôt être précisées par l’utilisateur.
Hofman et Wiggins [Hofman and Wiggins 08] ont proposé un modèle équivalent à celui
de Hastings sauf que les paramètres Pin et Pout sont estimés à partir des données. Latouche et
al. [Latouche et al. 10] ont proposé une version bayésienne du modèle SBM que nous avons
présenté ici. Pour l’estimation des paramètres de leur modèle bayésien, ils ont utilisé
l’inférence variationnelle.
114
Chapitre 3 Synthèse des différentes approches d’ISC
( )
& K 2×ω jl
(1− Rij )
5. ωik ← π k ∏∏ µ kl
Rij
(1 − µkl )
j ≠ i l =1
6. fin
ω i.
7. ωi . ←
ω i. 1
8. fin
// Etape M de l’algorithme
9. pour k = 1,… , K faire
&
πk = 1
&∑
10. ω ik
i =1
∑ ∑
& &
i =1 j =1
ωik ω jl Aij
12. µkl =
∑ ∑
& &
i =1 j =1
ωik ω jl
13. fin
14. fin
15. jusqu’à convergence
fin
Dans le premier chapitre de cette thèse, nous avons mis l’accent sur le fait que les
graphes de documents possèdent certaines caractéristiques qui rendent la tâche
d’identification de communautés plus complexe que pour d’autres types de graphes. Dans
cette section, nous étudions l’adéquation des différents algorithmes présentés pour
l’identification de communautés dans les graphes de documents. Plus précisément, nous
analysons chacune des approches présentées en utilisant les critères suivants :
115
Chapitre 3 Synthèse des différentes approches d’ISC
116
Chapitre 3 Synthèse des différentes approches d’ISC
Les tableaux 3.1 et 3.2 résument les propriétés des différents algorithmes d’ISC présentés
dans ce chapitre. Nous commentons ci-dessous les informations reportées sur ces deux
tableaux.
Le principal avantage de l’algorithme des K-moyennes est sa rapidité. Cependant, la
qualité de la structure de communautés qu’il identifie dépend des centroïdes initiaux. Un
"mauvais" choix de ces centroîdes conduit à une structure de communautés de faible qualité.
L’algorithme des K-moyennes peut identifier des communautés de tailles et de densités
différentes à condition que les communautés soient suffisamment séparées dans l’espace
métrique. En effet, les clusters (i.e. communautés) calculés par cet algorithme ont une forme
hyper-sphérique ce qui peut causer la fusion des clusters proches.
La complexité des algorithmes de Newman & Girvan et de Donetti & Munoz est
quadratique par rapport au nombre de liens pour le premier et par rapport au nombre de
sommets pour le deuxième. Leur utilisation est donc restreinte à des graphes de taille limitée.
Le fait que ces algorithmes soient basés sur la modularité de Newman les rend incapables
d’identifier des communautés dont la taille est inférieure à un certain seuil (cf. problème de la
modularité dans la section 3.1.3). Il est par ailleurs nécessaire de préciser pour l’algorithme de
Donetti et Munoz le nombre de vecteurs propres qui formeront l’espace de projection.
Propriété KM G% DM BS
Identification de communautés
oui non oui non
dans des graphes orientés
Identification de communautés
non non non non
qui se recouvrent
Nombre de
Dimension de
communautés Taille des
Connaissances a priori aucune l’espace de
et une mesure communautés
projection
de similarité
Complexité O ( IKM ) O(M 2& ) O(&3) O ( I& )
Déterministe non oui oui oui
Identification de communautés
de tailles et/ou de densités oui* oui* oui* non
différentes
Multi-vue sur la structure de
non non non non
communautés
117
Chapitre 3 Synthèse des différentes approches d’ISC
Identification de communautés
oui oui non oui
dans des graphes orientés
Identification de communautés
non* oui oui non*
qui se recouvrent
Nombre de Nombre de Nombre de Nombre de
Connaissances a priori
communautés communautés communautés* communautés*
Complexité O ( IKM ) O ( IKM ) O ( IKM ) O ( IK 2 & 2 )
Déterministe non non non non
Identification de communautés
de tailles et/ou de densités oui oui oui oui
différentes
Multi-vue sur la structure de
non oui non non
communautés
118
Chapitre 3 Synthèse des différentes approches d’ISC
En considérant les critères 1, 3 et 4 (que nous jugeons les plus importants), nous
remarquons que l’algorithme des K-moyennes et les deux modèles MNL et PHITS sont les
mieux adaptés à l’identification de communautés dans les graphes de documents. Le modèle
PHITS possède en plus l’avantage de prendre en compte le recouvrement des communautés.
En fait, la plupart des algorithmes d’ISC existants sont destinés à l’identification de
communautés disjointes dans des graphes non-orientés [Fortunato 10].
Finalement, nous montrons dans le chapitre 4 que les modèles MNL et PHITS sont sujets
à un problème important qui se manifeste par de très mauvaises performances lorsque la
densité du graphe à analyser est très faible, alors que l’algorithme des K-moyennes n’est pas
sensible à cette faible densité. Nous avons remarqué ce problème également avec les modèles
SPAEM et SBM lors de l’analyse de graphes non-orientés de très faible densité. Il s’agit d’un
problème qui concernerait apparemment toutes les approches génératives existantes.
Nous proposons dans le chapitre suivant deux nouveaux modèles génératifs pour
l’identification de communautés dans les graphes de documents. Nous proposons également
pour ces modèles des techniques pour pallier au problème de la faible densité, pour
déterminer de manière automatique le nombre de communautés et enfin des techniques
d’initialisation car cette étape est cruciale pour ces modèles.
119
Chapitre 4 Des modèles génératifs pour l’ISC dans les graphes de documents
Dans cette thèse, nous défendons l’idée que les modèles génératifs représentent une
solution très intéressante au problème de l’identification de structures de communautés. Nous
avons montré à la fin du chapitre précédent que ce type de modèles possède plusieurs
avantages tels que la capacité à analyser des graphes orientés ou encore la détection de
communautés qui se recouvrent. Cependant, en utilisant ces modèles pour l’ISC dans des
graphes de documents, nous avons trouvé que ces modèles donnent de mauvais résultats par
rapport à des méthodes classiques telles que l’algorithme des K-moyennes. Cette mauvaise
performance est en fait due à la faible densité en liens qui caractérise les graphes de
documents.
Dans ce chapitre, nous proposons le modèle SPCE pour l’identification de structures de
communautés dans des graphes orientés. Contrairement aux autres approches génératives,
SPCE est robuste à la faible densité des graphes de documents. Cette robustesse est obtenue
par l’utilisation de la technique du lissage ainsi que d’une initialisation adéquate de
l’algorithme d’estimation des paramètres du modèles SPCE. Dans le but de valider le modèle
SPCE, nous l’avons comparé à d’autres approches génératives et non génératives en utilisant
quatre graphes de documents. Les résultats expérimentaux montrent que le modèle SPCE
réalise les meilleures performances par rapport à toutes les autres approches étudiées. A la fin
du chapitre, nous proposons le modèle SPCE-PLSA pour l’identification de thématiques dans
les collections de documents. Il s’agit d’une extension du modèle SPCE permettant de prendre
en compte non seulement les liens entre documents mais aussi leurs contenus. Ce modèle est
également évalué expérimentalement en utilisant deux corpus de documents. Les résultats
obtenus montrent que le fait de combiner les liens et les contenus permet d’améliorer
120
Chapitre 4 Le modèle SPCE
Le processus génératif du modèle SPCE [Chikhi et al. 09][Chikhi et al. 10] est proche de
celui de PHITS (et donc de celui de PLSA) à ceci près qu’il utilise des priors (i.e. des
distributions a priori) sur les paramètres du modèle. Le but de ces priors est de lisser les
distributions des paramètres.
121
Chapitre 4 Le modèle SPCE
Nous noterons par Θ l’ensemble des paramètres (et hyper-paramètres) du modèle SPCE
i.e. :
Θ = (π i )i =1,…, & , ( µki )k =1,…, K , (φ jk ) j =1,…, & , α , β
i =1,…, & k =1,…, K
La figure 4.1 indique la représentation graphique du modèle SPCE. Ce modèle est basé
sur des hypothèses similaires à celles de PHITS i.e. :
p ( S = sm , D = d m , C = cm ; Θ ) = p ( S = sm ; Θ ) p ( C = cm | S = sm ; Θ )
p ( D = d m | C = cm ; Θ ) (4.1)
= π sm µcm sm φdm cm
ii) Les liens observés {( s m , d m )} sont indépendants les uns des autres. La log-
vraisemblance du graphe observé est donc :
LL = log p ( ( s1 , d1 ) ,… , ( sM , d M ) ; Θ )
M
= ∑ log p ( S = sm , D = d m ; Θ )
m =1
M K (4.2)
= ∑ log ∑ p ( S = sm , D = d m , C = k ; Θ )
m =1 k =1
M K
(
= ∑ log ∑ π sm µ ksm φdm k
m =1 k =1
)
122
Chapitre 4 Le modèle SPCE
π α β
µ φ
& K
S C D
Concernant les priors sur les paramètres, nous avons utilisé des distributions de Dirichlet
car celles-ci sont conjuguées à la loi multinomiale. Cela permet en fait de simplifier la
procédure d’estimation des paramètres du modèle SPCE. Plus précisément, en faisant un tel
choix, la distribution a posteriori des paramètres aura la même forme que la distribution a
priori. De plus, nous considérons que les distributions de Dirichlet utilisées sont symétriques
i.e. les valeurs de leur vecteur de paramètres sont toutes égales ( α1 = … = α K et β1 = … = β & ).
p ( µ , φ | ( s1 , d1 ) ,… , ( sM , d M ) ) α p ( ( s1 , d1 ) ,… , ( sM , d M ) ) p ( µ | α ) p (φ | β ) (4.3)
(
LLC = log p ( ( s1 , d1 , c1 ) ,… , ( sM , d M , cM ) ; Θ ) )
M
= ∑ log p ( S = sm , D = d m , C = cm ; Θ )
m =1
M & & K (4.4)
= ∑∑∑∑ 1{sm =i , dm = j ,cm = k} log p ( S = i, D = j , C = k ; Θ )
m =1 i =1 j =1 k =1
M & & K
= ∑∑∑∑ 1{sm =i , dm = j ,cm = k} ( log π i + log µ ki + log φ jk )
m =1 i =1 j =1 k =1
123
Chapitre 4 Le modèle SPCE
ωkij = p ( C = k | S = i, D = j ; Θold )
=
(
p S = i, D = j , C = k ; Θold ) (4.5)
(
p S = i, D = j ; Θ old
)
µ kioldφ jkold
=
∑
K
t =1
µtiold φ old
jt
M & & K
Q = EC ∑∑∑∑ 1{sm =i ,dm = j ,cm =k } ( log π i + log µki + log φ jk )
m =1 i =1 j =1 k =1
M & & K
= ∑∑∑∑ 1{sm =i ,dm = j} ECm 1{cm =k} ( log π i + log µki + log φ jk )
m =1 i =1 j =1 k =1
M & & K
(
= ∑∑∑∑ 1{sm =i ,dm = j} p C = k | S = i, D = j ; Θold ) ( log π i + log µki + log φ jk ) (4.6)
m =1 i =1 j =1 k =1
& & K
= ∑∑∑ Aijωkij ( log π i + log µki + log φ jk )
i =1 j =1 k =1
& & & & K
= ∑∑ Aij log π i + ∑∑∑ Aijωkij ( log µ ki + log φ jk )
i =1 j =1 i =1 j =1 k =1
Q MAP = Q + log p ( µ , φ | α , β )
= Q + log p ( µ | α ) + log p (φ | β ) (4.8)
& K
= Q + ∑ log p ( µi | α ) + ∑ log p (φk | β )
i =1 k =1
Les variables {µi } et {φk } étant des variables qui suivent une loi de Dirichlet, leurs
distributions sont données respectivement par [Bishop 07] :
K
p ( µi | α ) = C (α ) ∏ µkiα −1 (4.9)
k =1
124
Chapitre 4 Le modèle SPCE
&
p (φk | β ) = C ( β ) ∏ φ jkβ −1 (4.10)
j =1
Cela signifie que la probabilité a priori d’un nœud i est proportionnelle au nombre de liens
sortants que possède ce nœud.
α − 1 + ∑ j =1 Aijωkij
&
µki = (4.14)
K (α − 1) + ∑ t =1 ∑ j =1 Aijωtij
K &
β − 1 + ∑ i =1 Aijωkij
&
φ jk = (4.15)
& ( β − 1) + ∑ l =1 ∑ i =1 Ailωkil
& &
125
Chapitre 4 Le modèle SPCE
L’algorithme EM complet pour l’estimation des paramètres du modèle SPCE est décrit
par l’algorithme 4.1. Nous constatons que dans l’étape M, α et β jouent le rôle de pseudo-
comptes (ou de pseudo-liens) qui permettent à SPCE de prendre en compte la faible densité
du graphe. Ainsi, lorsque α = β = 1, SPCE est équivalent à PHITS. Ceci est évident car dans
un pareil cas, les a priori de Dirichlet sont uniformes et les distributions a posteriori ne
dépendent donc que de la vraisemblance. Afin d’éviter des valeurs de probabilité
incohérentes, nous imposons α ≥ 1 et β ≥ 1. En outre, dans le cas où α = β = 2, cela revient au
lissage de Laplace (ajout de 1) utilisé en recherche d’information.
10. µki =
K (α − 1) + ∑ t =1 ∑ j =1 Aijωtij
K &
β − 1 + ∑ i =1 Aijωkij
&
11. φ jk =
& ( β − 1) + ∑ l =1 ∑ i =1 Ailωkil
& &
12. fin
13. jusqu’à convergence
fin
126
Chapitre 4 Mise en œuvre du modèle SPCE
Comme nous l’avons précisé, l’initialisation joue un rôle important dans l’algorithme EM
et dans les techniques d’optimisation en général. C’est pourquoi nous proposons ici trois
stratégies d’initialisation différentes pour l’algorithme d’estimation des paramètres du modèle
SPCE. Nous avons tenu à ce que ces stratégies aient une complexité faible. En effet, il n’est
guère intéressant d’avoir une méthode d’initialisation dont la complexité est supérieure à celle
de l’algorithme SPCE.
La première méthode d’initialisation est une initialisation aléatoire où les paramètres µ
et φ sont tirés à partir d’une distribution de Dirichlet. Nous avons pour cela utilisé la boîte à
outils Fastfit développée par Thomas Minka [URL 2]. Nous désignerons par SPCER la version
de SPCE qui utilise cette méthode d’initialisation.
La deuxième méthode consiste à utiliser l’algorithme des K-moyennes pour faire un
premier regroupement des documents. Ce regroupement est ensuite utilisé pour initialiser la
matrice φ . Plus précisément, il s’agit d’initialiser les K colonnes de cette matrice par les K
centres (ou centroïdes) des clusters. Pour le calcul de similarités entre les documents par
l’algorithme des K-moyennes, nous utilisons la mesure du cosinus. Nous désignerons par
SPCEK la version de SPCE qui utilise une initialisation basée sur l’algorithme des K-
moyennes.
La troisième stratégie est basée sur deux éléments. D’une part, l’utilisation de Graclus
[Dhillon et al. 07], un algorithme efficace (en termes de qualité et de rapidité) pour le
partitionnement de graphes, et d’autre part, l’utilisation de la mesure d’Amsler [Amsler 72]
pour le calcul de similarité entre documents. Graclus est un algorithme clustering spectral de
graphes. Cependant, comme il ne fonctionne qu’avec des graphes non-orientés, nous
calculons à partir du graphe de documents initial un graphe non-orienté en utilisant la mesure
d’Amsler. La mesure d’Amsler entre deux documents i et j est définie par [Calado et al. 03] :
V (i ) ∩V ( j )
sim Ams ( i, j ) = (4.16)
V (i ) ∪V ( j )
où V(k) correspond au voisinage immédiat du document i i.e. l’ensemble des documents qui
pointent vers i ou bien qui sont pointés par celui-ci. L’avantage de cette mesure de similarité
est qu’elle prend en compte à la fois les liens entrants et les liens sortants pour calculer la
similarité entre deux documents, à la différence des mesures de co-citation ou de couplage
bibliographique qui ne prennent en compte qu’un seul type de liens (sortants ou entrants). De
la même façon que la méthode précédente, une fois le partitionnement effectué par Graclus,
nous initialisions la matrice φ par les centres des différentes partitions. Nous désignerons par
SPCEG la version de SPCE qui utilise cette troisième méthode d’initialisation.
127
Chapitre 4 Mise en œuvre du modèle SPCE
Nous avons remarqué lors de nos expérimentations que les paramètres de lissage α et β
influent beaucoup sur la qualité de la structure de communautés identifiée par SPCE. C’est
pourquoi nous avons jugé utile de proposer une méthode permettant de déterminer les valeurs
optimales pour ces paramètres. Dans la version initiale de SPCE, publiée à ICMLA’09, nous
avons utilisé la modularité pour trouver les valeurs des paramètres de lissage. Cependant,
nous allons ici proposer une nouvelle méthode pour arriver à cette fin et laisser plutôt la
modularité comme mesure d’évaluation qui sera utilisée dans la section 4.3.
Nous commençons d’abord par faire une simplification en considérant que α = β . Cette
simplification est motivée par le fait que l’hyper-paramètre α (resp. β ) détermine le nombre
total de pseudo-liens sortants (resp. entrants) qui seront pris en compte lors de l’estimation
des paramètres du modèle. En prenant α = β , nous supposons ainsi que le nombre de pseudo-
liens entrants est égal au nombre de pseudo-liens sortants. Cela semble raisonnable puisque
dans un graphe orienté, le nombre total de liens entrants est toujours égal au nombre total de
liens sortants. De plus, nous allons supposer que α et β prennent des valeurs telles que :
α = β = 1+ λ M (4.17)
K×&
où M est le nombre total de liens, K est le nombre de communautés, & est le nombre total de
nœuds (i.e. de documents) et λ est un réel compris entre 0 et 1. Le paramètre λ détermine le
pourcentage de pseudo-liens par rapport au nombre total de liens qui seront pris en compte
lors de l’estimation des paramètres. λ = 0 signifie qu’aucun pseudo-lien ne sera pris en
compte (i.e. pas de lissage) tandis que λ = 1 signifie que M pseudo-liens (i.e. 100% du
nombre total de liens) seront pris en compte.
La solution que nous proposons est basée sur la méthode de la validation croisée [Bishop
07] ainsi que sur la mesure de la perplexité comme critère de qualité d’un modèle. La
validation croisée à K-passes (K-fold cross validation) est une technique permettant de
sélectionner le meilleur modèle parmi plusieurs modèles candidats (ces modèles ne sont pas
forcément des modèles probabilistes) [Utsugi 97]. Elle consiste à diviser l’ensemble de
données en K ensembles de tailles plus ou moins égales puis à répéter K fois l’opération
suivante : utiliser K-1 groupes (appelés données d’apprentissage) pour l’apprentissage du
modèle et le groupe restant (appelé donnée de test) pour l’évaluation du modèle avec un
critère donné. La qualité du modèle est alors égale à la moyenne des K mesures de qualités
calculées lors de chaque passe.
La perplexité est une mesure propre aux modèles génératifs. Sa valeur est inversement
proportionnelle à la vraisemblance des données de test. Formellement, la perplexité d’un
ensemble de données de test T est définie par [Hofmann 01]:
LL (T )
PP = exp − (4.18)
T
log p ( ( s1 , d1 ) ,… , ( sH , d H ) | Θ )
PP SPCE = exp −
H
H
)
K
∑ log ∑ (
π sh µksh φdh k (4.19)
= exp − h =1 k =1
H
L’interprétation de la perplexité est la suivante : plus elle est petite, meilleur est le
modèle.
Dans la littérature sur les modèles génératifs, il existe tout un domaine qui s’intéresse à la
problématique de la sélection de modèles. Plusieurs critères ont été proposés tels que les
critères AIC (Akaike Information Criterion) ou BIC (Bayesian Information Criterion)
[MacKay 02]. L’avantage de ces mesures est qu’elles peuvent être calculées directement à
partir de la log-vraisemblance des données. Cependant, cet avantage s’avère être aussi un
inconvénient car la vraisemblance des données d’apprentissage n’est pas un critère suffisant
pour juger de la qualité d’un modèle génératif. D’ailleurs, lors de nos expérimentations, nous
avons testé la capacité du modèle SPCE à déterminer le nombre de communautés en utilisant
les critères AIC et BIC mais nous n’avons pas obtenus de résultats concluants.
Afin de calculer le nombre de communautés avec le modèle SPCE, nous adoptons à
nouveau la méthode de la validation croisée décrite dans la section précédente. Nous
appliquons ainsi l’algorithme SPCE en utilisant différentes valeurs pour le nombre de
communautés. Pour chacune de ces valeurs, la perplexité du modèle obtenu est calculée et le
modèle aboutissant à la plus faible perplexité est choisi.
a) Graphes utilisés :
129
Chapitre 4 Evaluation expérimentale du modèle SPCE
regroupement à partir des liens entrants et à partir des liens sortants. Pour les autres
approches, il sera nécessaire de lancer l’algorithme deux fois : une première fois avec la
matrice d’adjacence et une deuxième fois avec la transposée de la matrice d’adjacence.
Pour chacun des graphes, nous analysons uniquement la plus grande composante
faiblement connexe.
b) Mesures d’évaluation :
Pour les mesures d’évaluation, plusieurs critères sont envisageables. En effet, l’ISC peut
être considérée comme étant une tâche de clustering et dans ce domaine, les chercheurs ont
proposé depuis longtemps plusieurs mesures d’évaluation de clustering. Ces mesures
d’évaluation sont de deux types : les mesures internes et les mesures externes. Le lecteur est
invité à consulter [Jain et al. 99][Halkidi et al. 01][Tan et al. 05] pour plus de détail sur ces
mesures.
Les mesures internes sont propres au modèle, nous pouvons citer la mesure de silhouette,
la distance euclidienne ou encore la vraisemblance des données. D’autres mesures internes
concernent l’identification de communautés telles que la modularité de Newman ou encore la
coupe normalisée (normalized cut [Shi and Malik 97]). Parmi toutes ces mesures, nous
utiliserons la modularité qui est d’ailleurs la plus utilisée [Fortunato 10].
Les mesures dites externes font appel à des informations supplémentaires concernant la
classe de chaque objet à classer. Dans le cas de l’ISC, il s’agit d’informations concernant la
communauté à laquelle appartient chaque sommet. Là encore, une panoplie de mesures existe,
nous citerons par exemple : l’entropie, la pureté, la F-mesure, l’information mutuelle
normalisée (NMI, Normalized Mutual Information), l’indice de Rand, la variation
d’information. etc. Nous avons utilisé plusieurs de ces mesures lors de nos expérimentations
mais nous présenterons uniquement les résultats concernant la F-mesure et la NMI. Ces deux
mesures sont en effet très utilisées dans le domaine de l’évaluation de la classification non
supervisée.
La NMI est une mesure issue de la théorie de l’information permettant de comparer deux
partitions (ou clusterings). Avec cette mesure, on considère chaque partition comme une
distribution de probabilité et on calcule la quantité d’information commune aux deux
distributions. Strehl [Strehl 02] propose de normaliser ce critère afin que sa valeur soit
comprise entre 0 et 1. Une valeur 1 indique que les deux partitions sont identiques.
La F-mesure est une mesure très connue dans le domaine de la recherche d’information.
Elle est égale à la moyenne géométrique entre la précision et le rappel. Elle est toujours
comprise entre 0 et 1.
c) Algorithmes comparés :
Nous comparons plusieurs algorithmes d’ISC. L’accent sera mis sur les approches
génératives. Mais pour donner une idée sur les performances des approches non génératives,
nous présentons également les résultats de deux approches non génératives à savoir
l’algorithme des K-moyennes et l’algorithme Graclus décrit dans la section 4.2.1. Pour les
130
Chapitre 4 Evaluation expérimentale du modèle SPCE
approches génératives, nous comparons le modèle SPCE avec trois initialisations différentes
au modèle PHITS et au modèle MNL (Mélange de Multinomiales de Newman et Leicht).
Nous n’avons pas pu appliquer le modèle SBM avec nos graphes en raison de la forte
complexité de ce modèle qui, rappelons-le, est de O ( IK 2 & 2 ) .
d) Résultats expérimentaux
Les tableaux 4.1, 4.2 et 4.3 indiquent les résultats expérimentaux obtenus en appliquant
les différents algorithmes comparés avec les quatre graphes utilisés dans cette étude. Nous
remarquons que les performances du modèle SPCEG sont meilleures que celles des autres
approches ; elles sont en particulier nettement supérieures à celles des autres approches
génératives. Les modèles MNL et PHITS donnent quant à eux de mauvais résultats. Les trois
tableaux montrent également que l’initialisation du modèle SPCE influe beaucoup sur ses
performances, et que l’initialisation basée sur l’algorithme Graclus et la mesure d’Amsler
permet d’atteindre les meilleures performances. L’apport de l’initialisation est toutefois moins
conséquent lors de l’analyse des graphes Plasma_Physics et Solar_Wind. En effet, ces deux
graphes étant "suffisamment" denses, les différents modèles génératifs réussissent à trouver
une structure de communautés de bonne qualité. Les résultats de PHITS et de SPCER
montrent que le lissage permet d’améliorer légèrement les performances et que celui-ci n’est
pas suffisant à lui seul pour obtenir des performances optimales. Nous observons par ailleurs
que les performances de l’algorithme Graclus sont comparables à celles de SPCEG (à une
exception près pour le graphe Cora(T)). Enfin, nous noterons que les résultats avec les liens
sortants sont dans la plupart des cas meilleurs que ceux avec les liens entrants. Cela
s’explique par le fait que dans les quatre graphes étudiés, il existe plus de documents ayant au
moins un lien sortant que de documents ayant au moins un lien entrant.
131
Chapitre 4 Evaluation expérimentale du modèle SPCE
Nous étudions à présent l’effet du paramètre de lissage λ (lambda) sur la qualité des
résultats du modèle SPCE. Nous reportons sur les figures 4.2, 4.3, 4.4 et 4.5 la modularité et
la NMI en fonction du paramètre λ pour les graphes Cora et Citeseer. Les résultats avec les
liens sortants étant similaires à ceux avec les liens entrants, nous reporterons ici uniquement
les résultats concernant les liens entrants ; ceux avec les liens sortants sont présentés dans
l’annexe C. L’évaluation de la perplexité montre que le lissage joue un rôle crucial lorsque
l’initialisation n’est pas de bonne qualité alors qu’une bonne initialisation réduit l’importance
du lissage. Les résultats de la NMI montrent que le lissage améliore légèrement les
performances du modèle SPCER tandis qu’à partir d’un certain seuil, il détériore légèrement
celles de SPCEG. De plus, pour ce dernier, nous avons remarqué qu’une valeur de λ = 0.1
132
Chapitre 4 Evaluation expérimentale du modèle SPCE
donne toujours des résultats très satisfaisants. Cela nous permet de suggérer une valeur fixe
pour λ avec le modèle SPCEG afin d’éviter le calcul de la valeur optimale de ce paramètre.
Les figures montrent également qu’avec le modèle SPCEG, la plus faible perplexité coïncide
avec la meilleure modularité ainsi qu’avec la meilleure NMI. Cela confirme que la perplexité
est aussi un bon indicateur pour la qualité de la structure de communautés identifiée.
Le tableau 4.4 indique les résultats de la NMI et de la perplexité obtenus en appliquant
les algorithmes PHITS, SPCER, SPCEK et SPCEG avec les graphes Cora et Citeseer sans
utiliser de lissage (i.e. λ = 0 ). Nous remarquons que les performances de PHITS sont les plus
faibles alors que celles de SPCEG sont les meilleures. D’après la figure 4.3, la plus faible
perplexité de SPCEG (lorsque λ = 0.2 ) avec le graphe Cora est égale à 4.8 × 107 tandis que
lorsqu’aucun lissage n’est appliqué, ce même algorithme a une perplexité de 1.3 ×1010 (voir
tableau 4.4). Cela signifie que le lissage a un impact très important sur la capacité du modèle
SPCE à prédire de nouvelles données.
7
x 10
0.5 12
SPCE(R)
0.45
11 SPCE(K)
0.4 SPCE(G)
10
0.35
0.3 9
Perplexité
NMI
0.25 8
0.2
7
0.15
6
0.1 SPCE(R)
SPCE(K) 5
0.05
SPCE(G)
0 4
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
lambda lambda
Figure 4.2 - La %MI en fonction du paramètre de Figure 4.3 - La Perplexité en fonction du paramètre de
lissage lambda avec le graphe Cora lissage lambda avec le graphe Cora
8
x 10
0.4 2.6
SPCE(R) SPCE(R)
0.35 SPCE(K) SPCE(K)
2.4
SPCE(G) SPCE(G)
0.3
2.2
0.25
Perplexité
2
NMI
0.2
1.8
0.15
1.6
0.1
0.05 1.4
0 1.2
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
lambda lambda
Figure 4.4 - La %MI en fonction du paramètre de Figure 4.5 - La Perplexité en fonction du paramètre de
lissage lambda avec le graphe Citeseer lissage lambda avec le graphe Citeseer
133
Chapitre 4 Evaluation expérimentale du modèle SPCE
NMI Perplexité
Graphe PHITS SPCER SPCEK SPCEG PHITS SPCER SPCEK SPCEG
Cora (O) 0.04 0.04 0.20 0.46 4.4 × 1012 4.4 × 1012 1.2 × 1011 1.3 × 1010
Citeseer (O) 0.03 0.03 0.16 0.35 8.3 × 1011 8.3 × 1011 2.4 × 1010 1.6 × 1010
Nous évaluons ici la robustesse des modèles PHITS et SPCE face à la faible densité des
graphes. Pour ce faire, nous analysons chacun des quatre graphes étudiés en retirant à chaque
fois un certain pourcentage de liens. La modularité de la structure de communautés obtenue
avec chacun des deux modèles est ensuite calculée. Les résultats obtenus sont indiqués par les
figures 4.6, 4.7, 4.8 et 4.9. En retirant 40% des liens, la modularité de PHITS se dégrade de
presque 50% tandis que celle de SPCE ne baisse que d’environ 10%. En enlevant 80% des
liens, PHITS n’arrive plus à retrouver la structure de communautés puisque celle-ci a une
modularité quasi nulle. La modularité avec SPCE quant à elle baisse d’environ 50% lorsque
80% des liens ont été retirés ce qui est satisfaisant. Notons également que le retrait de liens
affecte beaucoup plus les graphes Cora et Citesser que les graphes Plasma_Physics et
Solar_Wind : les deux premiers étant beaucoup moins denses que les deux derniers.
0.5 0.4
PHITS PHITS
0.45
SPCE(G) 0.35 SPCE(G)
0.4
0.3
0.35
0.3 0.25
Modularité
Modularité
0.25 0.2
0.2
0.15
0.15
0.1
0.1
0.05 0.05
0 0
0 10 20 30 40 50 60 70 80 0 10 20 30 40 50 60 70 80
Pourcentage de liens retirés Pourcentage de liens retirés
Figure 4.6 - La Modularité par rapport au Figure 4.7 - La Modularité par rapport au
pourcentage de liens retirés du graphe Cora pourcentage de liens retirés du graphe Citeseer
134
Chapitre 4 Evaluation expérimentale du modèle SPCE
0.7 0.7
PHITS PHITS
0.6 SPCE(G) 0.6 SPCE(G)
0.5 0.5
Modularité
Modularité
0.4 0.4
0.3 0.3
0.2 0.2
0.1 0.1
0 0
0 10 20 30 40 50 60 70 80 0 10 20 30 40 50 60 70 80
Pourcentage de liens retirés Pourcentage de liens retirés
Figure 4.8 - La Modularité par rapport au Figure 4.9 - La Modularité par rapport au
pourcentage de liens retirés du graphe pourcentage de liens retirés du graphe
Plasma_Physics Solar_Wind
Nous avons suivi la méthodologie utilisée notamment par [Daudin et al. 08] et [Latouche
et al. 10] pour évaluer la capacité de notre modèle à calculer le nombre correct de
communautés dans un graphe. Cette méthode consiste à générer des graphes dont le nombre
exact de communautés est connu. Cette méthode peut aussi être utilisée pour évaluer et
comparer la qualité des algorithmes d’ISC ; les graphes générés servent de benchmarks.
Lancichinetti et Fortunato [Lancichinetti and Fortunato 09] ont développé récemment un outil
permettant de générer des graphes tests ayant différentes propriétés : orientés ou non,
pondérés ou non, etc. Newman [Newman 04a][Newman 06] est le premier à avoir suggéré
l’utilisation de graphes test pour comparer et évaluer des algorithmes d’ISC. Il a notamment
proposé un processus permettant de générer un graphe non orienté de 128 nœuds appartenant
à quatre communautés. Un paramètre permet de jouer sur la connectivité de la structure de
communautés i.e. le nombre de liens que possède un nœud vers l’intérieur de la communauté
versus vers l’extérieur de la communauté.
135
Chapitre 4 Le modèle SPCE-PLSA
Pour l’évaluation de cette partie, nous avons généré des graphes orientés contenant un
nombre fixe de communautés. Nous considérons un cas simple où les communautés sont de
taille et de densité homogènes. Les résultats préliminaires obtenus montrent que la méthode
proposée pour le calcul du nombre de communautés permet de déterminer le nombre exact de
communautés dans un graphe.
Nous envisageons à l’avenir d’utiliser la plateforme de Lancichinetti et Fortunato
[Lancichinetti and Fortunato 09] pour comparer et évaluer notre modèle avec différents types
de graphes y compris en ce qui concerne l’évaluation du calcul du nombre de communautés.
Il serait particulièrement intéressant d’étudier la sensibilité de SPCE au problème de la
"résolution limite" dont souffre la modularité.
4.4 SPCE-PLSA : un modèle hybride pour l’analyse des liens et des contenus
Dans [Cohn and Hofmann 01], Hofmann, l’auteur du modèle PLSA et Cohn, l’un des
auteurs du modèle PHITS, proposent le modèle PHITS-PLSA pour l’analyse combinée des
liens et des contenus. En s’inspirant de leurs travaux, nous proposons dans cette section le
modèle SPCE-PLSA qui combine notre modèle SPCE pour l’analyse de liens entre
documents avec le modèle PLSA pour l’analyse des contenus des documents.
Les approches hybrides combinant analyse de liens et de contenus ont reçu une attention
particulière de la part des chercheurs dans le domaine de la fouille de textes. A titre
d’exemple, la thèse de Janssens [Janssens 07] est entièrement consacrée à cette
problématique. D’autres exemples incluent les travaux de [Chakrabarti et al. 01], [Drost et al.
06], [Wang and Kitsuregawa 02], [Modha and Spangler 00] ou encore ceux de [Jo et al. 07].
Notons également à ce propos que nous avons proposé dans [Chikhi et al. 08b] une approche
hybride pour le regroupement automatique de documents. Il s’agit dans ce cas d’une approche
basée sur l’idée du voisinage bibliographique.
136
Chapitre 4 Le modèle SPCE-PLSA
Nous noterons par Θ l’ensemble des paramètres (et hyper-paramètres) du modèle SPCE-
PLSA i.e. :
Θ = π iL ( ) i =1,…, &
( )
, π iC
i =1,…, &
( )
, ( µki )k =1,…, K , φ jkL j =1,…, & ( )
, φvkC v =1,…,V ,α , β
i =1,…, & k =1,…, K k =1,…, K
α
πL S X πC
β
T µ T
&
φL D W φC
K M P
137
Chapitre 4 Le modèle SPCE-PLSA
Comme pour le modèle SPCE, nous utilisons l’estimation par maximum a posteriori pour
estimer les paramètres du modèle SPCE-PLSA. L’algorithme 4.2 indique l’algorithme EM
pour l’estimation des paramètres de SPCE-PLSA. Il est à noter que ce dernier utilise un
paramètre 0 ≤ γ ≤ 1 indiquant l’importance relative donnée aux liens et aux contenus. Lorsque
γ = 0 , le modèle est équivalent à SPCE, tandis que lorsque γ = 1 , le modèle revient à faire
une analyse basée sur les contenus avec PLSA.
138
Chapitre 4 Le modèle SPCE-PLSA
4. fin
5. répéter
// Etape E de l’algorithme
6. pour i = 1… & , j = 1… & et k = 1… K faire
µkiφ jkL
7. ωkijL ←
∑
K
t =1
µtiφ jtL
8. fin
9. pour i = 1… & , j = 1…V et k = 1… K faire
µ kiφ Cjk
10. ω ← C
∑
kij K
t =1
µtiφ Cjt
11. fin
// Etape M de l’algorithme
12. pour i = 1… & et k = 1… K faire
α − 1 + ∑ j =1 AijωkijL ∑ Wω
& V C
µki = (1 − γ ) × j =1 ij kij
13. +γ×
K (α − 1) + ∑ t =1 ∑ j =1 AijωtijL ∑ ∑ Wω
K & K V C
t =1 j =1 ij tij
β − 1 + ∑ i =1 AijωkijL
&
φ = L
& ( β − 1) + ∑ l =1 ∑ i =1 AilωkilL
jk & &
14.
∑ Wω
& C
φ i =1 iv kiv
C
=
∑ ∑ Wω
vk V & C
l =1 i =1 il kil
15. fin
16. jusqu’à convergence
fin
139
Chapitre 4 Le modèle SPCE-PLSA
Pour l’initialisation du modèle SPCE-PLSA, nous utilisons pour les paramètres φ L une
initialisation basée sur un clustering initial avec l’algorithme Graclus en utilisant la mesure de
similarité d’Amsler. Pour les paramètres µ et φC , ils sont initialisés par des valeurs
aléatoires.
Pour les paramètres de lissage α et β , nous adoptons la stratégie proposée dans la
section 4.3.2 qui consiste à fixer ces paramètres aux valeurs suivantes :
α = β = 1 + 10−1 M (4.20)
&×K
où M est le nombre total de liens dans le graphe de documents, & est le nombre de sommets
(i.e. de documents) et K est le nombre de thèmes.
Enfin, le paramètre γ qui détermine l’importance des liens et des contenus a un impact
important sur les performances du modèle SPCE-PLSA. Trouver la valeur optimale pour ce
paramètre est une tâche délicate sur laquelle plusieurs chercheurs se sont penchés. A notre
connaissance, il n’existe aucune solution satisfaisante dans la littérature à cette problématique.
C’est pourquoi nous proposons d’utiliser, encore une fois, la méthode de la validation croisée
en prenant comme critère la perplexité pour déterminer le meilleur compromis entre les liens
et les contenus. Nous utilisons plus précisément une validation croisée à cinq passes où l’on
divise les ensembles des liens et des occurrences de mots en cinq ensembles de tailles plus ou
moins égales. L’apprentissage du modèle SPCE-PLSA se fait à chaque fois en utilisant 80%
des données (i.e. des liens et des occurrences de mots) puis la perplexité est calculée pour les
20% restants. L’opération est répétée cinq fois et la perplexité finale est obtenue en faisant la
moyenne des cinq valeurs de la perplexité obtenues à chaque étape de la validation croisée.
Plus précisément, la perplexité est égale à la moyenne entre la perplexité par rapport aux liens
et la perplexité par rapport aux contenus.
Nous utilisons les corpus Cora et Citeseer pour évaluer les performances du modèle
SPCE-PLSA en termes de NMI, de F-mesure, de modularité et de perplexité. Bien que la
modularité ne soit pas un critère pertinent pour évaluer le regroupement en thématiques, nous
reportons quand même les résultats avec cette mesure car elle montre l’impact de la prise en
compte des contenus sur la structure de communautés identifiée. Notre modèle est comparé au
modèle PHITS-PLSA. Les résultats obtenus sont indiqués par les figures 4.11, 4.12, 4.13 et
4.14. La perplexité avec le modèle PHITS-PLSA étant très élevée (de l’ordre de 1012), nous
n’avons pas rapporté les résultats qui la concernent.
140
Chapitre 4 Le modèle SPCE-PLSA
0.55 0.7
0.5 0.65
0.45
0.6
0.4
0.55
0.35
F-mesure
0.5
NMI
0.3
0.45
0.25
0.4
0.2
0.15 0.35
Figure 4.11 - La %MI en fonction du paramètre Figure 4.12 - La F-mesure en fonction du paramètre
gamma pour le corpus Cora Gamma pour le corpus Cora
6
x 10
0.65 3.1
SPCE-PLSA
0.6 3
0.55
2.9
0.5
2.8
Modularité
Perplexité
0.45
2.7
0.4
2.6
0.35
0.3 2.5
Figure 4.13 - La Modularité en fonction du paramètre Figure 4.14 - La Perplexité en fonction du paramètre
gamma pour le corpus Cora gamma pour le corpus Cora
Avec le corpus Cora, nous remarquons que l’utilisation combinée des liens et des
contenus permet d’améliorer considérablement les performances en particulier avec le modèle
SPCE-PLSA. Le paramètre gamma semble avoir beaucoup moins d’effet sur les performances
de SPCE-PLSA que sur les performances de PHITS-PLSA. Pour SPCE-PLSA, il semblerait
même que n’importe quelle valeur de gamma permet d’obtenir de meilleurs résultats qu’avec
le modèle SPCE ou PLSA seuls. La perplexité indique par ailleurs que SPCE-PLSA explique
mieux les données de test lorsque la valeur de gamma est proche de 1. Cela se justifie par le
fait que la matrice documents/termes contient beaucoup plus de données que la matrice
d’adjacence. Pour le corpus Cora par exemple, nous avons 5209 liens entre documents contre
155429 occurrences de mots dans le corpus, soit presque 30 fois plus que de liens. Enfin, la
perplexité permet de déterminer une "bonne“ valeur pour le paramètre gamma à savoir 0.9
pour le corpus Cora.
141
Chapitre 4 Le modèle SPCE-PLSA
0.5 0.75
0.45 0.7
0.4
0.65
0.35
0.6
0.3
F-mesure
0.55
NMI
0.25
0.5
0.2
0.45
0.15
0.1 0.4
Figure 4.15 - La %MI en fonction du paramètre Figure 4.16 - La F-mesure en fonction du paramètre
gamma pour le corpus Citeseer gamma pour le corpus Citeseer
6
x 10
0.8 3
SPCE-PLSA
0.7 2.8
0.6 2.6
Modularité
Perplexité
0.5 2.4
0.4 2.2
0.3 2
Figure 4.17 - La Modularité en fonction du paramètre Figure 4.18 - La Perplexité en fonction du paramètre
gamma pour le corpus Citeseer gamma pour le corpus Citeseer
Les figures 4.15, 4.16, 4.17 et 4.18 montrent que l’amélioration des performances en
utilisant le modèle PHITS-PLSA avec le corpus Citeseer est moins bonne qu’avec le corpus
Cora. La meilleure performance qu’atteint ce modèle (lorsque γ = 0.9 ) est en effet presque
égale à la performance du modèle PLSA seul. PHITS ne semble pas apporter un plus pour
l’identification de thématiques. Le modèle SPCE-PLSA, quant à lui, améliore
considérablement les performances et ce quelle que soit la valeur du paramètre gamma. En
d’autres termes, rien qu’en effectuant une analyse hybride avec SPCE-PLSA, on améliore
l’identification de thématiques quelle que soit l’importance donnée aux liens et aux contenus.
Les résultats de la perplexité indiquent que la meilleure valeur de celle-ci est atteinte lorsque
γ = 0.8 . Cette valeur est légèrement inférieure à la valeur précédente avec Cora (i.e. γ = 0.9 )
car le rapport entre le nombre d’occurrences de mots dans le corpus et le nombre total de liens
entre documents est plus petit ( 62506/3366 ≃ 19 ).
142
Chapitre 4 Bilan
4.5 Bilan
Nous avons proposé dans ce dernier chapitre le modèle génératif SPCE pour
l’identification de structures de communautés dans les graphes de documents. Nous avons
décrit son processus génératif, son algorithme d’estimation des paramètres, sa procédure
d’initialisation ainsi qu’une méthode permettant à la fois de déterminer les valeurs optimales
des paramètres de lissage et de calculer le nombre exact de communautés dans un graphe.
Une partie expérimentale validant le modèle a notamment été présentée. Les résultats de
celle-ci ont montré que le modèle SPCE possède de très bonnes performances.
En utilisant les critères que nous avons établis à la fin du troisième chapitre, nous
résumons dans le tableau 4.5 les différentes propriétés du modèle SPCE.
Enfin, nous avons présenté le modèle SPCE-PLSA qui est un modèle génératif hybride
combinant analyse de liens et analyse des contenus pour l’identification de thématiques i.e.
pour la classification non supervisée de documents. L’évaluation du modèle SPCE-PLSA sur
des corpus de documents a mis en valeur l’intérêt d’une approche hybride pour le
regroupement de documents car celui-ci réalise de meilleures performances que le modèle
SPCE ou le modèle PLSA appliqués séparément.
Propriété SPCE
143
Conclusion
Conclusion
Le travail réalisé dans le cadre de cette thèse s’inscrit dans le domaine de l’extraction de
connaissances à partir de documents. Une des originalités de notre approche réside dans le fait
d’analyser les liens entre documents au lieu d’analyser leurs contenus comme le font la
plupart des travaux existants. Ce travail a été motivé par le besoin de caractériser de grandes
collections de documents afin de faciliter leur utilisation et leur exploitation par des humains
ou par des outils informatiques. Pour répondre à ce besoin, nous avons entrepris des
recherches suivant deux axes qui, à première vue, peuvent sembler indépendants mais qui
sont en fait liés. Concrètement, nous avons développé de nouveaux algorithmes d’analyse de
liens entre documents en se basant sur des techniques d’apprentissage automatique.
Dans un premier temps, nous avons abordé la problématique du calcul de centralité dans
les graphes de document. Il s’agit d’assigner un degré d’importance ou de popularité à chaque
document en se basant uniquement sur ses connexions avec les autres documents du graphe.
Dans ce premier volet de la thèse, nous avons décrit les principaux algorithmes de calcul de
centralité existants en distinguant les approches issues de l’analyse des réseaux sociaux de
celles issues de la recherche d’information. Nous avons montré que les mesures de centralité
proposées récemment en recherche d’information (telles que HITS ou PageRank)
correspondent en fait à des variantes de la centralité spectrale publiée au début des années
1970 par Bonacich. Nous avons également mis l’accent sur le problème TKC (Tightly Knit
Community) dont souffre la plupart des mesures de centralité récentes. Ce problème est dû à
la présence de communautés c’est-à-dire de sous-graphes de forte densité possédant peu de
liens entre eux dans les graphes de documents (il s’agit en fait d’une propriété inhérente à ce
type de graphes). En pratique, l’effet TKC se manifeste par une attribution non équitable des
degrés d’importance aux différents documents. Ensuite, nous avons proposé trois nouveaux
algorithmes de calcul de centralité dans les graphes de documents permettant d’affronter le
phénomène TKC. Dans l’algorithme DocRank, un des trois algorithmes proposés, le degré
d’autorité (resp. d’hubité) d’un document n’est pas simplement proportionnel au nombre de
documents qui le citent (resp. qu’il cite) mais est plutôt égal à la somme des poids des
recommandations qu’il reçoit (resp. qu’il effectue). Le poids de chaque recommandation est,
144
Conclusion
145
Conclusion
- il calcule simultanément deux regroupements (un à partir des liens entrants et l’autre à
partir des liens sortants),
- il est générique et peut être utilisé pour l’ISC dans d’autres types de graphes,
- et surtout il possède une complexité linéaire par rapport au nombre total de liens dans le
graphe.
Enfin, nous avons montré que le modèle SPCE pouvait être étendu pour prendre en compte
les contenus des documents en plus des liens. Le modèle ainsi obtenu que nous avons appelé
SPCE-PLSA (en référence au modèle PLSA d’analyse des contenues) a lui aussi été évalué en
utilisant deux collections de documents. Les résultats expérimentaux ont montré que le
regroupement de documents obtenu en exploitant simultanément les liens et les contenus est
meilleur que celui obtenu en utilisant uniquement les liens ou les contenus. Les résultats de ce
deuxième volet de la thèse illustrent, à notre avis, le grand intérêt d’une approche générative
pour la classification non supervisée de documents.
Naturellement, de nombreuses perspectives sont envisageables pour poursuivre ce
travail. Nous citons ci-dessous celles qui nous semblent les plus importantes.
Concernant le calcul de centralité, il serait, par exemple, intéressant de développer une
technique permettant de déterminer de manière automatique la valeur optimale du paramètre
de normalisation de l’algorithme DocRank. Lors de nos expérimentations, nous avons suggéré
la valeur 1 pour ce paramètre qui correspond en fait à une version "démocratique" de
DocRank, mais les résultats expérimentaux ont montré qu’une valeur supérieure à 1
permettait parfois d’obtenir de meilleurs résultats. Une autre piste de recherche concerne
l’utilité de l’algorithme DocRank dans une tâche de recherche d’information. Nous
envisageons en effet d’étudier l’apport de la mesure de centralité calculée par DocRank pour
le calcul de la pertinence d’un document par rapport à une requête utilisateur. Dans ce
contexte, une comparaison entre les différentes mesures de centralité serait également
intéressante.
Quant à l’identification de structures de communautés, nous avons entamé le
développement d’une version totalement bayésienne du modèle SPCE. Il s’agit d’une version
dans laquelle tous les paramètres du modèle sont traités comme des variables dont la
distribution doit être estimée. Une approche bayésienne possède l’avantage d’être moins
sujette au problème du sur-apprentissage (overfitting) qui caractérise les approches
fréquentistes (telles que SPCE ou PHITS). Elle offre également la possibilité de déterminer le
nombre de communautés sans avoir à utiliser une méthode couteuse en temps de calcul telle
que la validation croisée ; les approches bayésiennes permettent en effet de mieux quantifier
la qualité d’un modèle probabiliste puisqu’elles prennent en compte à la fois la vraisemblance
des données et la complexité du modèle. Enfin, pour le modèle hybride SPCE-PLSA proposé,
nous envisageons d’étudier l’apport d’autres sources d’information telles que des ressources
termino-ontologiques ou des tags pour la classification non supervisée de documents.
146
Annexe A Eléments de la théorie des graphes
Annexe A
Eléments de la théorie des graphes
Dans un graphe complet, chaque sommet est adjacent à tous les autres sommets du
graphe.
Un graphe est connexe s’il existe une chaîne entre toute paire de nœuds.
Une composante connexe est un sous-graphe connexe maximal.
147
Annexe A Eléments de la théorie des graphes
Un graphe orienté (ou digraphe) est un graphe où les arêtes sont orientées et sont
appelées des arcs.
Le degré entrant d’un sommet i est le nombre d’arcs dont l’extrémité est i.
Le degré sortant d’un sommet i est le nombre d’arcs dont l’origine est i.
Le degré total d’un sommet est égal à la somme des degrés entrant et sortant de ce
nœud.
Un chemin est une suite finie d’arcs consécutifs (i.e. l’extrémité de chaque arc coïncide
avec l’origine de l’arc suivant). La longueur d’un chemin est égale au nombre d’arcs qui le
composent.
La distance entre deux sommets est la longueur du plus court chemin entre ces sommets.
Un graphe orienté est dit fortement connexe s’il existe un chemin entre tous les couples
de nœuds du graphe.
Un graphe orienté est dit faiblement connexe s’il existe une chaîne entre tous les couples
de nœuds du graphe, autrement dit si sa version non orientée est connexe.
148
Annexe B Compléments au chapitre 2
Annexe B
Compléments au chapitre 2
B.1 Résultats avec le graphe "Apple"
149
Annexe B Compléments au chapitre 2
150
Annexe B Compléments au chapitre 2
0.0033709
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/06/29/a
pple-store-online-down In:1 Out:3
0.0033415
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/07/10/f
ound-footage-iphone-dev-camp-hackathon In:1 Out:4
0.0033145
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/07/10/a
dium-x-hits-1-0-5 In:1 Out:5
0.0033061 http://bookoftech.blogspot.com In:1 Out:1
0.0033061 http://popsci.typepad.com/popsci/2007/06/gotta-get-an-ip.html In:1 Out:1
0.0032943
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/06/29/la
unch-gallery-chicago-il In:1 Out:6
0.0032816
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/07/08/s
py-shot-apple-store-touchwood-uk In:1 Out:6
0.0032773
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/06/29/li
ne-report-iphone-mania In:1 Out:7
0.0032773
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/06/29/it
-aint-easy-to-get-an-iphone-review-unit In:1 Out:7
0.0032728
http://www.technorati.com/cosmos/search.html?rank=&fc=1&url=http://www.tuaw.com/2007/06/29/li
ne-update-sherman-oaks-ca-apple-store In:1 Out:6
151
Annexe B Compléments au chapitre 2
152
Annexe B Compléments au chapitre 2
153
Annexe B Compléments au chapitre 2
154
Annexe B Compléments au chapitre 2
155
Annexe B Compléments au chapitre 2
156
Annexe B Compléments au chapitre 2
157
Annexe B Compléments au chapitre 2
158
Annexe B Compléments au chapitre 2
159
Annexe B Compléments au chapitre 2
160
Annexe B Compléments au chapitre 2
161
Annexe B Compléments au chapitre 2
162
Annexe B Compléments au chapitre 2
163
Annexe B Compléments au chapitre 2
164
Annexe B Compléments au chapitre 2
165
Annexe B Compléments au chapitre 2
166
Annexe B Compléments au chapitre 2
167
Annexe B Compléments au chapitre 2
168
Annexe B Compléments au chapitre 2
169
Bibliographie
Bibliographie
[Aggarwal and Wang 10] C. C. Aggarwal and H. Wang. A Survey of Clustering Algorithms
for Graph Data. Managing and Mining Graph Data. A. K. Elmagarmid, Springer US, 40:
275-301, 2010.
[Agresti 07] A. Agresti. An Introduction to Categorical Data Analysis, 2nd Edition. Wiley,
2007.
[Alba 73] R. D. Alba. A graph-theoretic definition of a sociometric clique. The Journal of
Mathematical Sociology, 3(1):113 - 126, 1973.
[Albert et al. 99] R. Albert, H. Jeong and A.-L. Barabasi. Internet: Diameter of the World-
Wide Web. &ature, 401(6749):130-131, 1999.
[Amsler 72] R. Amsler. Application of citation-based automatic classification, The University
of Texas at Austin, Linguistics Research Center, 1972.
[Anderson et al. 92] C. J. Anderson, S. Wasserman and K. Faust. Building stochastic
blockmodels. Social &etworks, 14(1-2):137-161, 1992.
[Baeza-Yates and Ribeiro-Neto 99] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information
Retrieval. Addison Wesley, 1999.
[Baldi et al. 03] P. Baldi, P. Frasconi and P. Smyth. Modeling the Internet and the Web:
Probabilistic Methods and Algorithms. Wiley, 2003.
[Barabasi 09] A.-L. Barabasi. Scale-Free Networks: A Decade and Beyond. Science,
325(5939):412-413, 2009.
[Barnes 82] E. R. Barnes. An Algorithm for Partitioning the Nodes of a Graph. SIAM Journal
on Algebraic and Discrete Methods, 3(4):541-550, 1982.
[Bennouas 05] T. Bennouas. Modélisation de parcours du web et calcul de communautés par
émergence. Thèse de doctorat, Université Montpellier II, 2005.
[Bharat and Henzinger 98] K. Bharat and M. R. Henzinger. Improved algorithms for topic
distillation in a hyperlinked environment. In Proceedings of the 21st annual international
ACM SIGIR conference on Research and development in information retrieval, Melbourne,
Australia, ACM, pages 104-111, 1998.
[Bishop 07] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2007.
[Bonacich 72] P. Bonacich. Factoring and weighting approaches to status scores and clique
identification. Journal of Mathematical Sociology, 2(1):113-120, 1972.
[Bonacich 07] P. Bonacich. Some unique properties of eigenvector centrality. Social
&etworks, 29(4):555-564, 2007.
170
Bibliographie
171
Bibliographie
172
Bibliographie
[Dhillon and Guan 03] I. S. Dhillon and Y. Guan. Information theoretic clustering of sparse
cooccurrence data. In Third IEEE International Conference on Data Mining, pages 517-
520, 2003.
[Dhillon et al. 07] I. S. Dhillon, Y. Guan and B. Kulis. Weighted Graph Cuts without
Eigenvectors A Multilevel Approach. IEEE Trans. Pattern Anal. Mach. Intell.,
29(11):1944-1957, 2007.
[Ding et al. 02] C. Ding, X. He, P. Husbands, H. Zha and H. D. Simon. PageRank, HITS and
a unified framework for link analysis. In Proceedings of the 25th annual international
ACM SIGIR conference on Research and development in information retrieval, Tampere,
Finland, ACM, pages, 2002.
[Donetti and Munoz 04] L. Donetti and M. A. Munoz. Detecting network communities: a new
systematic and efficient algorithm. Journal of Statistical Mechanics: Theory and
Experiment, 2004(10):P10012, 2004.
[Dourisboure et al. 07] Y. Dourisboure, F. Geraci and M. Pellegrini. Extraction and
classification of dense communities in the web. In Proceedings of the 16th international
conference on World Wide Web, Banff, Alberta, Canada, ACM, pages 461-470, 2007.
[Drost et al. 06] I. Drost, S. Bickel and T. Scheffer. Discovering Communities in Linked Data
by Multi-view Clustering. In From Data and Information Analysis to Knowledge
Engineering. Springer, pages 342-349, 2006.
[Farahat et al. 05] A. Farahat, T. LoFaro, J. C. Miller, G. Rae and L. A. Ward. Authority
Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of
Initialization. SIAM J. Sci. Comput., 27(4):1181-1201, 2005.
[Fiala et al. 08] D. Fiala, F. Rousselot and K. Ježek. PageRank for bibliographic networks.
Scientometrics, 76(1):135-158, 2008.
[Flake et al. 00] G. W. Flake, S. Lawrence and C. L. Giles. Efficient identification of Web
communities. In Proceedings of the 6th ACM SIGKDD international conference on
Knowledge discovery and data mining, Boston, Massachusetts, United States, ACM, pages
150-160, 2000.
[Flake et al. 04] G. W. Flake, K. Tsioutsiouliklis and L. Zhukov. Web Communities:
Bibliometric, Spectral, and Flow. In Web Dynamics: Adapting To Change In Content, Size,
Topology And Use. Springer, pages 45-68, 2004.
[Fortunato 10] S. Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75-
174, 2010.
[Fortunato 08] S. Fortunato, M. Boguñá, A. Flammini and F. Menczer. Approximating
PageRank from In-Degree. Algorithms and Models for the Web-Graph. W. Aiello, A.
Broder, J. Janssen and E. Milios, Springer Berlin / Heidelberg. 4936: 59-71. 2008.
173
Bibliographie
174
Bibliographie
[Jain et al. 99] A. K. Jain, M. N. Murty and P. J. Flynn. Data clustering: a review. ACM
Comput. Surv., 31(3):264-323, 1999.
[Janssens 07] F. Janssens. Clustering of scientific fileds by integrating text mining and
bibliometrics. PhD Thesis, Katholieke Universiteit Leuven, 2007.
[Jo et al. 07] Y. Jo, C. Lagoze and C. L. Giles. Detecting research topics via the correlation
between graphs and texts. In Proceedings of the 13th ACM SIGKDD international
conference on Knowledge discovery and data mining, San Jose, California, USA, ACM,
pages, 2007.
[Kessler 63] M. M. Kessler. Bibliographic coupling between scientific papers. American
Documentation, 14(10):10-25, 1963.
[Kleinberg 98] J. Kleinberg. Authoritative sources in a hyperlinked environment. In
Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, San
Francisco, California, United States, Society for Industrial and Applied Mathematics,
pages, 1998.
[Kleinberg 99a] J. Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM,
46(5):604-632, 1999.
[Kleinberg 99b] J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. The
Web as a Graph: Measurements, Models, and Methods. In Computing and Combinatorics.
Springer, 1627: 1-17, 1999.
[Koschützki et al. 05] D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-
Podehl and O. Zlotowski. Centrality Indices. In &etwork Analysis. Springer Berlin /
Heidelberg. 3418: 16-61, 2005.
[Kumar et al. 06] R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins. Core algorithms
in the CLEVER system. ACM Trans. Internet Technol., 6(2):131-152, 2006.
[Lancichinetti and Fortunato 09] A. Lancichinetti and S. Fortunato. Benchmarks for testing
community detection algorithms on directed and weighted graphs with overlapping
communities. Physical Review E, 80(1):016118, 2009.
[Langville and Meyer 05] A. Langville and C. Meyer. A Survey of Eigenvector Methods for
Web Information Retrieval. SIAM Rev., 47(1):135-161, 2005.
[Langville and Meyer 06] A. Langville and C. Meyer. Google's PageRank and Beyond: The
Science of Search Engine Rankings. Princeton University Press, 2006.
[Latouche et al. 10] P. Latouche, E. Birmelé and C. Ambroise. Bayesian Methods for Graph
Clustering. In Advances in Data Analysis, Data Handling and Business Intelligence.
Springer Berlin Heidelberg, pages 229-239, 2010.
[Lee and Seung 99] D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative
matrix factorization. &ature, 401:788-791, 1999.
175
Bibliographie
[Lee and Seung 01] D. D. Lee and H. S. Seung. Algorithms for non-negative matrix
factorization. In Proceedings of the 13th &eural Information Processing Systems
Conference, pages, 2001.
[Leicht and Newman 08] E. A. Leicht and M. E. J. Newman. Community Structure in
Directed Networks. Physical Review Letters, 100(11):118703, 2008.
[Lempel and Moran 00] R. Lempel and S. Moran. The stochastic approach for link-structure
analysis (SALSA) and the TKC effect. Comput. &etw., 33(1-6):387-401, 2000.
[Liu 06] B. Liu. Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data.
Springer, 2006.
[Lu and Getoor 03] Q. Lu and L. Getoor. Link-based Classification. In Proceedings of the
20th International Conference on Machine Learning (ICML), Washington, DC, USA,
2003.
[Luce and Perry 49] R. Luce and A. Perry. A method of matrix analysis of group structure.
PSYCHOMETRIKA, 14(2):95-116, 1949.
[Ma et al. 08] N. Ma, J. Guan and Y. Zhao. Bringing PageRank to the citation analysis.
Information Processing & Management, 44(2):800-810, 2008.
[MacKay 02] D. J. C. MacKay. Information Theory, Inference & Learning Algorithms.
Cambridge University Press, 2002.
[Macqueen 67] J. B. Macqueen. Some methods of classification and analysis of multivariate
observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics
and Probability, pages 281-297, 1967.
[Manning et al. 08] C. D. Manning, P. Raghavan and H. Schütze. Introduction to Information
Retrieval. Cambridge University Press 2008.
[Maslov and Redner 08] S. Maslov and S. Redner. Promise and Pitfalls of Extending
Google’s PageRank Algorithm to Citation Networks. The Journal of &euroscience,
28(44):11103-11105, 2008.
[McLachan and Krishnan 97] G. McLachan and T. Krishnan. EM Algorithm and Extensions.
Wiley, 1997.
[Modha and Spangler 00] D. S. Modha and W. S. Spangler. Clustering hypertext with
applications to web searching. In Proceedings of the eleventh ACM on Hypertext and
hypermedia, San Antonio, Texas, United States, ACM, pages 143-152, 2000.
[Mokken 79] R. J. Mokken. Cliques, clubs and clans. Quality & Quantity, 13(2):161-
173, 1979.
[Newman 04] M. E. J. Newman. Fast algorithm for detecting community structure in
networks. Physical Review E, 69(6):066133, 2004.
176
Bibliographie
177
Bibliographie
178
Bibliographie
[Yoon and Park 04] B. Yoon and Y. Park. A text-mining-based patent network: Analytical
tool for high-technology trend. The Journal of High Technology Management Research,
15(1):37-50, 2004.
[Zhang et al. 05] Y. Zhang, J. X. Yu and J. Hou. Web Communities: Analysis and
Construction. Springer, 2005.
[Zhou et al. 07] Z.-H. Zhou, H. Li, Q. Yang, L. Yen, F. Fouss, C. Decaestecker, P. Francq and
M. Saerens. Graph Nodes Clustering Based on the Commute-Time Kernel. Advances in
Knowledge Discovery and Data Mining, Springer Berlin / Heidelberg. 4426: 1037-1045.
2007.
[URL 1] http://www.cs.umd.edu/~sen/lbc-proj/LBC.html
[URL 2] http://research.microsoft.com/en-us/um/people/minka/software/fastfit/
179