[C] Numero di link prefissato in un grafo connesso
Ciao ragazzi. Avrei il seguente problema: vorrei generare una matrice random, in cui la probabilità che un nodo si connetta agli altri è uguale a 0.19. In questa rete non vi sono nodi isolati (quindi ogni nodo ha almeno una connessione con un altro nodo).
Le richieste sono che il massimo grado del nodo sia uguale a 6, mentre il numero di link sia uguale a 38.
Io ho svolto nel seguente modo:
(Sperando di non aver commesso errori).
Ciò che sono riuscito ad ottenere è che il grado massimo sia uguale a 6, ma il numero di link è uguale a 46 (quindi non 38).
E' davvero possibile fare in modo che, con la probabilità uguale a 0.19, vi siano 38 link?
Se è si, potreste spiegarmi come fare a modificare il codice affinché sia possibile ottenere tale valore? Vi ringrazio per l'aiuto.
p.s. Per la funzione ran2, generatore di numeri casuali, sto utilizzando il codice che troverete in questo link: http://www.ing.unitn.it/~rigon/FLUIDTUR ... T/random.c
Ho provato a generare numeri casuali utilizzando la funzione rand() al posto di ran2: tuttavia, i numeri generati con
Le richieste sono che il massimo grado del nodo sia uguale a 6, mentre il numero di link sia uguale a 38.
Io ho svolto nel seguente modo:
int i,j, n_links;
double value;
long idum;
idum=-87732434;
// Initialising
for (i = 0; i < 15; i ++ ){
for (j = 0; j < 15; j ++ ){
matrix[i][j] = 0;
matrix[j][i] = 0;
}
}
for(i=0;i<15;i++){
for(j=i+1;j<15;j++){
value=ran2(&idum);
if (value<= 0.19){
matrix[i][j] = 1;
matrix[j][i] = 1;
matrix[i][i] = 0;
matrix[j][j] = 0;
neighbour[i] = j;
neighbour[j] = i;
}
}
}
for(i=0; i<15; i++){
degree[i]=0;
for(j = 0; j < 15; j++){
if(matrix[i][j] == 1&matrix[j][i] == 1){
neighbour[i] = j;
degree[i]++;
}
}
printf("Node: %d Degree: %d\n",i, degree[i]);
}
n_links=0;
for(i=0; i<15; i++){
n_links+=degree[i];
}
printf("Number of links: %d\n", n_links);
degree_min=15;
for(i=0;i<15;i++){
if(degree[i]<degree_min) degree_min=degree[i];
}
// printf("Min degree: %d\n", degree_min);
(Sperando di non aver commesso errori).
Ciò che sono riuscito ad ottenere è che il grado massimo sia uguale a 6, ma il numero di link è uguale a 46 (quindi non 38).
E' davvero possibile fare in modo che, con la probabilità uguale a 0.19, vi siano 38 link?
Se è si, potreste spiegarmi come fare a modificare il codice affinché sia possibile ottenere tale valore? Vi ringrazio per l'aiuto.
p.s. Per la funzione ran2, generatore di numeri casuali, sto utilizzando il codice che troverete in questo link: http://www.ing.unitn.it/~rigon/FLUIDTUR ... T/random.c
Ho provato a generare numeri casuali utilizzando la funzione rand() al posto di ran2: tuttavia, i numeri generati con
(double)rand()/(double)((unsigned)RAND_MAX+1);rendono il grafo non connesso
Risposte
Generando un grafo totalmente a caso non è possibile assicurare che il numero di link sia uguale a 38, e che il grado di ogni vertice sia compreso tra 1 e 6 per ogni vertice. E' comunque possibile calcolare la probabilità che un grafo casuale abbia queste caratteristiche, ma il calcolo non è semplicissimo.
Ovviamente è possibile generare casualmente grafi finché non soddisfano le richieste, ma mi sembra sub-optimale. Forse risulta più semplice allocare casualmente gli archi. Ma per farlo bisogna studiare un po' il problema dal punto di vista probabilistico.
Ovviamente è possibile generare casualmente grafi finché non soddisfano le richieste, ma mi sembra sub-optimale. Forse risulta più semplice allocare casualmente gli archi. Ma per farlo bisogna studiare un po' il problema dal punto di vista probabilistico.
Ti ringrazio per la risposta, vic85.
Posso chiederti se il codice di per sé risulta essere corretto per generare un grafo connesso? Con rand() purtroppo ottengo nodi con grado 0
Inoltre, non so se sia effettivamente corretto considerare l'indice j a partire da i+1:
Esiste una funzione in C in grado di generare numeri casuali uniformemente distribuiti?
Posso chiederti se il codice di per sé risulta essere corretto per generare un grafo connesso? Con rand() purtroppo ottengo nodi con grado 0
Inoltre, non so se sia effettivamente corretto considerare l'indice j a partire da i+1:
for(i=0;i<15;i++){
for(j=i+1;j<15;j++){
value=ran2(&idum);
if (value<= 0.19){
matrix[i][j] = 1;
matrix[j][i] = 1;
matrix[i][i] = 0;
matrix[j][j] = 0;
neighbour[i] = j;
neighbour[j] = i;
}
}
}Esiste una funzione in C in grado di generare numeri casuali uniformemente distribuiti?
Non ho capito cosa serva l'array neighbour, specialmente dato che lo riscrivi tutte le volte. Similmente per l'azzerare la diagonale: è già uguale a zero prima dell'inizio del ciclo.
Non esiste una funzione standard C per fate ciò che cerchi. Il C++ invece ne ha introdotta una, ma poco importa dato che il procedimento non assicura che tu arrivi ad un grafo di quel tipo (di fatto neanche iterando il procedimento all'infinito). Il tuo problema è più algoritmico-probabilistico che implementativo.
Insomma quello è più o meno il modo in cui si può generare un grafo casuale, ma le restrizioni rendono il problema molto più complesso.
Non esiste una funzione standard C per fate ciò che cerchi. Il C++ invece ne ha introdotta una, ma poco importa dato che il procedimento non assicura che tu arrivi ad un grafo di quel tipo (di fatto neanche iterando il procedimento all'infinito). Il tuo problema è più algoritmico-probabilistico che implementativo.
Insomma quello è più o meno il modo in cui si può generare un grafo casuale, ma le restrizioni rendono il problema molto più complesso.
Ti ringrazio, vic85. Rivedrò questa parte con attenzione, così da eliminare le parti superflue. Grazie ancora per l'aiuto.
p.s. Per eliminare o non considerare le autoconnessioni di un nodo, potresti dirmi cosa dovrei aggiungere e/o modificare? Ho modificato il codice in questo modo:
p.s. Per eliminare o non considerare le autoconnessioni di un nodo, potresti dirmi cosa dovrei aggiungere e/o modificare? Ho modificato il codice in questo modo:
for (i = 0; i < 15; i ++ ){
for (j = 0; j < 15; j ++ ){
matrix[i][j] = 0;
matrix[j][i] = 0;
}
}
for(i=0;i<15;i++){
for(j=i+1;j<15;j++){
value=ran2(&idum);
if (value<= 0.19){
matrix[i][j] = 1;
matrix[j][i] = 1;
matrix[i][i] = 0;
matrix[j][j] = 0;
}
}
}
Nel secondo ciclo, è sempre vero che \(\displaystyle i < j \).
Venendo al tuo problema. Quando generi un grafo in maniera casuale, ogni grafo è possibile, ma non tutti i grafi sono ugualmente probabili. Suppongo dal tuo codice che ci siano \(\displaystyle 15 \) vertici, quindi un numero massimo di archi uguale a \(\displaystyle \frac{15 \times 14}{2} = 15\times 7 = 105 \).
Ora, la probabilità di generare un grafo con \(\displaystyle 38 \) archi è uguale a \(\displaystyle P(A = 38) = \binom{105}{38} p^{38}(1-p)^{67} < 0,000017 \) con \(\displaystyle p = 0.19 \), mentre il numero medio di archi è \(\displaystyle \mathbb{E}(A) = 105p = 19,95 \approx 20 \). Ho notato ora che nel tuo codice hai contato gli archi due volte, quindi hai generato un grafo con 23 archi e non 46 (probabilisticamente ancora più improbabile di uno con 38 archi). Nota che \(\displaystyle P(A = 23) = \binom{105}{23} p^{23}(1-p)^{82} \approx 0.07 \).
Data l'improbabilità di beccare un grafo con le caratteristiche cercate usando una generazione casuale e che ogni grafo con 38 archi ha la stessa probabilità di essere generato ti suggerisco di assegnare casualmente i 38 archi piuttosto che generarli con una certa probabilità. Ovviamente nell'assegnazione devi tenere conto delle altre due condizioni.
Venendo al tuo problema. Quando generi un grafo in maniera casuale, ogni grafo è possibile, ma non tutti i grafi sono ugualmente probabili. Suppongo dal tuo codice che ci siano \(\displaystyle 15 \) vertici, quindi un numero massimo di archi uguale a \(\displaystyle \frac{15 \times 14}{2} = 15\times 7 = 105 \).
Ora, la probabilità di generare un grafo con \(\displaystyle 38 \) archi è uguale a \(\displaystyle P(A = 38) = \binom{105}{38} p^{38}(1-p)^{67} < 0,000017 \) con \(\displaystyle p = 0.19 \), mentre il numero medio di archi è \(\displaystyle \mathbb{E}(A) = 105p = 19,95 \approx 20 \). Ho notato ora che nel tuo codice hai contato gli archi due volte, quindi hai generato un grafo con 23 archi e non 46 (probabilisticamente ancora più improbabile di uno con 38 archi). Nota che \(\displaystyle P(A = 23) = \binom{105}{23} p^{23}(1-p)^{82} \approx 0.07 \).
Data l'improbabilità di beccare un grafo con le caratteristiche cercate usando una generazione casuale e che ogni grafo con 38 archi ha la stessa probabilità di essere generato ti suggerisco di assegnare casualmente i 38 archi piuttosto che generarli con una certa probabilità. Ovviamente nell'assegnazione devi tenere conto delle altre due condizioni.
"vict85":
Nel secondo ciclo, è sempre vero che \(\displaystyle i < j \).
Per secondo ciclo, intendi quello in cui creo gli archi con la probabilità?
"vict85":
Suppongo dal tuo codice che ci siano \(\displaystyle 15 \) vertici, quindi un numero massimo di archi uguale a \(\displaystyle \frac{15 \times 14}{2} = 15\times 7 = 105 \).
Si, sto rappresentando un grafo avente 15 vertici, i cui collegamenti sono determinati casualmente.
"vict85":
Ho notato ora che nel tuo codice hai contato gli archi due volte, quindi hai generato un grafo con 23 archi e non 46 (probabilisticamente ancora più improbabile di uno con 38 archi)
Non so se era voluta la generazione di un grafo con 23 arch (sto considerando un grafo indiretto)
Sto sbagliando a generarlo con 23 archi? In realtà, facendo alcune simulazioni (n=50), ho visto che in media il numero di archi generati si aggira intorno a 33-40. Potrebbe essere una soluzione, dividere il numero di link per 2? (potrebbe essere una assurdità... o potrei parlare così per disperazione...)Grazie ancora, vic85, per l'aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo