Kursplan för

Nätverksdynamik
Network Dynamics

FRTN30, 7,5 högskolepoäng, A (Avancerad nivå)

Gäller för: Läsåret 2014/15
Beslutad av: Utbildningsnämnd B
Beslutsdatum: 2014-04-08

Allmänna uppgifter

Valfri för: D4, E4-ra, F4, F4-r, Pi4-bg
Undervisningsspråk: Kursen ges på engelska

Syfte

Olika typer av nätverk finns överallt i vårt moderna samhälle: infrastrukturnätverk tillhandahåller kommunikation, transporter och energi; sociala nätverk styr vår tillgång till information och påverkar våra åsikter; ekonomiska och finansiella nätverk styr ekonomiska transaktioner och finansiella kopplingar; och naturliga nätverk (t.ex. biologiska och fysiska nätverk) bestämmer evolution och spridningen av naturfenomen.

Kursen fokuserar på de gemensamma matematiska principer som bestämmer strukturen och funktionen hos dessa nätverk. Koncept och verktyg från dynamiska system, (slump)grafteori, markovkedjor, optimering och spelteori introduceras. Kursen täcker också ett antal tillämpningar inklusive lärande och informationskedjor, ekonomiska och finansiella nätverk, sociala påverkansnätverk, formering av sociala grupper, kommunikations nätverk och Internet, konsensus och ryktesspridning, spridning och reglering av epidemier samt reglering av transport och energinätverk

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

• känna till de grundläggande principerna inom grafteori och kunna använda dem för att modellera riktiga nätverk
• ha insikt i de grundläggande skillnaderna mellan olika modeller för slumpgrafer
• känna till egenskaperna för slumpvandring över grafer
• kunna analysera enkla dynamiska system över nätverk
• förstå "emerging phenomena" i storskaliga nätverk
• kunna ge en översikt av moderna forskningsinriktningar inom nätverksteori.

Färdighet och förmåga
För godkänd kurs skall studenten

• kunna analysera egenskaper hos (slump)grafer både kvalitativt och kvantitativt
• kunna genomföra grundläggande analytiska beräkningar av slumpvandring
• kunna analysera enkla dynamiska system över nätverk och relatera dess beteende till nätverksstrukturen
• kunna använda datorverktyg för simulering och analys av nätverk.

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

• förstå relationer och begränsningar när enkla modeller används för att beskriva komplexa nätverk
• kunna utvärdera "emerging phenomena" för nätverksdynamik
• visa förmåga till arbete i grupp.

Kursinnehåll

• Grundläggande grafteori: konnektivitet, ordningsfördelningar, träd, "adjacency" matriser, spektra.
• Slumpgrafer: Erdos-Renyi, konfigurationsmodeller, "preferential attachment", "small-world", "branching process abstractions".
• Flöden och spel över grafer: "max-flox min-cut", optimal transport, "Wardrip equilibria", evolutionär dynamik.
• Slumpvandring över grafer: invarianta distributioner, "hitting times", "mixing times".
• Dynamiska system över grafer: distribuerad medelvärdesbildning, interagerande partikelsystem, epidemier, opinionsdynamik, "Mean-field and branching process approximations".

Kursens examination

Betygsskala: TH
Prestationsbedömning: Skriftlig examen (5 tim), fyra godkända inlämningsuppgifter. Vid färre än fem anmälda kan en muntlig tentamen ges.

Delmoment
Kod: 0115. Benämning: Tentamen.
Antal högskolepoäng: 7,5. Betygsskala: TH.
Kod: 0215. Benämning: Inlämningsuppgift 1.
Antal högskolepoäng: 0. Betygsskala: UG.
Kod: 0315. Benämning: Inlämningsuppgift 2.
Antal högskolepoäng: 0. Betygsskala: UG.
Kod: 0415. Benämning: Inlämningsuppgift 3.
Antal högskolepoäng: 0. Betygsskala: UG.
Kod: 0515. Benämning: Inlämningsuppgift 4.
Antal högskolepoäng: 0. Betygsskala: UG.

Antagningsuppgifter

Förutsatta förkunskaper: FRT010 Reglerteknik, allmän kurs.
Begränsat antal platser: Nej

Kurslitteratur

• D. Easley & J. Kleinberg: Networks, crowds and markets, reasoning about a highly connected world. Cambridge University Press, 2010, ISBN: 978-0-521-19533-1, Supplement to lecturer's notes.
• R. Van Der Hofstad: Random Graphs and Complex Networks. Supplement to lecturer's notes. Tillgänglig online via http://www.win.tue.nl/~rhofstad/.
• D. Levin, Y. Peres, E. Wilmer: Markov chains and mixing times. American Mathematical Society, 2009, ISBN: 978-0-8218-4739-8, Supplement to lecturer's notes.

Kontaktinfo och övrigt

Kursansvarig: Giacomo Como, giacomo.como@control.lth.se
Studierektor: Karl-Erik Årzén, karlerik@control.lth.se