Discussion :

[jyboo]

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]

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]

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]

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]

euh...

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

[Matthieu Brucher]

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