Ricerca prossimità in grafo e costo computazionale

[Marte8400]

Ciao a tutti,

scusate innanzitutto per la lunghezza del post.

Mi sono imbattuto nel seguente problema:

"Supponendo di avere una rete composta da nodi (dell'ordine di un milione) ed archi che rappresentano i collegamenti tra di essi, descrivere un algoritmo che, dati in input n nodi della rete, restituisce in output coppie di nodi non collegati direttamente ma che hanno alta probabilità di avere un'utilità a diventarlo (pensiamo ad esempio al suggerimento delle amicizie di facebook). Stimare l'occupazione in memoria ed il tempo d'esecuzione in secondi del programma".

Le ipotesi aggiuntive che ho fatto sono le seguenti:

1) Nodi della rete pari a n=10^6

2) Nodi i,j con alta probabilità di avere un'utilità nel collegarsi se nodo i e j condividono almeno un ulteriore nodo. Ovvero se esiste arco (i,k) e arco (j,k)

3)Suppongo di aver già la matrice d'incidenza che descrive la topologia della rete di dimensione n*m con m pari agli archi possibili che al massimo sono m=n*(n-1)/2 per grafo completamente connesso. Ho stimato che l'occupazione in memoria di tale matrice, composta solo da interi (2 byte), sia dell'ordine di 10^18 byte per n=10^6, poiché ho n righe e m colonne con m=n*(n-1)/2 nel caso peggiore, quindi O(n^3) in totale. Possibile questa dimensione? Sbaglio il ragionamento?

4) Suppongo che la frequenza di clock del calcolatore sia di 2 GHz

Ho affrontato il problema nel seguente modo:

a) Dati n nodi in input le coppie da verificare sono n(n-1)/2

b) Per ogni nodo in input ricerco gli "1" (ovvero i collegamenti nodo-arco) scorrendo tutta la corrispondente riga sulla matrice d'incidenza
c) Supponiamo di scorrere la riga del nodo x. Se trovo un "1" scorro la colonna corrispondente (che è relativa ad un arco) fino a trovare l'altro "1" (ogni colonna ha solo due celle valorizzate ad "1" poiché rappresenta il collegamento dell'arco fra due nodi) della colonna, supponendo che si trova sulla riga y.
d) Di conseguenza i nodi x ed y sono collegati direttamente. Scorro ora la lista riga di y, se trovo altri "1" scorro la colonna corrispondente, fino a trovare l'ulteriore "1", supponiamo sulla riga z. Di conseguenza x e z, seppur non collegati direttamente, hanno un'alta probabilità di avere un'utilità nel collegarsi poiché hanno un nodo "in comune", e li inserisco nella lista di coppie da restituire in output.
e) Itero i passi da b) a d) per tutti i nodi forniti in input.

Spero di aver reso l'idea del procedimento che mi è venuto in mente
Vi sembra un approccio corretto?

Sapreste fornirmi qualche suggerimento sul tempo d'esecuzione e avvallare il ragionamento oppure proporre un'idea migliore?

Grazie per il vostro tempo,
P.

[Intermat]

Mi sembra che scritto in questo modo l'algoritmo abbia una complessità dell'ordine di $n^3$. Forse, ma non ne sono sicuro, si potrebbe fare qualcosa meglio (dato che la matrice è simmetrica). Una "misurazione" più precisa potresti ottenerla applicando, per ogni coppia $(s,t)$ [sono $n*(n-1)/2$], l'algoritmo di Dijkstra (pesando ogni arco del grafo con $c(i,j)=1$). In questo modo potresti calcolare quanto sono (effettivamente) distanti i due nodi. In questa seconda ipotesi la complessità, se non ricordo male, dovrebbe essere nell'ordine di $n^4$. Mi pare di poter dire che in entrambi i casi la complessità del problema dipende da $n$ in modo polinomiale.