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 |
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:
Dłuższa wersja autoreferatu tutaj
Ważniejsze publikacje doktoranta