Ostatnia aktualizacja:
March 12. 2024 09:39:46
Aktualności / News > Dydaktyka / Teaching > Historia / History > Grafy i sieci: projekt 2021/2022

Grafy i sieci: projekt 2021/2022


Zasady zaliczenia

  1. 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
  2. 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.
  3. 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.
  4. 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
  5. 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
  6. Każdy rozpoczęty tydzień spóźnienia wiąże się z karą 10 pkt.
  7. 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.
  8. Obecność na prezentacjach jest obowiązkowa. Pozostałe spotkania mają charakter konsultacji.
  9. 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


  1. 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.
  2. 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
  3. 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.
  4. 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
  5. 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
  6. 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 
  7. 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.
  8. 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
  9. Inne: modele generatywne grafów, systemy rekomendacyjne. Inspiracje: https://www.cs.mcgill.ca/~wlh/grl_book/
  10. 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
Przykładowe źródła danych