Grafy i sieci: projekt 2021/2022
Zasady zaliczenia
- Ocena z przedmiotu wystawiana jest na podstawie zebranych punktów. W sumie można uzyskać 100 punktów. Oceny wystawiane są na podstawie klucza:
50-59 3.0
60-69 3.5
70-79 4.0
80-89 4.5
90+ 5.0 - W ramach przedmiotu studenci w grupach trzyosobowych przygotowują projekt na temat ustalony z prowadzącym. W uzasadnionych przypadkach możliwe są odstępstwa dotyczące liczebności grup.
- Projekt składa się z trzech części: dokumentacji wstępnej, implementacji i końcowego raportu z opisem testów i wnioskami. Dodatkowo studenci zobowiązani są przedstawić postępy prac nad projektem.
- Dodatkowo, każda grupa w trakcie semestru przedstawia dwie prezentacje
pierwsza, w połowie semestru, dotyczy przedstawienia problemu i planu rozwiązania
druga, na koniec semestru, dotyczy podsumowania projektu i przedstawienia wyników - Punktacja za poszczególne etapy:
prezentacja 1: 20 pkt
prezentacja 2: 10 pkt
dokumentacja wstępna: 20 pkt
aplikacja: 25 pkt (w tym kontrola postępów prac)
raport końcowy: 25 pkt - Każdy rozpoczęty tydzień spóźnienia wiąże się z karą 10 pkt.
- Ocenie podlega cały projekt, jak i wkład każdego członka zespołu. Możliwa jest sytuacja, że różne osoby z jednej grupy dostaną różne oceny.
- Obecność na prezentacjach jest obowiązkowa. Pozostałe spotkania mają charakter konsultacji.
- Na stronie przedmiotu sukcesywnie będą pojawiały się ramowe informacje dotyczące oczekiwanej zawartości poszczególnych części projektu i prezentacji. Ze względu na duże zróżnicowanie tematów, każda grupa powinna ustalić szczegóły z prowadzącym przedmiot.
Opiekunem części grup projektowych jest inż. Łukasz Brzozowski.
Harmonogram projektu
04.03 ustalony podział na grupy
11.03 ustalony przydział tematów
25.03 termin oddania dokumentacji wstępnej
06.05-12.05 kontrola postępów prac
27.05 oddanie aplikacji i raportu końcowego
10.06 ostatni termin oddania czegokolwiek
Harmonogram prezentacji (wstępny)
pierwsza prezentacja: 25.03, 01.04 (i jeśli trzeba 08.04)
druga prezentacja: 27.05 i 03.06
Przykładowe tematy projektów
- Wykrywanie nierozłącznych społeczności, np. na podstawie pracy:
Yang, Jaewon, and Jure Leskovec. "Overlapping community detection at scale: a nonnegative matrix factorization approach." Proceedings of the sixth ACM international conference on Web search and data mining. 2013
W zależności od stopnia skomplikowania algorytmu, proszę porównać z wersją bez przecięć. W testach należy wykorzystać m.in. faktyczne dane np. ze zbioru (3) na liście poniżej. - Wykrywanie podstruktur w sieciach biologicznych.
Wong E, Baur B, Quader S, Huang CH. Biological network motif detection: principles and practice. Brief Bioinform. 2012;13(2):202–215. doi:10.1093/bib/bbr033 - PageRank, SimRank, CoSimRank - zastosowania, różnice i podobieństwa. W ramach projektu należy porównać te trzy algorytmy i ich implementacje oraz zaproponować usprawnienie dla ograniczonych klas grafów. Inne warianty projektu są do negocjacji.
- Analiza eksperymentalna i statystyczna różnic w sformułowaniach modelu Barabásiego-Alberta.
Giorgos Stamatelatos, Pavlos S. Efraimidis, About Weighted Random Sampling in Preferential Attachment Models, https://arxiv.org/abs/2102.08173 - Grafowe sieci konwolucyjne – propozycja i implementacja możliwych usprawnień
Thomas N. Kipf, Max Welling, Semi-Supervised Classification with Graph Convolutional Networks, https://arxiv.org/abs/1609.02907 - Grafowe sieci neuronowe a problem izomorfizmów grafów.
Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka, How Powerful are Graph Neural Networks?, https://arxiv.org/abs/1810.00826
Rickard Brüel-Gabrielsson, Universal Function Approximation on Graphs, https://arxiv.org/abs/2003.06706 - Uczenie reprezentacyjne grafów.
William L. Hamilton, Rex Ying, Jure Leskovec, Representation Learning on Graphs: Methods and Applications, https://arxiv.org/abs/1709.05584
Należy zaimplementować i porównać wybrane algorytmy oraz zaproponować i zaimplementować usprawnienia. - Czy uczenie reprezentacyjne oparte o podobieństwo strukturalne może znaleźć zastosowanie we współczesnej matematyce dyskretnej, np. w problemach kolorowania?
https://research.google.com/pubs/archive/46591.pdf
https://arxiv.org/abs/1710.10321 - Inne: modele generatywne grafów, systemy rekomendacyjne. Inspiracje: https://www.cs.mcgill.ca/~wlh/grl_book/
- Inne. Inspiracji można szukać na przykład tu:
- Bast, Hannah, et al. Route planning in transportation networks. Algorithm engineering. Springer, Cham, 2016. 19-80
- Rajaraman, Anand, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2011, rozdział 10
- Nettleton, David F. Data mining of social networks represented as graphs. Computer Science Review 7 (2013): 1-34