Kuinka nopeasti avautuva algoritmi tunnistaa yhteisöt suurissa verkoissa

Sosiaalisten verkostojen analyysiin kuuluu mallien tutkiminen suurissa tosielämän verkoissa, jotka koostuvat miljoonista solmuista. Jos sinulla on perustiedot graafiteoriasta, voit suorittaa nämä analyysit.

Digitaalinen maailma on avannut aivan toisenlaisen tavan luoda suhteita. Se on myös vapauttanut valtameren tietoja, joita voimme analysoida saadaksemme paremman käsityksen ihmisten käyttäytymisestä.

Sosiaalisen median tiedot tarkoittavat kaikkia yksilön sosiaalisen median aktiviteeteista kerättyjä raaka oivalluksia ja tietoja. Voimme luoda verkostoja näistä sosiaalisen median toiminnoista saadaksemme paremman käsityksen kyseisestä henkilöstä.

Nämä verkot voivat vaihdella laajasti, ja niihin voivat kuulua Facebook-ystäväsi, äskettäin Amazonista ostamasi tuotteet, suosikkisi tai uudelleentwiittasi twiitit, Zomatolta tilaamasi suosikkiruokasi, Googlessa tekemäsi haku tai hiljattain tykätty kuva Instagramissa .

Yritykset käyttävät näitä verkkoja käyttäjien luokittelemiseen eri ryhmiin. Tämä auttaa heitä

  • tehdä markkinatutkimuksia
  • tuottaa viitteitä
  • palvelemaan paremmin asiakkaitaan
  • etsiä ja jakaa valokuvia ja videoita
  • löytää ja keskustella nousevasta sisällöstä
  • jakaa tietoja palveluista ja ravintoloista
  • olla yhteydessä muihin kiinnostuksen kohteisiin tai harrastuksiin
  • ja enemmän.

Luettelo on melko loputon.

Ennen kuin pääsemme liian rikkaruohoon, hajotetaan nopeasti ero verkon eri komponenttien välillä.

Mikä on verkko?

Verkko on toisiinsa yhteydessä olevien henkilökohtaisten suhteiden verkko. Esimerkiksi eri henkilöt voivat kommunikoida keskenään sosiaalisen median ryhmässä dynaamisen suhteiden verkon kautta.

Verkko koostuu solmuista (yksittäisistä toimijoista, ihmisistä tai verkon sisällä olevista asioista) ja niitä yhdistävistä siteistä , reunoista tai linkeistä (suhteista tai vuorovaikutuksista).

Mikä on ryhmä?

Reicher SD ryhmässä Kollektiivisen käyttäytymisen määrittäminen kuvaa ryhmää kokoelmana yksilöitä, jotka pitävät itseään ryhmänä. Saman ryhmän jäsenillä on joukko yhteisiä uskomuksia ja käyttäytymistä.

Mikä on yhteisö?

David W.McMillanin ( Sense of Community: A Definition and Theory ) mukaan yhteisö voidaan määritellä seuraavasti:

Yhteisöllisyys on tunne, että jäsenillä on yhteenkuuluvuus, tunne, että jäsenillä on merkitystä toisilleen ja ryhmälle, ja yhteinen usko siihen, että jäsenten tarpeet täytetään sitoutumalla olemaan yhdessä.

Yhteisöt tai alayksiköt ovat verkon aliverkkoja, jotka ovat hyvin yhteydessä toisiinsa.

Yhteisö ilmoittaa sisäisten rakenteiden olemassaolon, joilla on erityispiirteitä tai joilla on sama rooli verkossa.

Näiden verkkojen sisällä läheisesti toisiinsa kytkeytyneet yksilöryhmät tai esineet ovat yhteisöjä. Se on yleensä verkon ja ryhmän leikkauspisteessä.

Nyt kun meillä on selkeä käsitys siitä, mikä verkosto, ryhmä ja yhteisö on, sukelkaamme syvemmälle siihen, miten nämä verkostot jaetaan pieniksi yhteisöiksi.

Tarkastelemme suosittua nopeasti avautuvaa algoritmia . Vincent C.Blondel ja paperin kirjoittajat vertailivat tätä algoritmia muihin yhteisön havaitsemisalgoritmeihin. He havaitsivat, että tämä algoritmi ylittää kaikki muut algoritmit suurissa verkoissa.

Mikä on nopeasti avautuva algoritmi?

Nopeasti avautuvaa algoritmia käytettiin kieliyhteisöjen tunnistamiseen 2,6 miljoonan asiakkaan belgialaisessa matkapuhelinverkossa.

Sitä käytettiin myös 118 miljoonan solmun ja yli miljardin linkin verkkokaavion analysointiin.

Yhteisöjen tunnistaminen näin valtavassa verkostossa kesti vain 152 minuuttia. Joten tämä algoritmi on sekä nopea että tehokas.

Kuinka algoritmi toimii

Algoritmi toimii kahdessa vaiheessa:

Vaihe 1

  1. Määritä jokaiselle verkon solmulle oma yhteisö.
  2. Sitten kutakin solmua, i katsoo solmu j ja arvioi vahvistusta modulaarisuus poistamalla solmun i sen yhteisön ja asettamalla se yhteisössä j.
  3. Solmu i sijoitetaan yhteisöön, jolle se saa maksimaalisen modulaarisuuden, mutta vahvistuksen tulisi olla positiivinen. Jos vahvistus on negatiivinen, solmu i pysyy samassa yhteisössä.

Vaihe 2

  1. Algoritmin toinen vaihe koostuu uuden verkon rakentamisesta, jonka solmut ovat nyt ensimmäisen vaiheen aikana löydettyjä yhteisöjä. Joten rakennamme solmut yhdistämällä kaikki yhteisön solmut yhdeksi solmuksi.
  2. Solmujen välisen linkin painot saadaan vastaavien kahden yhteisön solmujen välisten linkkien painojen summalla.
  3. Saman yhteisön solmujen välinen linkki johtaa uuden verkon yhteisöihin.
  4. Toista vaihe 1, kunnes mitään parannusta ei voida saavuttaa.

Kuinka modulaarisuuden voitto lasketaan

Osioiden laatua ( Q ) mitataan modulaarisuudella (eli osion modulaarisuudella). Sen skalaariarvo on välillä -1 ja 1, ja mittaa yhteyksien tiheyttä yhteisöjen sisällä verrattuna yhteisöjen välisiin yhteyksiin.

Gain Modulaarisuus (AQ), joka saatiin siirtämällä eristetty solmu i osaksi yhteisö C voidaan helposti laskea:

Σin on C: n sisäisten linkkien painojen summa.

Σtot on C: n solmuihin sattuvien linkkien painojen summa.

ki on linkkien painojen summa i: stä solmuun C.

m on verkon kaikkien linkkien painojen summa.

Modulariteetin voitto arvioidaan poistamalla i yhteisöstä ja siirtämällä se sitten naapurikuntaan. Jos voitto on positiivinen, kyseinen solmu sijoitetaan viereiseen yhteisöön.

Algoritmin kuivakäynti

Vasemmalla olevassa verkossa (15 solmua) määritämme ensin yksilöllisen yhteisön jokaiselle solmulle. Sitten arvioimme kunkin solmun modulaarisuuden ja osoitamme yhteisön uudelleen vahvistuksen perusteella. Tätä kutsutaan modulaarisuuden optimoinniksi .

Seuraavassa vaiheessa rakennamme solmut yhdistämällä kaikki kyseisen yhteisön solmut yhteen solmuun. Vihreässä yhteisössä meillä on yhteensä 5 solmua ja niiden välillä on yhteensä 7 reunaa.

Joten yhteisön yhdistämisen jälkeen vihreän solmun itsesilmukan paino on 14 (7 * 2, koska se on kaksisuuntainen linkki). Vastaavasti punaisen solmun itsesilmukan paino on 16, sininen solmu on 4 ja vaaleansininen solmu on 2.

Vihreän ja sinisen solmun välisen reunan paino on 4, koska modulaarisuuden optimoinnin jälkeen vihreän ja sinisen yhteisön välillä on yhteensä 4 reunaa.

Seuraavassa vaiheessa arvioimme uusien solmujen modulaarisuuden uudelleen ja teemme saman prosessin uudelleen.

Lopuksi saamme kaksi yhteisöä, vihreän ja vaaleansinisen. Vihreällä yhteisöllä on 26 itsesilmukkaa, koska vihreän yhteisön solmujen välillä on yhteensä 13 reunaa. Ja meillä on 12 reunaa vaaleansinisessä yhteisössä, yhteensä 24 itsesilmukkaa.

Algoritmin edut

  1. Sen vaiheet ovat intuitiivisia ja helppoja toteuttaa, ja lopputulosta ei valvota.
  2. Algoritmi on erittäin nopea. Hyvin valtavien modulaaristen verkkojen tietokonesimulaatiot viittaavat siihen, että sen monimutkaisuus on lineaarinen tyypilliseen ja harvaan dataan nähden. Tämä voi johtua siitä, että Gain in Modularity on helppo laskea ja yhteisöjen määrä vähenee rajusti vain muutaman ohituksen jälkeen.

Algoritmin rajoitukset

  1. Modulaarisuuden optimointi ei tunnista tiettyä mittakaavaa pienempiä yhteisöjä. Joten se aiheuttaa tarkkuusrajan yhteisölle, joka lasketaan puhtaalla modulaarisuuden optimointimenetelmällä.
  2. Pienissä verkoissa todennäköisyys, että kaksi erillistä yhteisöä voidaan yhdistää siirtämällä kutakin solmua, on hyvin pieni.

Johtopäätös

Jos olet ripustanut siellä niin kauan ... kiitos! Toivon, että sinulle on ollut arvokasta tietoa.

Joten nyt tiedät kuinka nopeasti avautuva algoritmi toimii ja että on erittäin tehokasta tunnistaa yhteisöt erittäin suurissa verkoissa.

Tapa, jolla se laskee modulaarisuuden vahvistuksen, saa algoritmin ylittämään kaikki muut algoritmit siellä. Pudota minulle muistiinpano, jos se on hyödyllinen tai jos sinulla on kysyttävää.

Kiitos lukemisesta!