Discussion :

[Lupa99]

Bonjour,

Je cherche à implémenter le modèle de Barabasi-Albert (en python, mais ce n'est pas très important ici). Voici de quoi il s'agit : https://fr.wikipedia.org/wiki/Mod%C3...ert#Algorithme.
Mais le problème c'est que je ne comprend pas comment faire.

Mon problème de compréhension peut se reformuler ainsi :

Comment choisir dans une liste [1,...,n] un et un seul élément selon une loi de probabilité fixé non uniforme (sinon on tire un nombre aléatoire et le tour est joué) ?
J'ai accès à une liste [p(1),...,p(n)] de probabilités associés.

Ma première idée : parcourir la liste, choisir un nombre aléatoire N (entre 0 et 1), si N>p(i) alors on choisit i, sinon on réitère. Mais j'ai l'impression que cela va favoriser le début de liste au dépend de la fin, et donc baiser le résultat.
Ou alors : je tire un nombre k uniformément entre 1 et n, je tire un second nombre N que je compare à p(k), si N >p(k) alors je continu le programme, sinon je retire un nombre k, puis un nombre N... ?

(Il y a t-il déjà une fonction en python ?)

je vous remercie par avance !

[wiwaxia]

Bonjour,

... Mon problème de compréhension peut se reformuler ainsi :

Comment choisir dans une liste [1,...,n] un et un seul élément selon une loi de probabilité fixée non uniforme (sinon on tire un nombre aléatoire et le tour est joué) ?
J'ai accès à une liste [p(1),...,p(n)] de probabilités associés ...

Puisque ton tirage pseudo-aléatoire porte sur un nombre fini (N) d'issues, tu peux l'obtenir comme suit, après constitution d'un tableau bidimensionnel dont
a) la première ligne contient les probabilités (p_k) arbitrairement choisies de chacun des termes d'indice (k), sans souci de normalisation;
b) la deuxième, le quotient de leur somme cumulée jusqu'au rang considéré par le total de tous les termes (soit donc un réel compris entre zéro et l'unité):
q = S_i=1^i=k(p_i) / S_T , avec S_T = S_i=1^i=N(p_i)

Tu dois obtenir au niveau de la deuxième ligne: T[2, 0] = 0 et T[2, N] = 1

Exemple: pour N = 10 termes associés à une loi de probabilité de la forme p_k = k²*(N + 1 - k)² , on obtient:

Code :

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

1
2
3
4
 
Pk = T[1, k] =     100    324    576    784    900    900    784    576    324    100  %  
Sk =               100    424   1000   1784   2684   3584   4368   4944   5268   5368  
qk = T[2, k] =    1.86   7.90  18.63  33.23  50.00  66.77  81.37  92.12  98.14 100.00  %

Un simple appel du générateur de nombres PA permet alors de tirer le rang du terme choisi:

Code :

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

1
2
3
 
r:= Random;                      i:= 1;
REPEAT Inc(i) UNTIL (T[2, i]>r); k:= i - 1;

[Lupa99]

Merci beaucoup pour votre réponse !
C'est très clair