Kako algoritam brzog odvijanja otkriva zajednice u velikim mrežama

Analiza društvenih mreža uključuje proučavanje obrazaca u velikim mrežama iz stvarnog života koje se sastoje od milijuna čvorova. Ako imate osnovno znanje teorije grafova, možete izvršiti ove analize.

Digitalni svijet otvorio je potpuno drugačiji način stvaranja odnosa. Također je oslobođen ocean podataka koje možemo analizirati kako bismo bolje razumjeli ljudsko ponašanje.

Podaci na društvenim mrežama odnose se na sve sirove uvide i informacije prikupljene iz aktivnosti pojedinca na društvenim mrežama. Možemo stvoriti mreže od ovih aktivnosti na društvenim mrežama kako bismo stekli bolju percepciju te osobe.

Te se mreže mogu široko kretati, a mogu obuhvaćati vaše prijatelje na Facebooku, proizvode koje ste nedavno kupili na Amazonu, tweetove koji su vam se svidjeli ili koje ste proslijedili ponovo, vašu omiljenu hranu koju ste naručili iz Zomata, pretragu koju ste izvršili na Googleu ili sliku koju ste nedavno lajkali na Instagramu .

Tvrtke koriste ove mreže za razvrstavanje svojih korisnika u različite skupine. Ovo im pomaže

  • raditi istraživanje tržišta
  • generirati potencijalne kupce
  • bolje služiti svojim kupcima
  • pronalaženje i dijeljenje fotografija i videozapisa
  • otkrijte i razgovarajte o trendovskom sadržaju
  • dijeliti informacije o uslugama i restoranima
  • povežite se s drugima oko zajedničkog interesa ili hobija
  • i više.

Popis je prilično beskrajan.

Prije nego što uđemo previše u korov, hajde da brzo razbijemo razliku između različitih komponenata mreže.

Što je mreža?

Mreža je mreža međusobno povezanih osobnih odnosa. Na primjer, različiti pojedinci mogu komunicirati jedni s drugima u grupi društvenih medija putem dinamične mreže odnosa.

Mreža se sastoji od čvorova (pojedinačni akteri, ljudi ili stvari unutar mreže) i veza , rubova ili veza (odnosi ili interakcije) koji ih povezuju.

Što je grupa?

Reicher SD u Određivanju kolektivnog ponašanja opisuje skupinu kao skup pojedinaca koji sebe smatraju grupom. Članovi iste skupine imaju skup zajedničkih uvjerenja i ponašanja.

Što je zajednica?

Prema Davidu W. McMillanu ( Sense of Community: A Definition and Theory ) , zajednica se može definirati kao sljedeće:

Osjećaj zajedništva je osjećaj pripadnosti pripadnicima, osjećaj da su članovi važni jedni drugima i grupi i zajednička vjera da će potrebe članova biti zadovoljene njihovom predanošću da budu zajedno. "

Zajednice ili podjedinice su podmreže u mreži koje su visoko povezani čvorovi.

Zajednica ukazuje na postojanje unutarnjih struktura koje imaju posebna obilježja ili igraju istu ulogu u mreži.

Jako povezane skupine pojedinaca ili objekata unutar ovih mreža su zajednice. Obično leži na sjecištu mreže i skupine.

Sad kad imamo jasnu ideju što je mreža, grupa i zajednica, zaronimo dublje u to kako su te mreže podijeljene u male zajednice.

Osvrnut ćemo se na popularni algoritam brzog odvijanja . Vincent C. Blondel i koautori rada uspoređivali su ovaj algoritam s drugim algoritmima za otkrivanje zajednice. Otkrili su da ovaj algoritam nadmašuje svaki drugi algoritam u velikim mrežama.

Što je algoritam brzog odvijanja?

Algoritam brzog odvijanja korišten je za identificiranje jezičnih zajednica u belgijskoj mreži mobilnih telefona od 2,6 milijuna korisnika.

Također je korišten za analizu mrežnog grafa od 118 milijuna čvorova i više od milijarde veza.

Identificiranje zajednica u tako velikoj mreži trajalo je samo 152 minute. Dakle, ovaj algoritam je istovremeno brz i učinkovit.

Kako algoritam funkcionira

Algoritam radi u dvije faze:

Faza 1

  1. Dodijelite različitu zajednicu svakom čvoru u mreži.
  2. Zatim, za svaki čvor, ja smatra čvora j i ocjenjuje dobitak u modularnosti uklanjanjem čvor I. iz svoje zajednice i stavljanje u zajednici j.
  3. Čvor i smješten je u zajednicu za koju dobiva maksimalnu modularnost, ali dobitak bi trebao biti pozitivan. Ako je dobitak negativan, tada čvor i ostaje u istoj zajednici.

Faza 2

  1. Druga faza algoritma sastoji se u izgradnji nove mreže čiji su čvorovi sada zajednice pronađene tijekom prve faze. Dakle, čvorove gradimo spajanjem svih čvorova u zajednici kao jednog čvora.
  2. Težine veze između čvorova daju se zbrojem težina veza između čvorova u odgovarajuće dvije zajednice.
  3. Veza između čvorova iste zajednice dovodi do samo-petlji za zajednicu u novoj mreži.
  4. Ponavljajte fazu 1 dok se ne mogu postići daljnja poboljšanja.

Kako se izračunava dobitak u modularnosti

Kvaliteta particije ( Q ) mjeri se modularnošću (aka modularnost particije). Njegova je skalarna vrijednost između -1 i 1 i mjeri gustoću veza unutar zajednica u usporedbi s vezama između zajednica.

Dobitak u modularnost (ΔQ) dobiven pomicanjem izoliranu čvor I u zajednici C može se lako izračunati pomoću:

Σin je zbroj težina karika unutar C.

Σtot je zbroj težina veza koje padaju na čvorove u C.

ki je zbroj težina veza od i do čvora u C.

m je zbroj težina svih veza u mreži.

Dobit u modularnosti procjenjuje se uklanjanjem i iz njegove zajednice i premještanjem u susjednu zajednicu. Ako je dobitak pozitivan, tada se taj čvor postavlja u susjednu zajednicu.

Suho pokretanje algoritma

U mreži s lijeve strane (15 čvorova) prvo dodijelimo jedinstvenu zajednicu svakom čvoru. Zatim procjenjujemo modularnost svakog čvora i preusmjeravamo zajednicu na temelju dobitka. To se naziva optimizacija modularnosti .

U sljedećoj fazi gradimo čvorove spajanjem svih čvorova u toj zajednici u jedan čvor. U zelenoj zajednici imamo ukupno 5 čvorova i između njih je ukupno 7 rubova.

Dakle, nakon agregacije zajednice , težina samo-petlje zelenog čvora bit će 14 (7 * 2 jer je dvosmjerna veza). Slično tome, težina samo-petlje crvenog čvora bit će 16, plavi čvor 4, a svijetloplavi čvor 2.

Težina ruba između zelenog i plavog čvora bit će 4, budući da nakon zelene i plave zajednice postoje ukupno 4 ruba nakon optimizacije modularnosti.

U sljedećem koraku ponovno procjenjujemo modularnost novih čvorova i ponovno radimo isti postupak.

Napokon, dobivamo dvije zajednice, zelenu i svijetloplavu. Zelena zajednica ima 26 samo-petlji, jer između čvorova zelene zajednice postoji ukupno 13 rubova. I imamo 12 rubova u svijetloplavoj zajednici, ukupno 24 samopetlja.

Prednosti algoritma

  1. Njegovi su koraci intuitivni i jednostavni za provedbu, a ishod je bez nadzora.
  2. Algoritam je izuzetno brz. Računalne simulacije na vrlo ogromnim modularnim mrežama sugeriraju da je njegova složenost linearna na tipičnim i rijetkim podacima. To je možda zato što je dobitak u modularnosti lako izračunati, a broj zajednica drastično se smanjuje nakon samo nekoliko prolaza.

Ograničenja algoritma

  1. Optimizacija modularnosti ne uspijeva identificirati zajednice manje od određene razmjere. Dakle, to uzrokuje ograničenje razlučivosti zajednice izračunato koristeći pristup optimizacije modularnosti.
  2. Za male mreže vrlo je mala vjerojatnost da se dvije odvojene zajednice mogu spojiti pomicanjem svakog čvora.

Zaključak

Ako ste toliko dugo visjeli tamo ... hvala! Nadam se da su za vas postojale dragocjene informacije.

Dakle, sada znate kako funkcionira algoritam brzog odvijanja i da je izuzetno učinkovito otkrivati ​​zajednice u vrlo velikim mrežama.

Način na koji izračunava dobitak u modularnosti čini da algoritam nadmašuje svaki drugi algoritam. Pošaljite mi napomenu ako vam se učini korisnom ili imate dodatnih pitanja.

Hvala na čitanju!