SKDIM sazetak 20141120

Izvor: KiWi

Inačica od 09:36, 3. studenog 2014. koju je unio/unijela Goranigaly (Razgovor | doprinosi)
(razl) ←Starija inačica | vidi trenutačnu inačicu (razl) | Novija inačica→ (razl)
Skoči na: orijentacija, traži

Nedjeljivi grafovi

U većini kompleksnih mreža pojavljuju se posebne grupe vrhova, tzv. zajednice (eng. communities). Zajednica unutar grafa je gust podgraf tog grafa, tj. više je bridova koji povezuju vrhove koji se nalaze unutar zajednice nego što je bridova koji povezuju vrhove zajednice sa vrhovima izvan zajednice. Za potrebe razumijevanja strukture kompleksne mreže, razvijene su razne metode za otkrivanje zajednica u mreži. Jedna od vrlo popularnih metoda je Newmanov spektralni modularni maksimizacijski algoritam, koji dijeli graf na dvije zajednice obzirom na predznake glavnog svojstvenog vektora pripadne modularne matrice, no, samo u slučaju da je najveća svojstvena vrijednost te matrice veća od nule. Prema Newmanu, graf je nedjeljiv ako pripadna modularna matrica nema pozitivnih svojstvenih vrijednosti. Karakterizirat ćemo nedjeljive grafove.

Dobavljeno iz "http://degiorgi.math.hr/kiwi/index.php/SKDIM_sazetak_20141120"
Osobni alati