Schválené projekty 2012

Rozdělení přidělené dotace z MŠMT na specifický vysokoškolský výzkum po fakultách se zohledněním celoškolských pracovišť na rok 2012

Celková přidělená částka z MŠMT na specifický vysokoškolský výzkum na VŠB-TUO - 40 767 tis.Kč

Z toho 2.5%  - 1 019 175 Kč - úhrada způsobilých nákladů spojených s organizací SGS

fakultačástka v  Kč
FBI 1 135 000
EKF 5 252 000
FAST 2 282 000
FS 7 631 476
FEI 9 323 810
HGF 6 829 216
FMMI 7 293 498
CELKEM 39 747 000

(825,-Kč rezerva)

KódSP2012/151
Název projektuAnalýza a zpracování rozsáhlých grafů
ŘešitelDvorský Jiří doc. Mgr., Ph.D.
Školitel projektu
Období řešení projektu01.01.2012 - 31.12.2012
Předmět výzkumuPř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).

Členové řešitelského týmuIng. Alisa Babskova
doc. Mgr. Jiří Dvorský, Ph.D.
Ing. Michal Holiš
Ing. Jan Martinovič, Ph.D.
Ing. Kateřina Slaninová, Ph.D.
Mgr. Pavla Dráždilová, Ph.D.
Ing. Lukáš Vojáček, Ph.D.
Specifikace výstupů projektu (cíl projektu)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.


Rozpočet projektu - uznané náklady

NávrhSkutečnost
1. Osobní náklady
Z toho
8000,-8040,-
1.1. Mzdy (včetně pohyblivých složek)8000,-6000,-
1.2. Odvody pojistného na veřejné zdravotně pojištění a pojistného na sociální zabezpečení a příspěvku na státní politiku zaměstnanosti0,-2040,-
2. Stipendia152500,-154500,-
3. Materiálové náklady0,-0,-
4. Drobný hmotný a nehmotný majetek0,-0,-
5. Služby0,-40000,-
6. Cestovní náhrady150000,-107960,-
7. Doplňkové (režijní) náklady max. do výše 10% poskytnuté podpory34500,-34500,-
8. Konference pořádané VŠB-TUO k prezentaci výsledků studentského grantu (max. do výše 10% poskytnuté podpory)0,-0,-
9. Pořízení investic0,-0,-
Plánované náklady345000,-
Uznané náklady345000,-
Celkem běžné finanční prostředky345000,-345000,-