Discussion :

[jyboo]

Bonjour,

j'ai une matrice carré symétrique de coefficient compris entre 0 et 1, correpondant à la distance entre deux personnes par exemple (c'est une distance subjective, comme par exemple le degré d'amitié). Plus ca tend vers 1, plus ces personnes sont proches, et 0 correspond à deux personnes non amies.

la première ligne et colonne correspondant à l'élément central. à partir de cet élément central, je vais placer le second élément par rapport à l'élément central en fonction du coefficient correspondant. Pareil ensuite pour le 3e en fonction des points placés précédemment (en privilégiant toujours la distance par rapport à l'élément central avant les autres), et ainsi de suite.

le problème réside dans la construction des coordonnées de tous les éléments: en effet, il est possible qu'il n'y ait pas de solution, et dans ce cas, il faudrait une forme de relaxation sur les "contraintes". deux cas où il n'y a pas de solution: une distance trop grande, ou, au contraire, une distance trop courte.

Ce que j'aimerais (si quelqu'un à une solution), c'est un algorithme qui puisse donner les coordonnées de chacune des personnes, en gérant les cas où il n'y a pas de solution, et s'il est possible de faire ça sous java.

Merci si quelqu'un a une piste...

[m_piou]

Bonjour

la première ligne et colonne correspondant à l'élément central.

La première ligne ou la première colonne?????

Bref. Si j'ai bien compris (arrete moi si je me trompe), un élément va etre associé à un point. Et tu veux symbolisé graphiquement la distance entre ces différents éléments?
Si on associé ton élément central aux oordonnées (0,0), il suffirait de prendre les coefficients entre cet élément et les autres éléments, et de les transformer en coordonnées graphiques (tout en gardant la proportionnalité).
Par exemple, si A est mon élément central, et que le coefficient de distance de B est de 0,56, tu place ta représentation de B à (coordonnée de A + 56).
Et ainsi de suite.

C'est un truc comme ca que tu veux?

Cdlt

[jyboo]

comme c'est une matrice symétrique, c'est la premiere colonne et la premiere ligne
en fait, le problème se situe dans la construction des points: il se peut que les coefficients ne permettent pas d'obtenir une "solution" (pas de point)
exemple: la distance par défaut est de 10 entre deux points. d'après la matrice de coefficient, on a des coefficients pour le point A de 0,4 avec le point B, et 0,4 pour le point C. la distance entre B et C est de 200=> pas de solution
c'est que j'aimerai, c'est une idée pour gérer ces problèmes par exemple, et donc avoir un algo pouvant gérer ca (si possible sous java tant qu'à faire)

[m_piou]

Bonjour,

j'ai du mal à comprendre (désolé) mais je vais quand meme essayé.

Pour déterminer que tu n'as pas de solution, tu vas surement appliquer un critère (de distance de coeff si j'ai suivi).
Du coup, il te suffit de boucler sur tous tes éléments, tu les compare avec les autres éléments, tu testes ton critère et tu agis en conséquence.

Je ne vois pas trop où est le problème.

Cdlt

[jyboo]

alors, je vais tenter de faire une explication claire et en expliquant bien ce que je voudrais
donc, en fait, 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)
ca donne quelque chose comme ca

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1
1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0
1 1 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0
1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0
1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0
1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 1
1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0
1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1
1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0

à partir de cette matrice, je vais déterminer le "degré" d'amitié entre chacun,
c'est a dire que pour chaque couple de personnes, je vais déterminer le nombre d'amis commun rapporter à la moyenne du nombre d'amis qu'ils ont parmi les amis de l'utilisateur (c'est assez difficile de suivre la, je sais).
ci-dessous la matrice du nombre d'amis commun
0 19 16 9 19 16 21 0 15 14 20 20 19 14 11 19 21 17 18 22 21 15 17 22 15
19 0 16 9 16 16 18 1 14 14 17 18 16 13 11 18 18 15 17 19 18 14 15 19 13
16 16 0 8 14 13 16 1 13 11 16 15 14 12 11 15 15 14 15 16 15 12 12 16 10
9 9 8 0 9 10 9 1 9 8 9 10 9 7 6 9 9 9 10 9 9 9 9 9 8
19 16 14 9 0 14 19 1 15 13 17 17 16 13 11 16 18 14 17 19 18 14 16 19 14
16 16 13 10 14 0 15 1 11 13 16 16 14 12 9 14 16 14 16 16 15 13 13 16 11
21 18 16 9 19 15 0 1 15 13 19 19 18 15 11 18 20 16 18 21 20 15 16 21 14
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 14 13 9 15 11 15 1 0 12 13 14 14 11 10 15 14 13 14 15 15 12 14 15 13
14 14 11 8 13 13 13 1 12 0 13 14 13 12 8 14 14 12 14 14 14 11 14 14 11
20 17 16 9 17 16 19 1 13 13 0 19 18 14 11 17 20 17 16 20 19 15 16 20 13
20 18 15 10 17 16 19 1 14 14 19 0 18 14 12 18 20 17 17 20 19 14 17 20 14
19 16 14 9 16 14 18 1 14 13 18 18 0 12 11 17 19 17 15 19 19 13 16 19 14
14 13 12 7 13 12 15 1 11 12 14 14 12 0 7 13 14 13 13 14 13 12 13 14 9
11 11 11 6 11 9 11 1 10 8 11 12 11 7 0 10 12 10 11 11 10 8 9 11 8
19 18 15 9 16 14 18 1 15 14 17 18 17 13 10 0 18 15 16 19 19 14 16 19 15
21 18 15 9 18 16 20 1 14 14 20 20 19 14 12 18 0 17 17 21 20 15 17 21 14
17 15 14 9 14 14 16 1 13 12 17 17 17 13 10 15 17 0 14 17 16 13 15 17 13
18 17 15 10 17 16 18 1 14 14 16 17 15 13 11 16 17 14 0 18 17 13 14 18 13
22 19 16 9 19 16 21 1 15 14 20 20 19 14 11 19 21 17 18 0 21 15 17 22 15
21 18 15 9 18 15 20 1 15 14 19 19 19 13 10 19 20 16 17 21 0 14 17 21 16
15 14 12 9 14 13 15 1 12 11 15 14 13 12 8 14 15 13 13 15 14 0 12 15 11
17 15 12 9 16 13 16 1 14 14 16 17 16 13 9 16 17 15 14 17 17 12 0 17 14
22 19 16 9 19 16 21 1 15 14 20 20 19 14 11 19 21 17 18 22 21 15 17 0 15
15 13 10 8 14 11 14 1 13 11 13 14 14 9 8 15 14 13 13 15 16 11 14 15 0

mais maintenant, à partir de cette matrice, il faudrait que je représente un graphe étoilé centré sur l'utilisateur en cours qui représente au mieux cette matrice. sauf que j'ai du mal à concevoir un algorithme efficace pour représenter tout ca, sachant que chacun des personnes sont représentées par des "pastilles" dont la taille dépend du nombre d'amis qu'ils ont.

l'idée, c'est de trouver un algorithme qui puisse positionner chacune des personnes en suivant au mieux cette matrice sur un graphe en 2D. Mais c'est sur ce point que je bloque.

voilà, merci merci pour tout

[m_piou]

Bonjour,

Que de chiffres que chiffres...... Bref!

Pour voir si j'ai bien compris, matrice[0][1] représente le nombre d'amis commun qu'il a en commun avec matrice[0][0] et matrice[2][1] représente le nombre d'amis commun qu'il a avec matrice[2][0] ?????

Si "Utilisateur principal" est représenté au centre du dessin, tu peux essayer de jouer avec des distances linéaires pour les relations utilisateur principal <-> autres et avec des distances radiales pour les relation autres<-> autres.

Par exemple, prenons U l'utilisateur principal et a1, a2 et a3 les autres.
U <-> a1 = 20;
U <-> a2 = 10;
U <-> a3 = 15;
a1 <-> a2 = 3;
a1 <-> a3 = 8;
a2 <-> a3 = 5;
Parlons en pixel (par exemple).
Tu met a1 à 200 de distance avec U.
Tu met a2 à 100 de distance avec U.
Tu met a3 à 150 de distance avec U.

Tu met donc a1 sur l'axe des abcisses.
Et ensuite tu tournes autour de U pour placer tes autres.
Genre un truc comme
angle_de_la_droite_a2-U_par_rapport_aux_absicces = 3
angle_de_la_droite_a3-U_par_rapport_aux_absicces = 8.

Si tu relie toutes les pastilles, t'auras un graphe.

Un truc comme ca peut etre.

Cdlt