Traduction

[zork]

Bonjour

Comment traduiriez vous ce bout de phrase:
an edge {u,v} from v by randomly and independently choosing u in proportion to the degree of u

perso j'aurai dis (je suis pas sûr du tout)
une arête {u,v} de v vers u qui est choisit aléatoirement et indépendamment de son degré


merci

[Ben314]

Salut,
non, ce n'est effectivement pas du tout ça :
Traduire "in proportion to" par "indépendamment de" c'est clairement n'importe quoi.

Là, si tu t'est pas gouré en recopiant (je trouve le truc un peu bizare) ça te dit que, partant d'un sommet v de ton graphe, tu choisi une des arrêtes {v,u} partant de v et que la proba. de choisir une arrête donnée est proportionnelle au degré de la deuxième extrémité u de l'arrête (donc tu va préférentiellement vers des sommets d'où partent beaucoup d'arêtes)

Perso, ça m'aurais paru plus "naturel" de choisir avec équiprobabilité une des différentes arrêtes, donc avec une proba de 1/degré(v), mais vu que j'ai pas le contexte...

[zork]

ce que j'ai donné est une étape où on ajoute un sommet, l'autre étape est la suivante:
add a new edge {r,s} by independently choosing vertices r and s with probability proportionnal to their degrees

que j'ai traduit par:
ajouter une nouvelle arête {r,s}en choisissant r et s avec une probabilité proportionnelle à leurs degrés

[Ben314]

Mot à mot, ça semble bien ça, mais j'ai du mal à imaginer quel peut bien être l'intérêt du bidule.

Il ne faut clairement pas partir d'un graphe sans aucune arrête (sinon "division by zéro error" concernant le calcul des proba.) et si on part d'un graphe déjà commencé, je vois pas trop l'intérêt du bidule.

Concrètement, c'est sensé servir à construire quoi ton truc ?

[zork]

c'est un schéma d'attachement préférentiel
d'ailleurs il y a un truc que j'ai pas bien compris, dans le procédé de construction on part d'un graphe initial avec un sommet composé d'une boucle. Puis soit on ajoute un sommet avec probabilité p, soit on ajoute une arête

mais à ce moment-là comment savoir quelle probabilité on a? on ne sait jamais si on ajoute un sommet ou une arête?

[Ben314]

c'est un schéma d'attachement préférentiel
d'ailleurs il y a un truc que j'ai pas bien compris, dans le procédé de construction on part d'un graphe initial avec un sommet composé d'une boucle. Puis soit on ajoute un sommet avec probabilité p, soit on ajoute une arête

mais à ce moment-là comment savoir quelle probabilité on a? on ne sait jamais si on ajoute un sommet ou une arête?

Heuuuu....
Là, clairement, si tu utilise le procédé que tu as susnommé, je vois pas comment tu va faire pour ajouter d'autres arêtes que des copies de la boucle initiale vu que les sommets de degré 0 ont une proba nulle d'être pris comme extrémité d'une nouvelle arrête.

Tu peut pas mettre tout le passage en question histoire qu'on y comprenne quelque chose ?

[zork]

le graphe initial composé d'un sommet et d'une boucle est pris considéré de degré 1
Il n'y a pas de sommet de degré 0