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:

  1. 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.
  2. 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 tutaj

Ważniejsze publikacje doktoranta

  1. Wojciech Czech, Invariants of Distance k-Graphs for Graph Embedding, Pattern Recognition Letters, volume 33, issue 15, 2012.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
2012/czech/start.txt · ostatnio zmienione: 2012/10/12 11:26 przez Wojciech Czech