Studentská grantová soutěž - předchozí roky

Analýza a zpracování rozsáhlých grafů

SP2012/151

Dvorský Jiří doc. Mgr., Ph.D.

01. 01. 2012 - 31. 12. 2012

Předmět výzkumu v rámci projektu: Díky nárůstu výpočetních možností v posledních letech se mohou více používat metody práce s grafy, které byly dříve vhodné jen pro menší datové kolekce z důvodů výpočetní náročnosti. Typickým zástupcem těchto metod, kterými se budeme v navrhovaném projektu zabývat, jsou metody spektrálního rozkladu matic odpovídajících incidenčním maticím grafů, ať už ohodnocených nebo neohodnocených. Rozkladem grafu vzniknou jednotlivé komponenty, které mají specifické vlastnosti a jichž lze využít v dalších oblastech výzkumu, odkud pocházel původní graf, například rozklad grafu rozsáhlé sociální sítě a následná vizualizace komponent. Jako příklad může sloužit Fiedlerova metoda založena na výpočtu druhého nejmenšího vlastního čísla a příslušného vlastního vektoru pozitivně semidefinitní, reálné, symetrické matice [1,2]. Tyto metody nám umožňují například lineárně přeuspořádat vrcholy ohodnoceného grafu tak, že blízké uzly mají blízké indexy a uzly, které si jsou vzdáleny, mají indexy s větším rozdílem. Pro nalezení tohoto uspořádání musíme spočítat několik vlastních čísel a příslušných vlastních vektorů. Tuto úlohu můžeme řešit pomocí různých numerických metod (např. Lanczosovou metodou). Tato metoda je vhodná i pro řídká data a je možné ji paralelizovat. Detailní popis projektu: V současnosti se všechny uvedené metody používají v různých oblastech (zpracovaní dat a obrazů, analýza sociálních sítí, vizualizace). Jejich přesnější použití je následující: 1. Neuronové sítě SOM – nalezení shluků, které jsou vizuálně reprezentované pomocí SOM mapy. 2. Analýza sociálních sítí – spektrální shlukování, detekce komunit v sociální síti, překrývající se shluky, studium dynamiky sociální sítě. 3. Komprese grafů – předzpracování dat (předpokládáme využití „spectral ordering“) tak, aby se zvýšila účinnost a rychlost komprese. 4. Vizualizace grafů – hierarchizovaná vizualizace grafů, přehlednější způsoby vizuální reprezentace rozsáhlých sítí (sociálních, komplexních). Zásadním problémem stávajících řešení je rozsáhlost dat a možnosti jejich “dostatečně rychlého” zpracování. V předloženém projektu se budeme zabývat výše uvedenými problémy. Výzkumným cílem projektu je vývoj a implementace jednotlivých metod, které budou splňovat následující podmínky: – schopnost zpracovat rozsáhlé datové kolekce, – paralelizovatelnost výpočtu, – efektivita výpočtu. Tabulka publikační činnosti řešitelského týmu: RIV 2011 ISI proc IF WoS ISI proc 2011 IF WoS Jiří Dvorský 172 26 1 5 1 Jan Martinovič 187 24 14 1 Pavla Dráždilová 26 3 4 Kateřina Slaninová - 2 5 Lukáš Vojáček - 0 Michal Holiš - 0 Alisa Babskova - 0 Jednotlivé sloupec tabulky obsahují: 1. RIV 2011 2. Publikace - články ve sbornících ISI 3. Publikace - IF časopisy WoS 4. Publikace 2011 - články ve sbornících ISI, předpoklad 5. Publikace 2011 - IF časopisy WoS, předpoklad Tým tvoří • 3 zaměstnanci, z nichž jeden je současně kombinovaným doktorandem • 4 doktorandi (3 interní a 1 kombinovaný) • Dále předpokládáme možné zapojení minimálně dalších 3 studentů magisterského studijního programu, kteří již nyní mají zadaná témata diplomových prací souvisejících s navrhovaným projektem. Harmonogram Předkládaný projekt je plánován na dobu jednoho roku. Projekt bude zpracováván paralelně v několika úlohách: • komplexní rešerše, zpracování podrobného stavu současného poznání, Q1 • práce na experimentech, výsledky experimentu budou průběžně shrnovány do technického reportu, Q1, Q2, Q3 • obeslání konferencí indexovaných WoS, Q1 až Q3 • zpracování poznatku do formy časopiseckého článku, výběr vhodného časopisu (časopisů), Q4 Literatura 1. Wong, P. C. et al. A Space-Filling Visualization Technique for Multivariate Small-World Graphs. IEEE Transactions on Visualization and Computer Graphics (2011). [online]. [cit. 2011-12-16]. 2. Yaliraki, S. N. , Barahona, M. Stability of graph communities across time scales. Transition 107, 1-8 (2009). 3. Xie, F., Ji, M., Zhang, Y. , Huang, D. The detection of community structure in network via an improved spectral method. Physica A: Statistical Mechanics and its Applications 388, 3268-3272 (2009). 4. Snášel, V. , Klement P. Using SOM in the performance monitoring of the emergency call-taking system. Simulation Modelling Practice and Theory 19, 98-109(2011). 5. Claesson, V., Lonn, H. & Suri, N. Mesh Partitioning for Efficient Use of Distributed Systems. IEEE Transactions on Parallel and Distributed Systems 13, 725-739 (2002).

Ing. Jan Martinovič, Ph.D.
Mgr. Pavla Dráždilová, Ph.D.
Ing. Lukáš Vojáček, Ph.D.
Ing. Kateřina Slaninová, Ph.D.
Ing. Alisa Babskova
Ing. Michal Holiš
doc. Mgr. Jiří Dvorský, Ph.D.

Cílem projektu je návrh a implmentace efektivních metod výpočtu spektrálního rozkladu matic (grafů). Takto implmentované metody chceme využít v těchto oblastech: shlukování pomocí SOM, spektrálním shlukování, kompresi grafů, vizualizace rozsáhlých sítí, dělení meshe. Dalším cílem projektu je návrh efektivních implementací založených na paralelizaci výpočtů. A v neposlední řadě je cílem příprava společných publikací na konferencích a v časopisech s impaktním faktorem.