^   **DZIEKAN i RADA WYDZIAŁU**    \\    **INFORMATYKI, ELEKTRONIKI I TELEKOMUNIKACJI**    \\    **AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE**   ^^
|   zapraszają na    \\    publiczą dyskusję nad rozprawą doktorską    \\      \\   //mgra inż. Wojciecha Czecha//      \\                 ||
|  **Exploring complex networks with topological descriptors**  ||
^  Termin:|24 października 2012 roku o godz. 13:00  |
^  Miejsce:| Pawilon D-17, sala 1.36, ul. Kawiory 21  |
^  **PROMOTOR:**|Prof. dr hab. inż. Witold Dzwinel - Akademia Górniczo-Hutnicza  |
^  ** RECENZENCI:**|Prof. dr hab. inż. Zbigniew Czech - Politechnika Śląska |
^  **            **|Dr hab. inż. Krzysztof Cetnarowicz, prof. nadzw. AGH - Akademia Górniczo-Hutnicza |
|  Z rozprawą doktorską i opiniami recenzentów można się zapoznać \\ w Czytelni   Biblioteki Głównej AGH, al. Mickiewicza 30  ||

==== Exploring complex networks with topological descriptors ====
     

//mgr inż. Wojciech Czech//


**Promotor:** prof. dr hab. inż. Witold Dzwinel (AGH)\\
**Dyscyplina:** Informatyka

\\


Ze względu na powszechność grafowych reprezentacji danych w wielu interdyscyplinarnych obszarach badań oraz stały wzrost rozmiaru grafów będących przedmiotem analiz, rozwijanie nowych, szybkich metod analizy i porównywania grafów jest dzisiaj ważnym problemem naukowym.

W niniejszej pracy autor rozpatruje problem efektywnego porównywania grafów proponując nowe narzędzia algorytmiczne i programowe pozwalające na obliczanie miar niepodobieństwa grafów oraz ich wykorzystanie w klasteryzacji i klasyfikacji danych z obszaru sieci złożonych i strukturalnego rozpoznawania wzorców. W szczególności metryka najkrótszej ścieżki, zastosowana do budowy wierzchołkowych grafów k-odległości i krawędziowych grafów k-odległości, pozwala na przekształcenie grafu do postaci tzw. B-macierzy. Wygenerowanie B-macierzy grafu jest mniej kosztowne obliczeniowo niż wyznaczenie niezmienników grafu opartych na dekompozycji spektralnej macierzy Laplace’a lub macierzy adiacencji. Autor zaproponował nowe deskryptory grafowe oparte na B-macierzach takie jak długi wektor cech, względne odchylenie oraz entropia wierszy B-macierzy. Wektory cech grafu, otrzymane przy użyciu B-macierzy pozwalają na separacje grafów o nietrywialnych różnicach strukturalnych i dają lepsze wyniki w eksploracji grafowych zbiorów danych niż aktualnie stosowane deskryptory spektralne. Generacja cech w oparciu o niezmienniki grafów k-odległości jest ogólnym podejściem do problemu porównywania grafów i może być zastosowana zarówno dla grafów bez wag, jak i grafów ważonych. Przeprowadzono szereg eksperymentów na grafowych zbiorach danych, w tym między innymi: rozpoznawanie zdjęć satelitarnych w oparciu o ich grafową reprezentację, klasyfikacja mutagennych związków chemicznych, budowa drzewa filogenetycznego w oparciu o deskryptory sieci metabolicznych, śledzenie dynamiki wzrostu naczyń krwionośnych w obecności nowotworu. Eksperymenty wykazały wysoką skuteczność proponowanej metody w porównaniu z innymi współcześnie stosowanymi algorytmami osadzania grafów w przestrzeni metrycznej.

W ramach pracy opracowana została aplikacja //Graph Investigator//, pozwalająca na porównywanie grup grafów w oparciu o ich deskryptory topologiczne oraz algorytmy uczenia z nadzorem i bez nadzoru. W celu zwiększenia wydajności aplikacji zaimplementowano wersje równoległe algorytmów obliczania deskryptorów grafowych wykorzystujące procesory graficzne (GPU). Pozwoliło to na znaczne polepszenie interaktywności aplikacji oraz poszerzyło możliwości jej zastosowania do analizy grafów o znacznym rozmiarze.

** Tezy rozprawy:**
  - **Grafy k-odległości, skonstruowane na podstawie miar niepodobieństwa między wierzchołkami grafu G, tworzą uporządkowany zbiór pochodnych grafów, który pozwala na wygenerowanie niezmienników izomorfizmu dla grafu G, efektywnych w klasteryzacji i klasyfikacji benchmarkowych zbiorów danych strukturalnych.**
  - **Wzrost wydajności obliczeniowej uzyskany dzięki realizacji metod generacji cech grafu na procesorze graficznym (GPU) pozwala na zwiększenie rozmiaru grafów analizowanych w sposób interaktywny o dwa rzędy wielkości.**

**Dłuższa wersja autoreferatu** {{:2012:czech:wczech_autoref.pdf|tutaj}}

**Ważniejsze publikacje doktoranta**

  - Wojciech Czech, Invariants of Distance k-Graphs for Graph Embedding, Pattern Recognition Letters, volume 33, issue 15, 2012.
  - Wojciech Czech, Witold Dzwinel, Review of graph invariants for quantitative analysis of structure dynamics, Advances in Intelligent Modeling and Simulation: Simulation Tools and Applications, eds. A. Byrski, Z. Oplatkova, M. Carvahlo, M. Kisiel-Dorohinicki, Springer, 2012.
  - Wojciech Czech, David A. Yuen, Efficient graph comparison and visualization using GPU, Proceedings of the 14th IEEE International Conference on Computational Science and Engineering (CSE 2011), IEEE Computer Society, 561-566, doi: 10.1109/CSE.2011.223, 2011.
  - Wojciech Czech, S. Goryczka, T. Arodz, W. Dzwinel, A. Dudek, Exploring complex networks with Graph Investigator research application, Computing and Informatics, vol. 30, no. 2, p. 381-410, 2011.
  - Wojciech Czech, Graph Descriptors from B-Matrix Representation, Graph-Based Representations in Pattern Recognition, Proc. of 8th IAPRTC-15 International Workshop, GbRPR 2011, Lecture Notes in Computer Science, vol. 6658, 12-21, 2011.
  - Wojciech Czech, Clustering of real-world data using multiple-graph representation and centrality measures, Computational Intelligence: methods and applications, eds. Leszek Rutkowski, Ryszard Tadeusiewicz, Lotfi A. Zadeh, Jacek Zurada, ISBN 978-83-60434-50-5, 9th Conference on Artificial Intelligence and Soft Computing, 2008.