PREDNÁŠKY:
 

Mária Markošová
markosova@ii.fmph.uniba.sk
Peter Náther - I6
nather@ii.fmph.uniba.sk

Projekty

Zadanie prvého projektu

Vašou úlohou bude analyzovať tri grafy. A určiť ich dôležité vlastnosti. Podľa týchto vlastností bude treba následne jednotlivé modely identifikovať. Môžte mať aj dve inštancie toho isté modelu s inými parametrami :).


Hodnotenie : 15 bodov spolu. Za každý z nižšie uvedených bodov tvorí jeden graf jednu tretinu.
Deadline : 6.12.2020 - 22:00 (odovzdať môžte aj skôr výsledky zverejníme až keď budú všetky zadania odovzdané)

Na vybraných sieťach treba namerať nasledovné vlastnosti:

  1. priemer grafu 1B

  2. priemernú najkratšiu cestu 1B

  3. priemerný stupeň vrchola 1B

  4. klasterizačný koeficient siete 1B

  5. Vykresliť distribúciu stupňov vrcholov 1.5B

  6. Vykresliť distribúciu priemerných klasterizačných koeficientov vrcholov daného stupňa 1.5B

  7. Aproximovať zlogaritmovanú distribúciu stupňov vrcholov priamkou a zistiť tangens jej smerového uhla 1.5B

  8. Aproximovať zlogaritmovanú distribúciu priemerných klasterizačných koeficientov vrcholov daného stupňa 1.5B

  9. Vykresliť graf v niektorom z nástrojov, so zdôraznením dominantnej črty ak tam taká je 2B

  10. Z dostupných dát zanalyzovať, ktorý model vám bol pridelený 3B

Odporúčania

  • Na riešenie bodov 1.-4. odporúčam Gephi alebo Network workbench (nemusíte ho ale použiť ak nechcete)

  • Na riešenie bodov 5.-8. postačí Gnuplot (nemusíte ho ale použiť ak nechcete)

  • Layout je vaša kreatívna robota, nezabudnite, že prostredia majú užitočné pluginy (Užitočné je napr Gephi alebo Cytoscape)

Zoznam možných modelov

  • Barabási-Albert

  • Klienberg

  • Wats-Strogatz - radnom

  • Random model

  • Ravázs model

    • Súbory zo sieťami na analýzu v textovom .net formáte

  • A.zip
  • B.zip

    • Zadanie druhého projektu

    Vašou úlohou je odskúšať rôzne stratégie umiestňovania imunizačnej látky zá účelom minimalizovania :

    • maximálneho percenta nakazených jednom momente
    • počet chorých osobo dní počas simulácie. Jeden osobo deň znamená človeka chorého v daný deň, keď sčítame všetkých chorých v daný deň dostanem počet osobodní za daný deň. Po sčítaní cez všetky dni simulácie dostaneme výsledné číslo.
    Dĺžka trvania experimentu je počet dní infekcie (FinalTime). Choroba má nasledovné parametre :
    • Počiatočný počet nakazených - je percento z celkobého počtu, ktoré udáva koľko uzlov bude je nakazených na začiatku epidémie. Tieto uzly sú vyberané rovnomerne náhodne (InitialInfectionRate)
    • Mieru Infekcie - pravdepodobnosť s akou nakazí každý zdravý susedný uzol (InfectionProbability)
    • Dĺžku trvania infekcie - časový interval od úpešného nakazenia po vyzdravenie (MinimalInfectionTime, MaximalInfectionTime)
    Imunizačná látka nasledovné parametre :
    • Dobu účinku počas ktorej nemôže byť vrchol nakazený (VaccinationDuration)
    • Maximálne percento pokrytia imunizovaných vrcholov v systéme. (MaximalVaccinationRate)
    • Implicitný imunizačný rate ktorý udáva počet vakcín za jednotku času. Ten je funkcia : veľkosti grafu*percenta pokrytia / doby účinku
    Základnou vlastnosťou našej experimentálnej epidémie je cyklickosť ochorenia. To znamená, že ak vyzdraviem a mám chorého suseda tak sa môžem nakaziť znova.

    Na experimentovanie je treba použiť predpripravený simulačný template v jazyku java : template na stiahnutie

    Ten si ako počiatočné vstupy načítava neorientovaný graf v tvare edgelist a súbor s parametrami simulácie. Kód je slušne okomentovaný a štrukturovaný, čiže odpovede na implementačné otázky hľadajte najprv tam :).

    Požadovaný výstup na odovzdanie je formát v dokumente pdf, ktorý bude obsahovať nasledovné položky :

    1. Analýzu štruktúry grafu - ktoré sú strategické body príapdne klastre, aké má niektoré vlastosti (napr. prvé 4 z prvého projektu) a čo z nich vyplýva. 5B
    2. Štúdiu troch rôznych strátégii rozmiestňovania imunizačnej látky, kde každá je jeden experiment, rovnomerná náhodná sa nepočíta. Každá musí obsahovať popis stratégie, graf priebehu choroby, zhodnotenie experimentu. Každý experiment 7B spolu 21B
      Môj typ na varianty stratégii na stratégie :
      A - cieľ minimalizovať primárne maximálne dosiahnuté percento
      B - cieľ minimalizovať osobodni
      C - cieľ minimalizovať oba faktory súčasne
    3. Porovnanie všetkých prístupov na jednom grafe so zdôvodnením prečo je ktorá krivka aká. 5B
    4. Zobrazenie grafu na počiatku experimentu, v dobe na maximálnom počte chorých a v minime, ktoré sa podarilo dosahnuť po odznení maximálneho nakazenia. Grafy sú menšie ako tie v prvom projekte :). Každá sada obrázkov 3B spolu 9B. Na export v lubovoľnom čase slúži metóda saveGraph(meno súboru) Graphml formát dokáže spracovať napríklad gephi

    K dispozícii sú graf A a graf B.
    Oba grafy sú o veľkosti 500 vrcholov aby sa potenciálne dalo aj niečo rozumné zobraziť. Graf aj zdroják choroby si nakopírujte do prostredia, prepíšte volanie a hrajte sa :).

    Na obidvoch grafoch vyskúšajte tieto sady parametrov parametre 1 a parametre 2.

    Maximálne hodnotenie projetku 40B + prípadný bonus.
    Deadline TBA predbežný odhad je prvý januárový týždeň.