Distribution non uniforme

Bonjour à tous,

Je devrais implémenter un modèle de graphe connu sous le nom de SmallWorld (cf. Kleinberg http://dl.acm.org/citation.cfm?id=335325) où des sommets sont reliés à d'autres de la manière suivante:

Soit un coefficient r >= 0, et d(u,v) la distance entre u et v, la probabilité qu'un arc relie u à v est proportionnelle à [d(u,v)]^-r.

Si r=0, cette probabilité est donc uniforme pour tous les points. Si r augmente, les points adjacents sont de plus en plus serrés autour de u, ou autrement dit, les arcs joignant des points lointains sont de plus en plus rare.

Le texte de Kl. précise: To obtain a probability distribution, we divide this quantity (d(u,v)^-r) by the appropriate normalizing constant (Sum)v[d(u,v)]^−r; we will call this the inverse rth-power distribution.

Là, je décroche.

Pour chaque sommet u du graphe, je dois en choisir n autres dans l'ensemble des autres sommets pour les relier à u. Comment procéder pour que la probabilté en question soit respectée ?

Si quelqu'un a une piste...

Cordialement,

G.

Citation:

---

Envoyé par gvdmoort

Le texte de Kl. précise: To obtain a probability distribution, we divide this quantity (d(u,v)^-r) by the appropriate normalizing constant (Sum)v[d(u,v)]^−r; we will call this the inverse rth-power distribution.

Là, je décroche.

---

Cette phrase dit simplement qu'il faut appliquer un coefficient d'échelle à toutes les mesures, afin d'en faire une loi de probabilité.

- a chaque arc #i partant de U est associé une mesure Mi=d(U,Vi)^-r
- La probabilité Pi que l'arc #i existe est une valeur entre 0 et 1
- La somme des probabilités Pi vaut 1

=> Pi = Mi / somme_j {Mj}

Citation:

---

Envoyé par pseudocode

Cette phrase dit simplement qu'il faut appliquer un coefficient d'échelle à toutes les mesures, afin d'en faire une loi de probabilité.

- a chaque arc #i partant de U est associé une mesure Mi=d(U,Vi)^-r
- La probabilité Pi que l'arc #i existe est une valeur entre 0 et 1
- La somme des probabilités Pi vaut 1

=> Pi = Mi / somme_j {Mj}

---

Merci, ça m'éclaire quand au fait que cette mesure n'est pas elle-même la probabilité, et qu'il faut connaître cette mesure pour tous les éléments de l'ensemble pour en déduire la probabilité.

À présent, pratiquement, si je dois attribuer à U n arcs de ce type, je fais

Code:

---

1 2 3 4 5

c = 0 tant que c < n pour chaque Vi de l'ensemble des sommets \ {U} lier U à V selon Pi si oui, c++

---

en prenant soin d'itérer en (3) sur selon un ordre aléatoire différent à chaque fois.

Mais ce que je comprends pas, c'est comment déterminer d'établir l'arc, ou non, en fonction de la probabilité.

Citation:

---

Envoyé par gvdmoort

en prenant soin d'itérer en (3) sur selon un ordre aléatoire différent à chaque fois

---

Tu peux iterer dans l'ordre que tu veux, aleatoire ou non.

Citation:

---

Mais ce que je comprends pas, c'est comment déterminer d'établir l'arc, ou non, en fonction de la probabilité.

---

Le moyen le plus simple c'est d'utiliser un generateur aleatoire uniforme, generalement la fonction "random" du langage de programmation.

Code:

---

1 2 3 4 5 6

If (random <= Pi) { // creation de l'arc }else{ // ne pas creer l'arc }

---

Citation:

---

Envoyé par pseudocode

Le moyen le plus simple c'est d'utiliser un generateur aleatoire uniforme, generalement la fonction "random" du langage de programmation.

Code:

---

1 2 3 4 5 6

If (random <= Pi) { // creation de l'arc }else{ // ne pas creer l'arc }

---

---

Comme quoi il ne faut pas toujours chercher midi à quatorze heures :roll:

Citation:

---

Envoyé par pseudocode

Tu peux iterer dans l'ordre que tu veux, aleatoire ou non.

---

Là par contre, je ne suis pas sûr; typiquement, si mon ensemble est constitué des clés d'un hachage, elles seront probablement toujours parcourues dans le même ordre. Si je construis un tel graphe en attribuant n arcs à chaque sommet, tous les sommets ne vont-ils êtres raccordés aux premiers qui apparaissent lors de l'itération ?

Citation:

---

Envoyé par gvdmoort

Là par contre, je ne suis pas sûr; typiquement, si mon ensemble est constitué des clés d'un hachage, elles seront probablement toujours parcourues dans le même ordre. Si je construis un tel graphe en attribuant n arcs à chaque sommet, tous les sommets ne vont-ils êtres raccordés aux premiers qui apparaissent lors de l'itération ?

---

Je n'ai pas lu la publication que tu as cité dans le 1er post. Donc je dis peut-être des bétises.

Mais à mon sens, tant que la création d'un arc est aléatoire (random) alors peu importe l'ordre de construction du graphe.

Citation:

---

Envoyé par pseudocode

Je n'ai pas lu la publication que tu as cité dans le 1er post. Donc je dis peut-être des bétises.

---

Il est plus probable que c'est moi qui en raconte ;)

Un grand merci de toute façon.