algorithme de construction d'un graphe en étoile

**jyboo** · 15/02/2008, 18h19

Bonjour,
voici mon problème
je développe une application facebook en java, en récupérant des données sur les "amis" de l'utilisateur.

je détermine ensuite une première matrice carré symétrique, qui est la "matrice d'amitié" (qui représente l'utilisateur et ses amis, et s'il sont amis entre eux).

si l'utilisateur est ami avec quelqu'un, c'est représenté par 1, mais aussi si un ami de l'utilisateur est ami avec un autre ami de celui-ci, c'est représenté par 1
par exemple, si l'utilisateur c'est A, qui a 3 amis B C et D, avec B ami de C et D, mais C pas ami avec D, on a:
A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 0
D 1 1 0 0

ensuite, avec ca, on va déterminer la seconde matrice, qui représente le nombre d'amis commun deux à deux
exempl: pour D et C, on regarde toute les valeurs communes pour lesquelles ils sont à 1. on a A et B, amis commun de D et C, donc ils ont 2 amis commun
de proche en proche, on a la seconde matrice:
A B C D
A 0 2 1 1
B 2 0 1 1
C 1 1 0 2
D 1 1 2 0
c'est cette seconde matrice qui va permettre de construire le graphique (tel que je le concois), car elle détermine les distances entre chacun (en les ramenantà une base commune, pour que ca soit relatif parce que quelqu'un qui a 1000 amis et qui a 50 amis commun avec un autre, on peut se douter de leur "proximité")

la difficulté, c'est de construire quelque chose qui respecte plus ou moins la seconde matrice.

il y a fa aire trois choses sur un meme graphique :
- représenter l'amitié entre tout le monde et le l'utitlisateur principal (ca c'est facile)
- représenter chaque personne par une pastille en fonction du nombre d'amis qu'il a
- représenter l'amitié de tout le monde entre eux (ca ca pose problème)

je pense qu'il est possible de faire une sorte de relaxation sur les contraintes, pour avoir une marge de manoeuvre sur les distances de la matrice de distance, mais ensuite, je sais pas trop comment, l'idée est de pouvoir visualiser directement les "groupes" d'amis, qui devraient être visible par interprétation de la matrice des distances...

Si quelqu'un connait un algorithme de ce genre, ou sait comment faire, ca serait G E N I A L

**acx01b** · 15/02/2008, 21h30

ce que tu veux représenter c'est le graphe des liens entre un groupe de personnes sur face book ? et tu veux optimiser l'affichage pour qu'on voit bien des sous groupes se départager

je ne sais pas si tu peux avoir des solutions optimales en temps réel

ce que tu veux c'est un graphe où
pour tout x,y, x et y sont d'autant plus proches à l'écran qu'ils ont d'amis en commun

moi j'oublirais les histoires de matrices et je ferais un algo génétique ou recuit simulé ou un truc du genre

l'idée c'est: on positionne aléatoirement tous les noeuds, puis on boucle en modifiant aléatoirement une partie du graphe, on regarde si le graphe est mieux ou pas après modification, si oui on garde la modif, sinon on l'annule

avec quelques petites heuristiques en 1000 tours de boucles tu dois obtenir quelque chose de pas mal du tout

**pseudocode** · 16/02/2008, 00h35

je vote comme acx01b: oublier la methode avec les matrices de distances et utiliser des algos plus standards de Clustering (CAG, K-means, ...)

**Matthieu Brucher** · 16/02/2008, 15h35

Tu as une matrice de similarités (1 - (sont-ils amis ou pas)), donc passe par un algorithme classique de réduction de dimension, tel que les Laplacian Eigenmaps (si ta matrice est symétrique

) :
- Calcule D^(-1/2)W D^(-1/2) (D étant la matrice des sommes par ligne ou par colonne et W ta matrice des poids)
- Diagonalise cette matrice et récupères les 4 premiers vecteurs propres. L'un sera de poids 1, tu l'élimines (solution évidente au problème).
- Les 2 ou 3 autres vecteurs propres te donneront une répartition des points dans l'espace 2D ou 3D selon ce que tu veux.

La solution de passer par la matrice des distances (géodésiques) est possible, mais potentiellement plus longue et plus coûteuse en temps. De plus, si ton graphe n'est pas connexe, ça ne marche pas, mais je te donne l'autre solution :
- calcule ta matrice de distances (Dijkstra ou Floyd-Warshall)
- diagonalise ta matrice et récupère les 2 ou 3 plus grands vecteurs propres
- ton espace 2D ou 3D sera constitué par ces 2 ou trois vecteurs propres.
C'est un algorithme qui s'appelle Isomap.

Pour certains renseignements complémentaires, ce sera dans ma thèse, ou tu peux regarder sur ma page perso mes publications en français qui traitent en partie de la visualisation de données dans un espace réduit.

**souviron34** · 16/02/2008, 18h17

euh...

Moi je vote comme pseudocode et acx01b : voir les algos de clustering ....

**Matthieu Brucher** · 16/02/2008, 18h20

Une fois l'espace réduit, le clustering est bien plus facile et réalisable

**souviron34** · 16/02/2008, 18h22

sauf que ça prend du temps de calcul... Et pour une appli style Facebook, la réactivité "quasi temps réel" est relativement importante, non ??

**Matthieu Brucher** · 16/02/2008, 18h29

Envoyé par souviron34

sauf que ça prend du temps de calcul... Et pour une appli style Facebook, la réactivité "quasi temps réel" est relativement importante, non ??

Le calcul est plus complexe sur les données brutes. Le problème est aussi connu sous le nom de spectral clustering ; pour faire du clustering, il est nécessaire d'avoir des coordonnées, et c'est ce système de réduction de dimension qui le retourne.

Quant au temps de calcul, il est très faible pour le premier algorithme (une fois la matrice créée, c'est une affaire de secondes pour plus de 2000 points par exemple).

**pseudocode** · 16/02/2008, 18h31

Envoyé par Matthieu Brucher

Le calcul est plus complexe sur les données brutes. Le problème est aussi connu sous le nom de spectral clustering ; pour faire du clustering, il est nécessaire d'avoir des coordonnées, et c'est ce système de réduction de dimension qui le retourne.

Quant au temps de calcul, il est très faible pour le premier algorithme (une fois la matrice créée, c'est une affaire de secondes pour plus de 2000 points par exemple).

C'est un peu équivalent à faire une ACP, non ?

**Matthieu Brucher** · 16/02/2008, 18h47

Sauf que ça fait vraiment son boulot, pas comme une ACP

**pseudocode** · 17/02/2008, 13h11

Envoyé par Matthieu Brucher

Sauf que ça fait vraiment son boulot, pas comme une ACP

flambait

Projeter les données sur la base réduite des vecteurs propres de plus grands poids, ca ressemble quand même rudement au principe de l'ACP.

A quoi correspond la matrice "D^(-1/2).W.D^(-1/2)" que tu utilises ? On dirait une sorte de distance sur le graphe.

**Matthieu Brucher** · 17/02/2008, 13h47

C'est simplement l'étape finale.
L'ACP travaille sur les produits scalaires entre tous les points du graphe, les cartes dont je parle sont calculées à partir de similarités entre certains points du graphe, ce qui permet d'approcher la variété riemannienne de manière correcte (on n'est pas dans un espace euclidien, donc tout ce qu'on fait avec le produit scalaire euclidien n'est pas valable).

La matrice dont je parle est la matrice des similarités pondérées. En cherchant les publications sur le spectral clustering, tu verras de quoi je parle de manière plus exacte.

**pseudocode** · 17/02/2008, 14h06

Envoyé par Matthieu Brucher

La matrice dont je parle est la matrice des similarités pondérées. En cherchant les publications sur le spectral clustering, tu verras de quoi je parle de manière plus exacte.

Je vais me renseigner...