Dovoľujeme si oznámiť, že dňa
25. 6. 2014 o 10.00 hod.
sa uskutoční na Fakulte informatiky a informačných technológií STU v Bratislave
Ilkovičova 2, v miestnosti 4.08 obhajoba dizertačnej práce
Ing. Davida Chalupu
Názov dizertačnej práce: | Partitioning Networks into Cliques: A Randomized Heuristic Approach Rozdeľovanie sietí do kompletných podgrafov: znáhodnený heuristický prístup |
Odbor: | 9.2.9. Aplikovaná informatika |
Školiteľ:
- prof. RNDr. Jiří Pospíchal, DrSc., FIIT STU v Bratislave
Oponenti dizertačnej práce:
- doc. RNDr. Mária Markošová, PhD., FMFI UK v Bratislave
- doc. Ing. Ivan Sekaj, PhD. - FEI STU v Bratislave
Abstrakt:
Rozdeľovanie sietí do kompletných podgrafov je zaujímavý súčasný problém, motivovaný rastom popularity sociálnych sietí a ich komunitnou štruktúrou. Cieľom problému (vrcholového) pokrývania kompletnými podgrafmi (angl. clique covering problem, skr. CCP) je rozdeliť vrcholy siete do minimálneho počtu skupín, vo vnútri ktorých je každá dvojica vrcholov susedná.
V tejto dizertačnej práci prezentujeme permutačnú reprezentáciu pre CCP, založenú na greedy (voľný preklad "pažravom") algoritme pokrývania kompletnými podgrafmi. krem toho predstavujeme vysoko efektívny iterovaný greedy (IG) algoritmus pre CCP v sociálnych a iných komplexných sieťach, ktorý používa túto reprezentáciu. IG kombinuje myšlienky z oblasti klasických a stochastických algoritmov, vďaka čomu dosahuje vhodné vyváženie medzi škálovateľnosťou a kvalitou dosiahnutých výsledkov.
Pre permutačnú reprezentáciu, GCC a IG prezentujeme rozsiahle empirické a analytické výsledky, ktoré ukazujú, že IG je špeciálne vhodný prístup pre veľké riedke grafy. V prezentovaných experimentoch IG prekonáva známu Brélazovu heuristiku farbenia grafov v kvalite dosiahnutých výsledkov.
Okrem toho ukazujeme, že IG získava optimálne, resp. aspoň takmer optimálne výsledky na rozmanitej množine reálnych sietí, ktoré sme postupne získali.
Prvé rigorózne teoretické výsledky pre prístup sú tiež dokázané. Formulujeme postačujúcu podmienku pre to, aby IG dosiahlo zlepšenie riešenia. Dokazujeme, že IG nájde optimálne riešenie na cestách v polynomickom čase. Najhorší prípad správania algoritmu je tiež analyzovaný.
Partitioning of networks into cliques is an interesting current problem, motivated by the rise of popularity of social networks and their community structure. The aim of the (vertex) clique covering problem (CCP) is to partition the vertices of a network into the minimum number of groups, such that within each of these groups called cliques, all pairs of vertices are adjacent.
In this dissertation, we present an order-based representation for CCP based on a greedy clique covering (GCC) algorithm. Additionally, we propose a highly efficient iterated greedy (IG) algorithm for CCP in social and other complex networks, which uses this representation. IG combines the ideas from the areas of classical and stochastic algorithms, which leads to a favorable tradeoff between scalability and quality of results.
For the order-based representation, GCC and IG, we present extensive empirical and analytical results, which show that IG is particularly well-suited for large sparse graphs. In the presented experiments, IG outperforms the well-known Brélaz's graph coloring heuristic in terms of solution quality. Additionally, IG is shown to provide optimal or at least near-optimal results for a diverse set of real-world networks we acquired over time. First rigorous theoretical results for the approach are also proven. Sufficient condition for an improvement of solution by IG is formulated. It is shown that IG finds the optimal solution on path graphs in polynomial time. Worst-case performance is analyzed as well.
Autoreferát dizertačnej práce zaslaný do vedeckého časopisu Information Sciences and Technologies - Bulletin of ACM Slovakia
Dizertačná práca je k nahliadnutiu na Študijnom oddelení FIIT STU.