Despre retele sociale

Cred ca toata lumea a auzit de cel putin unul din numele: YouTube, hi5 , Facebook, Flikr, Yahoo360 , Twitter, LinkedIn.

Ce este o retea sociala de fapt? Este vorba de o structura formata din noduri ce pot reprezenta oameni sau organizatii si legaturile dintre ele. Legaturile pot avea diferite semnificatii. Se considera o legatura intre 2 astfel de noduri atat cand este vorba de 2 persoane ce au o relatie de prietenie, dar si cand o persoana primeste un comentariu (la videoclip, profil, poze), un raspuns (videoclip-youtube), un semn (signs-hi5), sau o recomandare(LinkedIn).
Considerand astfel un nod pentru fiecare persoana sau organizatie si un arc fiecare legatura intre 2 noduri, se obtine un graf.

Am avut de curand de redactat o tema ce dorea explorarea relatiilor dintr-o retea sociala si salvarea lor intr-un format structurat (xml). Ce am realizat facand aceasta tema, este pe de-o parte numarul mare al retelelor sociale existente dar si faptul ca datorita diferitelor tipuri de legaturi existente si numarului mare de persoane inscrise in aceste retele, grafurile sunt
extraordinar de complexe. Cum am putea atunci face o parcurgere in-un astfel de graf cat mai eficient? Well, depinde ce ne intereseaza. Pentru relatiile unei anumite persoane(ca in cerinta) se poate merge accesand prietenii si celelate tipuri de relatii oferite de reteaua sociala, printr-o parcurgere in latime pana la adancimea ceruta. Problema va creste insa semnificativ cu cat adancimea creste.

Ce se intampla insa daca se doreste toata baza de date existenta?
Inainte de a primi tema de retele sociala, am realizat o aplicatie de lua baza de date de utilizatori de pe un site, plecand de la id-ul acestora. Partea foarte neplacuta era ca pentru toate persoanele ce si-au sters contul, id-ul lor a ramas nefolosit. Ca urmare la fiecare pas se verifica intai ca id-ul este valid, rezultand un overhead in plus. (Numarul de id-uri mergea intre 1 si 250mii, relativ mic fata de retele sociale precum Hi5, Facebook sau LinkedIn si totusi extragerea intregii baze de date dura pana la 8 ore)
O solutie de optimizare ar fi fost sa se faca plecarea de la un anumit user si accesand prietenii lui, apoi prietenii acestora s.a.m.d. Insa solutia nu garanta obtinerea bazei de date complete.
O solutie de mijloc, a fost sa se faca la inceput o parcurgere pe id-uri, astfel stabilind id-urile valide, apoi urmatoarele sa foloseasca datele de la prima rulare. Cu fiecare noua parcurgere se si actualiza noua lista de id-uri, in vederea unor noi eliminari. In plus, folosind faptul ca id-urile pierdute nu erau refolosite (fapt total ineficent), periodic puteam verifica aparitia de noi id-uri valide pornind de la id-ul maxim valid.


O problema mai complexa insa: Cum ati extrage intreaga baza de date de pe o retea sociala precum Hi5 sau LinkedIn cat mai eficient?

Tags: programare, retele sociale