Како алгоритам који се брзо одвија открива заједнице у великим мрежама

Анализа друштвених мрежа укључује проучавање образаца у великим мрежама из стварног живота које се састоје од милиона чворова. Ако имате основно знање теорије графова, можете извршити ове анализе.

Дигитални свет отворио је потпуно другачији начин стварања односа. Такође је ослобођен океан података које можемо анализирати да бисмо боље разумели људско понашање.

Подаци на друштвеним мрежама односе се на све сирове увиде и информације прикупљене током активности појединца на друштвеним мрежама. Можемо створити мреже од ових активности на друштвеним мрежама да бисмо стекли бољу перцепцију те особе.

Ове мреже могу се широко ширити и могу укључивати ваше пријатеље на Фацебоок-у, производе које сте недавно купили на Амазону, твитове који су вам се свидели или су их проследили, вашу омиљену храну коју сте наручили из Зомато-а, претрагу на Гоогле-у или слику коју сте недавно волели на Инстаграму .

Компаније користе ове мреже да класификују своје кориснике у различите групе. Ово им помаже

  • бавити се истраживањем тржишта
  • генеришу потенцијалне клијенте
  • боље опслужују своје купце
  • пронађите и делите фотографије и видео записе
  • откријте и разговарајте о актуелном садржају
  • размењују информације о услугама и ресторанима
  • повежите се са другима око заједничког интереса или хобија
  • и још.

Листа је прилично бескрајна.

Пре него што уђемо превише у коров, хајде да брзо разбијемо разлику између различитих компонената мреже.

Шта је мрежа?

Мрежа је мрежа међусобно повезаних личних односа. На пример, различити појединци могу комуницирати једни с другима у групи друштвених медија путем динамичке мреже односа.

Мрежу чине чворови (појединачни актери, људи или ствари у мрежи) и везе , ивице или везе (односи или интеракције) које их повезују.

Шта је група?

Реицхер СД у Одређивање колективног понашања описује групу као скуп појединаца који себе сматрају групом. Чланови исте групе имају скуп заједничких веровања и понашања.

Шта је заједница?

Према Давиду В. МцМиллану ( Сенсе оф Цоммунити: А Дефинитион анд Тхеори ) , заједница се може дефинисати као следеће:

Смисао заједнице је осећај припадности чланова, осећај да су чланови важни једни другима и групи и заједничка вера да ће потребе чланова бити задовољене њиховом опредељеношћу да буду заједно.

Заједнице или подјединице су подмреже у мрежи које су високо повезани чворови.

Заједница указује на постојање унутрашњих структура које имају посебне карактеристике или играју исту улогу у мрежи.

Високо повезане групе појединаца или објеката унутар ових мрежа су заједнице. Обично лежи на тачки пресека мреже и групе.

Сад кад имамо јасну представу о томе шта је мрежа, група и заједница, заронимо дубље у то како су те мреже подељене на мале заједнице.

Осврнућемо се на популарни алгоритам брзог одвијања . Винцент Ц. Блондел и коаутори рада упоређивали су овај алгоритам са другим алгоритмима за откривање заједнице. Открили су да овај алгоритам надмашује сваки други алгоритам у великим мрежама.

Шта је алгоритам брзог одвијања?

Алгоритам брзог расплета коришћен је за идентификовање језичких заједница у белгијској мрежи мобилних телефона од 2,6 милиона корисника.

Такође је коришћен за анализу веб графа од 118 милиона чворова и више од милијарде веза.

Идентификовање заједница у тако огромној мрежи трајало је само 152 минута. Дакле, овај алгоритам је и брз и ефикасан.

Како алгоритам функционише

Алгоритам ради у две фазе:

Фаза 1

  1. Доделите различиту заједницу сваком чвору у мрежи.
  2. Затим, за сваки чвор, ја сматра чвор ј и оцењује добитак у модуларности уклањањем чвор И од своје заједнице и стављања у заједници ј.
  3. Чвор и је постављен у заједницу за коју добија максималну модуларност, али добитак би требао бити позитиван. Ако је добитак негативан, чвор и остаје у истој заједници.

Фаза 2

  1. Друга фаза алгоритма састоји се у изградњи нове мреже чији су чворови сада заједнице пронађене током прве фазе. Дакле, чворове градимо спајањем свих чворова у заједници као једног чвора.
  2. Пондери везе између чворова дати су збиром пондера веза између чворова у одговарајуће две заједнице.
  3. Веза између чворова исте заједнице доводи до само-петљи за заједницу у новој мрежи.
  4. Понављајте фазу 1 док се не може постићи даље побољшање.

Како се израчунава добитак у модуларности

Квалитет партиције ( К ) мери се модуларношћу (ака модуларност партиције). Његова скаларна вредност је између -1 и 1 и мери густину веза унутар заједница у поређењу са везама између заједница.

Добитак у Модуларност (ΔК) добија се креће изоловани чвор и у заједници Ц може лако да се израчуна:

Σин је збир тежина веза унутар Ц.

Σтот је збир тежина веза које падају на чворове у Ц.

ки је збир тежина веза од и до чвора у Ц.

м је збир тежина свих веза у мрежи.

Добитак модуларности процењује се уклањањем и из његове заједнице и премештањем у суседну заједницу. Ако је добитак позитиван, тада се тај чвор поставља у суседну заједницу.

Суво покретање алгоритма

У мрежи лево (15 чворова) прво додељујемо јединствену заједницу сваком чвору. Затим процењујемо модуларност сваког чвора и додељујемо заједницу на основу добитка. Ово се назива оптимизација модуларности .

У следећој фази градимо чворове спајањем свих чворова у тој заједници у један чвор. У зеленој заједници имамо укупно 5 чворова и између њих има укупно 7 ивица.

Дакле, након агрегације заједнице , тежина само-петље зеленог чвора биће 14 (7 * 2 јер је двосмерна веза). Слично томе, тежина само-петље црвеног чвора биће 16, плави чвор 4, а светло плави чвор 2.

Тежина ивице између зеленог и плавог чвора биће 4, јер након оптимизације модуларности постоје укупно 4 ивице између зелене и плаве заједнице.

У следећем кораку поново процењујемо Модуларност за нове чворове и поново радимо исти поступак.

Коначно, добијамо две заједнице, зелену и светло плаву. Зелена заједница има 26 самопетља, јер између чворова зелене заједнице постоји укупно 13 ивица. И имамо 12 ивица у светло плавој заједници, укупно 24 самопетља.

Предности алгоритма

  1. Његови кораци су интуитивни и једноставни за спровођење, а исход је без надзора.
  2. Алгоритам је изузетно брз. Компјутерске симулације на веома огромним модуларним мрежама сугеришу да је његова сложеност линеарна у односу на типичне и ретке податке. То је можда зато што је добитак у модуларности лако израчунати, а број заједница драстично опада након само неколико пролаза.

Ограничења алгоритма

  1. Оптимизација модуларности не успева да идентификује заједнице мање од одређене скале. Дакле, то узрокује ограничење резолуције за заједницу израчунато коришћењем чистог приступа оптимизацији модуларности.
  2. За мале мреже вероватноћа да се две одвојене заједнице могу спојити померањем сваког чвора је врло мала.

Закључак

Ако сте се толико дуго задржали тамо ... хвала! Надам се да су за вас постојале драгоцене информације.

Дакле, сада знате како функционише алгоритам брзог одвијања и да је изузетно ефикасно откривање заједница у врло великим мрежама.

Начин на који израчунава добитак у модуларности чини да алгоритам надмашује сваки други алгоритам. Пошаљите ми белешку ако вам се учини корисном или ако имате било каква додатна питања.

Хвала за читање!