Discussion :

[gvdmoort]

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.

[pseudocode]

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}

[gvdmoort]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é.

[pseudocode]

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
If (random <= Pi) {
    // creation de l'arc
}else{
    // ne pas creer l'arc
}

[gvdmoort]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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 ?

[pseudocode]

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.

[gvdmoort]

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.