Lezioni 6 7

RETI RANDOM

RICHIAMI DI MATEMATICA COMBINATORIA

Due insiemi di oggetti si possono combinare in base a dei gruppi n membri e in base appunto a questi due elementi,( il numero di oggetti che vogliamo combinare e la cardinalità dei gruppi che vogliamo creare) possiamo sapere quante sono le combinazioni possibili.
Prendiamo per esempio un gruppo di cinque elementi A B C D E vediamo che queste sono le possibili combinazioni in gruppi di tre. Prendiamo A la combiniamo con tutte le possibili coppie, prendiamo B la combiniamo con le possibili coppie che non sono già state usate e infine C e quindi otteniamo che in totale abbiamo 10 possibili combinazioni.
Sostanzialmente abbiamo preso il numero dei nostri elementi, siccome partivamo da un primo elemento e volevamo combinare quel elemento con tutti gli altri quindi sostanzialmente abbiamo fatto cinque per quattro, quindi abbiamo moltiplicato il primo elemento per tutti gli altri elementi e n meno uno. Secondo giro facciamo n meno due perché dobbiamo moltiplicare tutto quello per gli elementi che ancora sono rimasti, però se noi consideriamo questa serie di moltiplicazioni, quindi n per n meno uno per n meno k fino a k essere il numero di gruppi che vogliamo costruire. Noi andiamo anche a creare tutti i possibili gruppi permutati quindi dobbiamo togliere le permutazioni dei gruppi di tre. Sapete che una permutazione è data dal fattoriale di un certo numero quindi il fattoriale di tre, è uno per due per tre. Quindi è molto semplice, noi sostanzialmente prendiamo n lo moltiplichiamo tante volte fino ad arrivare alla cardinalità del gruppo che ci interessa, ogni volta decrementiamo di due e poi dividiamo per il fattoriale della cardinalità dei gruppi che abbiamo.

RETI CASUALI

reti casuali come si possono costruire queste reti casuali o random? L’idea di base è molto semplice noi abbiamo l’insieme n di nodi e li dobbiamo connettere fra loro questi si collegheranno in modo casuale e in base alla proprietà ci avvicineremo sempre di più a tutte le possibili combinazioni di questi n nodi che prendiamo in considerazione quindi vediamo che all’aumentare della probabilità aumenta il livello di connessione di questi nodi quindi del grafo. Ricordiamo inoltre che i primi lavori in questo ambito sono legati al lavoro di Erdos and Renyi sulla costruzione di grafi casuali.

Quindi noi se ci interessiamo appunto ai grafi che sono generati casualmente partiamo da n nodi una prima cosa che possiamo mettere in luce è che il numero di tutti i possibili archi che ho di connessione fra i nodi è dato sostanzialmente da n per n-1 fratto 2, che è anche chiamato coefficiente binomiale. Quindi non abbiamo fatto nient’altro che fare la combinazione di tutti i possibili nodi n in gruppi di due.

Notiamo subito, che siccome noi non consideriamo uguali le combinazioni il quale l’ordine degli elementi è stato permutato (è quella la ragione per cui dividiamo per due) quindi consideriamo questo collegamento come simmetrico. Il fatto che il nodo A sia collegato al nodo B è la stessa cosa del fatto che il nodo B sia collegato al nodo A, cioè la relazione che c’è fra di loro.

Questo va per esempio molto bene è se descriviamo una rete di relazione fra individui perché è chiaro che se io conosco un individuo quello conosce anche me, poi in realtà già ad esempio le reti sociali dimostra che comunque poi dipende un po’, perché poi questa è di solito l’interpretazione che si da della nozione di conoscere una persona però forse un pò dipende da quello che intendiamo per conoscenza infatti se voi guardate degli studi sulle reti sociali i risultati variano anche in base a come io ho definito la nozione di conoscenza ( solo quelli che conosco per nome, a cui darei del tu) Se invece sto analizzando la rete delle comunicazioni che avvengono per e-mail fra individui, invece non siamo in un caso di questo tipo perché se si manda una mail a tizio è chiaro che lui non necessariamente ha fatto lo stesso.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License