Netwerkanalyse

Network Analysis

Studiewijzer 2021/2022

Globale inhoud

Alle informatie over dit vak vind je op http://maartenmarx.nl/teaching/NetwerkAnalyse/.

Heel veel wetenschappelijk en ook practische problemen zijn te bekijken en te analyseren met de theorie van netwerken. Voorbeelden van netwerken zijn het internet, het GPS netwerk, FaceBook, Twitter, samenwerk-netwerken, netwerken tussen woorden, infectie netwerken, etc.

We bekijken de formele theorie achter netwerken en grafen; we bekijken hoe we belangrijke (centrale) spelers in een netwerk kunnen detecteren, hoe we clusters van spelers kunnen maken, hoe informatie zich door een netwerk verspreid, hoe het toch komt dat rijkdom en aandacht vaak zo oneerlijk verdeeld zijn, en nog veel meer.

Theoretische stof wordt steeds voorzien van concrete voorbeelden. Je toetst of je de stof beheerst door het maken van opdrachten. Met het Python netwerk analyse  pakket NetWorkX gaan we bestaande grote netwerken analyseren en visualiseren. De theoretische stof kunnen we zo direct toepassen op bestaande en zelf vergaarde data.

Het vak is geschikt voor informatiekundigen, als minor- of keuzevak voor studenten AI, Informatica, media en cultuur, communicatiewetenschappers en studenten uit de sociale wetenschap.

Leerdoelen

Network Science

• Wat zijn netwerken? Verschillende soorten: gericht/ongericht, gewogen/ongewogen, multiple layers, met eigenschappen op knopen
• Basisbegrippen: volledig, verbonden, componenten, afstand, dichtheid,..
• Centraliteitsmaten: degree, betweenness , closenness, eccentricity, pagerank, ...
• Eigenschappen echte netwerken: triangular closure, clustering, small world, machtsverdeelde grootheden
• (Bijna) alles zelf implementeren vanuit basis (in FO logica en in Python)
• Theorie: strong-weak tie netwerken, friend-foe netwerken, diffusie van innovatie/besmetting in netwerken
• Praktijk:
  • zelf netwerken opbouwen uit data te vinden op het web (eg co-starring netwerken in NL films, NL talkshows op TV, rapsongs)
  • leren werken met real life netwerken in networkx (via Python tutorials and datasets bij het boek).

Verzamelingen, logica, datastructuren en algorithmes

• naieve verzamelingenleer
  • verzamelingen, cardinaliteit, gelijkheid, deelverzameling, notatie
  • de operaties op verzamelingen
  • nieuwe verzamelingen maken: comprehensies, product, machtsverzameling
  • Machtsverzameling stelling
  • Verzamelingen in Python, syntax, set comprehensies, frozensets, operaties zelf programmeren
• Geldigheid van redenering
  • modellen, tegenvoorbeelden
• Propositielogica
  • syntax
  • waarheidstabellen
  • SAT algorithme met waarheidstabel, idem voor logisch gevolg
  • intuitie achter NP volledigheid
  • verband met verzmelingen
• Eerste orde logica
  • 1 en 2 plaatsige relaties, interpretatie op netwerk modellen
  • syntax, intuitieve semantiek
  • Waarheid op een model, tegenvoorbeeld, geldigheid van redeneringen
  • Vertalen van zinnen in Nederlands naar FO zinnen, en naar equivalente Python code
  • FO zinnen programmeren als equivalente verzamelingen elementen
    • bijv "Elke man houdt van een vrouw" is equivalent aan
    • ∀𝑥(𝑀𝑥→∃𝑦(𝑅𝑥𝑦∧𝑉𝑦))∀x(Mx→∃y(Rxy∧Vy)) is equivalent aan
    • not {x for x in G if M(x) and not {y for y in G if R(x,y) and V(y)} }
  • Allerlei netwerk begrippen vertalen naar FO logica.
• Datasctructuren
  • Bomen
  • lijsten, sets, dics, en heel veel oefenen met (complexe) comprehensies
  • stack, en heap
• Algorithmes
  • wanneer is iets een algorithme? Wanneer is het correct? Wat zijn de kosten?
  • max zonder sorteren
  • mean met miniem geheugen gebruik
  • sorteren
  • breadth first search
  • SAT, uitputtend alle mogelijkheden afgaan.

Studiemateriaal

Literatuur

• David Easley and Jon Kleinberg, 'Networks, Crowds, and Markets: Reasoning About a Highly Connected World', gratis te verkrijgen via http://www.cs.cornell.edu/home/kleinber/networks-book/

• Menczer, F., Fortunato, S., & Davis, C. (2020). A First Course in Network Science. Cambridge: Cambridge University Press. doi:10.1017/9781108653947

Syllabus

•  https://canvas.uva.nl/courses/17240/assignments/syllabus

Software

• IPython Notebooks, bij voorkeur de Anaconda distributie

Overig

• Alle informatie over dit vak. Wat hier in de syllabus op Canvas staat is leidend.

Leerdoelen

• De student kan de centrale wiskundige theorie over netwerken en gerichte en ongerichte grafen te beschrijven uitleggen.
• De student kan de centrale theorie over sociale netwerken toepassen.
• De student kan praktische problemen uit de echte wereld modelleren als netwerk probleem.
• De student kan netwerk gegevens extraheren uit verzamelde data.
• De student kan geavanceerde netwerk analyse software gebruiken om problemen op te lossen met behulp van de theorie en techniek van (sociale) netwerken.
• De student kan eigen werk en dat van anderen testen op correctheid, voorzien van een heldere geschreven beoordeling, en kan ingeleverd werk van zichzelf en anderen ordenen op kwaliteit.
• Leerdoelen Network Science Wat zijn netwerken? Verschillende soorten: gericht/ongericht, gewogen/ongewogen, multiple layers, met eigenschappen op knopen Basisbegrippen: volledig, verbonden, componenten, afstand, dichtheid,.. Centraliteitsmaten: degree, betweenness , closenness, eccentricity, pagerank, ... Eigenschappen echte netwerken: triangular closure, clustering, small world, machtsverdeelde grootheden (Bijna) alles zelf implementeren vanuit basis (in FO logica en in Python) Theorie: strong-weak tie netwerken, friend-foe netwerken, diffusie van innovatie/besmetting in netwerken Praktijk: zelf netwerken opbouwen uit data te vinden op het web (eg co-starring netwerken in NL films, NL talkshows op TV, rapsongs) leren werken met real life netwerken in networkx (via Python tutorials and datasets bij het boek). Verzamelingen, logica, datastructuren en algorithmes naieve verzamelingenleer verzamelingen, cardinaliteit, gelijkheid, deelverzameling, notatie de operaties op verzamelingen nieuwe verzamelingen maken: comprehensies, product, machtsverzameling Machtsverzameling stelling Verzamelingen in Python, syntax, set comprehensies, frozensets, operaties zelf programmeren Geldigheid van redenering modellen, tegenvoorbeelden Propositielogica syntax waarheidstabellen SAT algorithme met waarheidstabel, idem voor logisch gevolg intuitie achter NP volledigheid verband met verzmelingen Eerste orde logica 1 en 2 plaatsige relaties, interpretatie op netwerk modellen syntax, intuitieve semantiek Waarheid op een model, tegenvoorbeeld, geldigheid van redeneringen Vertalen van zinnen in Nederlands naar FO zinnen, en naar equivalente Python code FO zinnen programmeren als equivalente verzamelingen elementen bijv "Elke man houdt van een vrouw" is equivalent aan ∀𝑥(𝑀𝑥→∃𝑦(𝑅𝑥𝑦∧𝑉𝑦)) is equivalent aan not {x for x in G if M(x) and not {y for y in G if R(x,y) and V(y)} } Allerlei netwerk begrippen vertalen naar FO logica. Datasctructuren Bomen lijsten, sets, dics, en heel veel oefenen met (complexe) comprehensies stack, en heap Algorithmes wanneer is iets een algorithme? Wanneer is het correct? Wat zijn de kosten? max zonder sorteren mean met miniem geheugen gebruik sorteren breadth first search SAT, uitputtend alle mogelijkheden afgaan.

Onderwijsvormen

• Hoorcollege
• Werkcollege
• Laptopcollege
• Zelfstudie
• Begeleiding/feedbackmoment
• Zelfstandig werken aan bijv. project/scriptie
• (Computer)practicum
• online vragenuur (Corona)

4 uur hoorcollege, 2 uur werkcollege en 2 uur computer practicum per week.

Voor het werkcollege   geldt een aanwezigheidsplicht van 90%.

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkcolleges, met opdrachten, geldt een aanwezigheidsplicht, tenzij anders vermeld in de studiegids. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan het onderdeel niet met een voldoende worden afgerond. De aanwezigheidsplicht met betrekking tot hoor-werkcolleges staat, indien van toepassing, vermeld in de studiegids.
  

Aanvullende eisen voor dit vak:

Er mogen hooguit  1 van 6 werkcolleges gemist worden.

Wat te doen als je door overmacht afwezig bent? 

In principe dien je bij alle verplichte practica, waaronder PAV, aanwezig te zijn. Nu kan het in de loop van een collegejaar best een keer gebeuren dat je bijvoorbeeld ziek bent of naar een begrafenis wilt waardoor je een bijeenkomst mist. Het gaat hier steeds om overmacht: een onmogelijkheid die je niet valt toe te rekenen.

Bij de meeste vakken staat hier een regeling voor in de studiewijzer of studiegids. Doe in dat geval wel het volgende:

1. Meld je vooraf per e-mail af bij de begeleider van die bijeenkomst (meestal een tutor, practicumassistent, of de docent).
2. Neem zo goed mogelijk zelfstandig het materiaal door.
3. Informeer bij je medestudenten wat je verder gemist hebt.

Wanneer je niet voldoet aan, of buiten de regeling van het vak valt, of denkt dat je door één keer missen al studievertraging oploopt, dan ontstaat er mogelijk een probleem. Neem in dat geval contact op met de studieadviseur. Zij kan met je kijken wat de gevolgen van jouw afwezigheid zijn voor jouw studie, en eventueel meedenken naar oplossingen.

De studieadviseur is via de mail te bereiken aan de hand van het online vragenformulier. Ook kun je online een afspraak inplannen. Telefonisch is de studieadviseur bereikbaar via de ESC servicedesk: 020 5257100.

De studieadviseur voor de bacheloropleiding Informatiekunde is:

  Zie de informatiepagina van de studieadviseurs.

Toetsing

Alle informatie over toetsing staat op https://canvas.uva.nl/courses/17240/assignments/syllabus#toets

Inzage toetsing

Na elke toets is er een responsiecollege waarop de vragen van de toets en de juiste antwoorden daarop besproken worden. Daarna is er de mogelijkheid om de open vragen van je eigen toets in te zien.

Opdrachten

Zie https://canvas.uva.nl/courses/17240/assignments/syllabus#toets

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: http://student.uva.nl

Weekplanning

Rooster

Het rooster van dit vak is in te zien op DataNose.

Aanvullende informatie

Noodzakelijke voorkennis: Programmeren IK

Verwerking vakevaluaties

Hieronder vind je de aanpassingen in de opzet van het vak naar aanleiding van de vakevaluaties.

* toetsen en opdrachten verhelderd

* meer aandacht aan programmeren

* meer assistenten

* meer mogelijkheid tot het stellen van vragen en hulp bij opdrachten

* heldere communicatie via Canvas

* al het materiaal beschikbaar via surfdrive

Contactinformatie

Coördinator

• dr. Maarten Marx

Assistenten

• Barbara Easton
• Jasper van der Heide
• Robin Langerak
• Roan Schellingerhout
• Iva Schenk
• Emma Tas