Az erdélyi tudomány hírei

Közösségi struktúrák detektálása Voronoj-particionálás segítségével súlyozott és irányított hálózatokban

Közösségi struktúrák detektálása Voronoj-particionálás segítségével súlyozott és irányított hálózatokban

Az alkalmazott hálózatkutatás egyik leggyakoribb problémája a csoportok, közösségek - lokálisan sűrűbb algráfok - detektálása, ellenben még nem minden típusú hálózati adat esetében állnak rendelkezésre hatékony technikák. Ez a kihívás különösen az irányított és súlyozott hálózatokban jelentkezik, ahol a kötéserősségek által kódolt többletinformáció és az esetlegesen magas gráfsűrűség sok meglévő megközelítést megnehezít. Ez a Scientific Reports-ban publikált tanulmány egy algoritmust mutat be, amely a Voronoj-particionálásból merít inspirációt, és amelyet az irányított súlyozott hálózatokra adaptáltak.

A Voronoj-particionálás egy módszer, amelyet a számítógépes geometria és a térbeli elemzés területén használnak, hogy egy teret felosszanak régiókra egy adott pontkészlettől (úgynevezett magoktól) mért távolságok alapján. Minden régió, amit Voronoj-cellának nevezünk, azokat a pontokat tartalmazza, amelyek közelebb vannak a saját magjához, mint bármely más maghoz. Ez a felosztás egy tesszellációt hoz létre a térben, ahol minden cella egy maghoz tartozik. A Voronoj-diagramok számos alkalmazással rendelkeznek különböző területeken, beleértve a földrajzot, biológiát, meteorológiát és hálózatelemzést.

A tanulmányban bemutatott algoritmus a relatív lokális gráfsűrűségek alapján jelöli ki a magokat és ezek köré építi fel a Voronoj cellákat, így detektálva a csoportokat. A távolságok számolásánál figyelembe veszi a súlyozott és irányított élek hosszait is. A módszernek egy fontos előnye, hogy közvetlenül tudja használni az élek olyan súlyait, amelyek hosszakat reprezentálnak. Másfajta súlyok esetén is használható a módszer, a súlyok megfelelő átalakításával.

Az algoritmust különböző hálózatokon validálták, beleértve az agyi területek közötti kapcsolatokat, a légiközlekedési rendszereket és különböző társadalmi hálózatokat. Az algoritmus teljesítményét több neves algoritmussal hasonlították össze, véletlenszerűen generált benchmark hálózatok sorozatán. Az eredmények azt mutatják, hogy az algoritmus jól kezeli a sűrű gráfokat, ahol a súlyok döntő szerepet játszanak a közösségi struktúrák meghatározásában. Emellett az algoritmus képes a hálózatok hierarchikus struktúráit is felismerni, ahogyan azt az agyi kapcsolati adatok is példázzák. Számítási hatékonysága versenyképes a legkorszerűbb módszerekével.

A tanulmány adatai:

Community detection in directed weighted networks using Voronoi partitioning

Szerző: Molnár Botond, Márton Ildikó-Beáta, Horvát Szabolcs, Ercsey-Ravasz Mária

Forrás: Scientific Reports (ISSN: 2045-2322), 2024. Volume: 14, Issue: 1.

 

Közösségi struktúrák detektálása Voronoj-particionálás segítségével súlyozott és irányított hálózatokban

Az alkalmazott hálózatkutatás egyik leggyakoribb problémája a csoportok, közösségek - lokálisan sűrűbb algráfok - detektálása, ellenben még nem minden típusú hálózati adat esetében állnak rendelkezésre hatékony technikák. Ez a kihívás különösen az irányított és súlyozott hálózatokban jelentkezik, ahol a kötéserősségek által kódolt többletinformáció és az esetlegesen magas gráfsűrűség sok meglévő megközelítést megnehezít. Ez a Scientific Reports-ban publikált tanulmány egy algoritmust mutat be, amely a Voronoj-particionálásból merít inspirációt, és amelyet az irányított súlyozott hálózatokra adaptáltak.

A Voronoj-particionálás egy módszer, amelyet a számítógépes geometria és a térbeli elemzés területén használnak, hogy egy teret felosszanak régiókra egy adott pontkészlettől (úgynevezett magoktól) mért távolságok alapján. Minden régió, amit Voronoj-cellának nevezünk, azokat a pontokat tartalmazza, amelyek közelebb vannak a saját magjához, mint bármely más maghoz. Ez a felosztás egy tesszellációt hoz létre a térben, ahol minden cella egy maghoz tartozik. A Voronoj-diagramok számos alkalmazással rendelkeznek különböző területeken, beleértve a földrajzot, biológiát, meteorológiát és hálózatelemzést.

A tanulmányban bemutatott algoritmus a relatív lokális gráfsűrűségek alapján jelöli ki a magokat és ezek köré építi fel a Voronoj cellákat, így detektálva a csoportokat. A távolságok számolásánál figyelembe veszi a súlyozott és irányított élek hosszait is. A módszernek egy fontos előnye, hogy közvetlenül tudja használni az élek olyan súlyait, amelyek hosszakat reprezentálnak. Másfajta súlyok esetén is használható a módszer, a súlyok megfelelő átalakításával.

Az algoritmust különböző hálózatokon validálták, beleértve az agyi területek közötti kapcsolatokat, a légiközlekedési rendszereket és különböző társadalmi hálózatokat. Az algoritmus teljesítményét több neves algoritmussal hasonlították össze, véletlenszerűen generált benchmark hálózatok sorozatán. Az eredmények azt mutatják, hogy az algoritmus jól kezeli a sűrű gráfokat, ahol a súlyok döntő szerepet játszanak a közösségi struktúrák meghatározásában. Emellett az algoritmus képes a hálózatok hierarchikus struktúráit is felismerni, ahogyan azt az agyi kapcsolati adatok is példázzák. Számítási hatékonysága versenyképes a legkorszerűbb módszerekével.

A tanulmány adatai:

Community detection in directed weighted networks using Voronoi partitioning

Szerző: Molnár Botond, Márton Ildikó-Beáta, Horvát Szabolcs, Ercsey-Ravasz Mária

Forrás: Scientific Reports (ISSN: 2045-2322), 2024. Volume: 14, Issue: 1.