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
  Egyetemi docens, Sztochasztika Tanszék
• 
  Dr. Nagy Marcell
  Tudományos munkatárs, Sztochasztika Tanszék

helyezés