Герван-Њуманов алгоритам

Герван-Њуманов алгоритам (назван по Мишел Гирван и Марку Њуману) је једна од метода које се користе за откривање заједнице у сложеним системима. Појам "структура заједнице" односи се на то груписање, иако то није сасвим исто. Заједница се састоји од подскупа чворова у оквиру које чвор-чвор везе су густе, а ивице на чворовима у другим срединама су мање густе. Постоје бројне алтернативне методе за откривање заједнице у мрежама. Ово укључује хијерархијско груписање, подела графова тако да максимизирају квалитетне функције, као што су мреже модуларности, изненадна максимизација, К - клика филтрирање итд.

Централна ивица и структура заједнице

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

Герван-Њуман алгоритам делује на супротан начин. Уместо да покушава да изгради меру која нам говори које су ивице централне у заједници, он се фокусира на тим ивицама које су најудаљеније од централне, ивице које су највише "између" заједница. Заједнице се откривају постепеним уклањањем ивица од оригиналног графа, а не додавањем најјаче ивице на почетку празне мреже.

"Централна тачка" је проучавана у прошлости као мера централности и утицаја чворова у мрежи. За сваки чвор , "Централна тачка" се дефинише као број најкраћих путева између парова чворова који пролазе кроз њу. То је мера утицаја чвора над протоком информација између осталих чворова, посебно у случајевима у којима проток информација преко мреже, пре свега следи најкраћи пут на располагању. Гирван-Њуман алгоритам проширује ову дефиницију у случају ивица, дефинисање "ивица између" од ивице као број најкраћих путева између парова чворова који се покрећу уз њега. Ако постоји више од једног најкраћег пута између пара чворова, сваки пут је добио једнаку тежину такав да је укупна маса свих стаза износи јединству. Ако мрежа садржи заједнице или групе које су само лабаво повезане са неколико унутрашњих ивица, онда су сви најкраћи путеви између различитих заједница морали да иду дуж једног од ових неколико ивица. Дакле, ивице које повезују заједнице ће имати велики број "ивица између" (бар једану од њих). Уклањањем ове ивице, групе су одвојене једна од друге и тако основна заједница структуре мреже је откривена.

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

1. Прво се рачуна средишњост свих постојећих ивица у мрежи.
2. Средња ивица се уклања.
3. Поново се рачуна средишњост свих ивица на које је утицало уклањање.
4. Кораци 2 и 3 се понављају све док се не уклоне преостале ивице.

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

Крајњи резултат Герван-њумановог алгоритма је дендрограм. Како Герван-Њуманов алгоритам ради, дендрограм се производи од врха надоле (тј. мрежу дели на различите заједнице са сукцесивним уклањањем линкова). Лишће дендрограма су појединачни чворови.