Hogyan ismeri fel a gyorsan kibontakozó algoritmus a közösségeket a nagy hálózatokban?

A közösségi hálózat elemzése magában foglalja a valós életben lévő hálózatok mintáinak tanulmányozását, amelyek millió csomópontból állnak. Ha rendelkezik a gráfelmélet alapismereteivel, elvégezheti ezeket az elemzéseket.

A digitális világ a kapcsolatok létrehozásának teljesen más módját nyitotta meg. Az adatok óceánját is felszabadította, amelyeket elemezhetünk, hogy jobban megértsük az emberi viselkedést.

A közösségi média adatai az egyén közösségi média tevékenységéből összegyűjtött összes nyers meglátásra és információra vonatkoznak. Hálózatokat hozhatunk létre ezekből a közösségi média tevékenységekből, hogy jobban megértsük az egyént.

Ezek a hálózatok széles skálán mozoghatnak, és magukban foglalhatják a Facebook-ismerőseidet, az Amazonon nemrég vásárolt termékeket, a tetszett vagy retweetelt tweeteket, a Zomato-tól megrendelt kedvenc ételedet, a Google-on végzett keresést vagy a legutóbb az Instagramon kedvelt képet. .

A vállalatok ezeket a hálózatokat használva különböző csoportokba sorolják felhasználóikat. Ez segít nekik

  • végezzen piackutatást
  • generál vezet
  • jobban szolgálja ügyfeleiket
  • fotók és videók megkeresése és megosztása
  • felfedezni és megvitatni a felkapott tartalmat
  • információkat osszon meg a szolgáltatásokról és az éttermekről
  • kapcsolatba lépni másokkal egy közös érdeklődés vagy hobbi körül
  • és több.

A lista nagyjából végtelen.

Mielőtt túlságosan belemennénk a gyomokba, bontsuk le gyorsan a hálózat különböző összetevői közötti különbséget.

Mi az a hálózat?

A hálózat az összekapcsolt személyes kapcsolatok hálója. Például különböző egyének kommunikálhatnak egymással egy közösségi média csoportban egy dinamikus kapcsolati hálón keresztül.

A hálózat csomópontokból (egyes szereplőkből, emberekből vagy a hálózaton belüli dolgokból) és az őket összekötő kapcsolatokból , élekből vagy kapcsolatokból (kapcsolatok vagy interakciók) áll.

Mi az a csoport?

Reicher SD: A kollektív viselkedés meghatározása a csoportot olyan egyének gyűjteményeként írja le, akik csoportnak tekintik magukat. Ugyanazon csoport tagjai közös meggyőződéssel és magatartással rendelkeznek.

Mi az a közösség?

David W. McMillan ( Sense of Community: A Definition and Theory ) szerint a közösség a következőképpen határozható meg:

A közösségi érzelem a tagok összetartozásának érzése, az az érzés, hogy a tagok számítanak egymásnak és a csoportnak, és közös hit, hogy a tagok igényeit kielégítik az elkötelezettségük, hogy együtt vannak.

A közösségek vagy alegységek a hálózat alhálózatai, amelyek erősen összekapcsolt csomópontok.

A közösség jelzi, hogy léteznek olyan belső struktúrák, amelyek különleges jellemzőkkel bírnak, vagy ugyanolyan szerepet játszanak a hálózatban.

A hálózatokon belül erősen összekapcsolt egyének vagy tárgyak csoportjai közösségek. Általában a hálózat és a csoport metszéspontjában fekszik.

Most, hogy világos elképzelésünk van arról, mi is egy hálózat, csoport és közösség, merüljünk el mélyebben abban, hogy ezek a hálózatok hogyan oszlanak fel kis közösségekre.

Megnézzük a népszerű Gyorsan kibontakozó algoritmust . Vincent C. Blondel és a cikk társszerzői összehasonlították ezt az algoritmust más közösségi detektáló algoritmusokkal. Felfedezték, hogy ez az algoritmus minden más algoritmust felülmúl nagy hálózatokban.

Mi a gyorsan kibontakozó algoritmus?

A gyorsan kibontakozó algoritmust használták a nyelvi közösségek azonosítására egy 2,6 millió ügyfélből álló belga mobiltelefon-hálózatban.

Ezenkívül 118 millió csomópontot és több mint egymilliárd linket tartalmazó webgrafikon elemzésére is használták.

A közösségek azonosítása egy ilyen hatalmas hálózatban mindössze 152 percet vett igénybe. Tehát ez az algoritmus egyszerre gyors és hatékony.

Az algoritmus működése

Az algoritmus két fázisban működik:

1. szakasz

  1. Rendeljen egy másik közösséget a hálózat minden csomópontjához.
  2. Ezután minden egyes csomópont i véli csomópont j és értékeli a nyereség modularitás eltávolításával csomópont i annak közösség és helyezze azt a közösség j.
  3. Az i csomópont abba a közösségbe kerül, amelynél maximális modularitást nyer, de a nyereségnek pozitívnak kell lennie. Ha az erősítés negatív, akkor az i csomópont ugyanabban a közösségben marad.

2. fázis

  1. Az algoritmus második fázisa egy új hálózat felépítéséből áll, amelynek csomópontjai immár az első fázis során talált közösségek. Tehát csomópontokat építünk úgy, hogy a közösség összes csomópontját egyetlen csomópontként egyesítjük.
  2. A csomópontok közötti kapcsolat súlyát a megfelelő két közösség csomópontjai közötti kapcsolatok súlyainak összege adja meg.
  3. Ugyanazon közösség csomópontjai közötti kapcsolat önhurkokhoz vezet a közösség számára az új hálózatban.
  4. Ismételje meg az 1. fázist, amíg további javulás nem érhető el.

Hogyan számítják ki a Modularitásban elért nyereséget

A partíció minőségét ( Q ) a modularitás (más néven a partíció modularitása ) méri . Skaláris értéke -1 és 1 között, és a közösségeken belüli kapcsolatok sűrűségét méri a közösségek közötti kapcsolatokhoz.

Az elkülönített i csomópont C közösségbe történő áthelyezésével kapott nyereség a modularitásban (∆Q) könnyen kiszámítható:

Σin a C-ben lévő linkek tömegének összege.

Σtot a C csomópontokhoz kapcsolódó linkek súlyainak összege.

ki az i- től a C-ig tartó csomópontig tartó linkek súlyainak összege .

m a hálózat összes linkjének tömegének összege.

A Modularitás nyereségét úgy értékeljük, hogy az i- t eltávolítom a közösségéből, majd áthelyezem egy szomszédos közösségbe. Ha az erősítés pozitív, akkor az a csomópont a szomszédos közösségbe kerül.

Az algoritmus száraz futtatása

A bal oldali hálózatban (15 csomópont) először minden csomóponthoz egyedi közösséget rendelünk. Ezután értékeljük az egyes csomópontok modularitását, és a nyereség alapján hozzárendeljük a közösséget. Ezt hívják Modularitás optimalizálásnak .

A következő szakaszban csomópontokat építünk úgy, hogy a közösség összes csomópontját egyetlen csomópontba egyesítjük. A zöld közösségben összesen 5 csomópontunk van, és összesen 7 él van közöttük.

Tehát a közösségi összesítés után a zöld csomópont önhurokjának súlya 14 lesz (7 * 2, mivel ez kétirányú kapcsolat). Hasonlóképpen, a vörös csomópont önhurokjának súlya 16, a kék csomópont 4 és a világoskék csomópont 2 lesz.

A zöld és a kék csomópont közötti él súlya 4 lesz, mivel a Modularitás optimalizálása után a zöld és a kék közösség között összesen 4 él van.

A következő lépésben átértékeljük az új csomópontok Modularitását, és újra elvégezzük ugyanazt a folyamatot.

Végül két közösséget kapunk, a Zöldet és a Világoskéket. A zöld közösségnek 26 önhurkja van, mivel a zöld közösség csomópontjai között összesen 13 él található. És 12 élünk van a világoskék közösségben, összesen 24 önhurok.

Az algoritmus előnyei

  1. Lépései intuitívak és könnyen megvalósíthatók, és az eredmény nem felügyelhető.
  2. Az algoritmus rendkívül gyors. A nagyon hatalmas moduláris hálózatokon végzett számítógépes szimulációk arra utalnak, hogy összetettsége lineáris a tipikus és ritka adatoknál. Ennek oka lehet, hogy a Gain in Modularity könnyen kiszámítható, és a közösségek száma néhány passz után drasztikusan csökken.

Az algoritmus korlátai

  1. A modularitás optimalizálása nem képes azonosítani egy bizonyos skálánál kisebb közösségeket. Tehát felbontási korlátot okoz a közösség számára, amelyet tiszta modularitás optimalizálási módszerrel számolnak.
  2. Kis hálózatok esetében nagyon kicsi annak a valószínűsége, hogy két külön közösség egyesülhet az egyes csomópontok mozgatásával.

Következtetés

Ha ennyire lógott ott ... köszönöm! Remélem, hogy értékes információk álltak rendelkezésére.

Tehát most már tudja, hogyan működik a Gyorsan kibontakozó algoritmus, és hogy rendkívül hatékony a nagyon nagy hálózatok közösségeinek felderítése.

A modularitásbeli nyereség kiszámításával az algoritmus minden más algoritmust felülmúl. Dobjon el egy jegyzetet, ha hasznosnak találja, vagy bármilyen további kérdése van.

Köszönöm, hogy elolvasta!