Regisztráció és bejelentkezés

Box-covering algoritmusok összehasonlító elemzése

A komplex hálózatok vizsgálata jelenleg is aktívan kutatott interdiszciplináris terület. A hálózatok jellemzésekor az egyik fő kihívás az olykor igen bonyolult struktúrák hatékony leírása néhány jellemző paraméterrel. A szokásos, könnyen interpretálható jellemzők mellett a hálózatok fraktalitása is érdekes tulajdonságnak bizonyult. Korábbi vizsgálatok arra utalnak, hogy a hálózatok fraktalitása kapcsolatban állhat a külső hatásokkal (akár szándékolt támadással) szembeni ellenállóképességgel - ez magyarázhatja például, hogy számos biológiai hálózat a fraktálosság irányába fejlődik. Egy hálózat fraktálossága és fraktáldimenziója az ún. box-covering (dobozszámláló) módszerrel definiált. Bár a módszer könnyen érthető azonban a kapcsolódó probléma bizonyítottan NP-nehéz, így a gyakorlatban elengedhetetlen közelítő algoritmusok alkalmazása. Az irodalomban nagyszámú heurisztikus algoritmust vezettek be az elmúlt években, melyek létjogosultságát szerzőik általában valamilyen intuitív érveléssel és néhány, egyéb algoritmussal való összehasonlítással támasztanak alá. A dolgozat célja számos ilyen algoritmus összegyűjtése, megvalósítása és ezek egységes szempontok (futási idő, approximációs képesség) szerinti tesztelése különböző valós hálózatokon és elméleti hálózatmodelleken. Az így készült keretrendszert a jövőben valószínűleg nyílt forráskódú Python package-ként tesszük közzé. Reményeink szerint munkánk mind a hálózatkutatók, mind a más tématerületről érkező, fraktálos hálózatokkal dolgozó kutatók munkáját segítheti.

szerző

  • Kovács Péter Tamás
    Matematikus mesterképzési szak (MSc)
    mesterképzés (MA/MSc)

konzulensek

  • Molontay Roland
    Tudományos munkatárs, Sztochasztika Tanszék
  • Nagy Marcell
    Doktorandusz, Sztochasztika Tanszék