Grafy i sieci: projekt 2019/2020
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: 25 pkt
aplikacja: 20 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.
Harmonogram projektu
13.03 ustalony podział na grupy i przydział tematów
17.04 oddanie dokumentacji wstępnej
08/12.05 kontrola postępów prac
29.05 oddanie aplikacji i raportu z testów
Harmonogram prezentacji (wstępny)
pierwsza prezentacja: (17,24,29.04)
druga prezentacja: (22,29.05, 05.06)
Przykładowe tematy projektów
- Znajdowanie map modułów w sieciach interakcji biologicznych.
Amar D, Shamir R. Constructing module maps for integrated analysis of heterogeneous biological networks. Nucleic Acids Res. 2014;42(7):4208–4219. doi:10.1093/nar/gku102
Wśród danych testowych powinny znaleźć się dane, których używali autorzy powyższego artykułu (ze zbioru BioGRID).
- Algorytm PHL dla skierowanych sieci transportowych.
Takuya Akiba, Yoichi Iwata, Ken ichi Kawarabayashi, and Yuki Kawata. Fast shortest-pathdistance queries on road networks by pruned highway labeling. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14), pages 147–154. SIAM,2014
Patrz też: Bast, Hannah, et al. Route planning in transportation networks. Algorithm engineering. Springer, Cham, 2016. 19-80 - 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.
- 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