Xarxes Complexes

Crèdits
5
Tipus
Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
URV;CS
Mail
Les estructures de connexió en xarxa estan omnipresents en el món que ens envolta: les xarxes de comunicació, xarxes de transport, xarxes d'amics i coneguts, i les xarxes biològiques, per anomenar només alguns. En aquest curs, els estudiants aprendran les similituds i les abstraccions matemàtiques que jeuen sota aquests exemples. Altres exemples s'extrauran de la biologia molecular (regulació genètica i xarxes d'interacció de proteïnes), economia (xarxes de comerç, les relacions entre les empreses, i les interaccions en les xarxes estratègiques), les xarxes informàtiques (Internet, world wide web), i l'ecologia (les xarxes d'alimentació). En l'última dècada hi ha hagut una explosió de treball en la teoria i aplicacions de xarxes per a una enorme gamma de problemes. Els estudiants que completin aquest curs obtindran una àmplia introducció als treballs recents en aquest àmbit; comprendran les fortaleses i debilitats de modelatge de la xarxa, i podran aplicar les xarxes i la seva anàlisi en una varietat de configuracions.

A la primera part del curs ens centrarem en la descripció empírica de l'estructura de la xarxa. A continuació, dirigirem la nostra atenció a la dinàmica de les xarxes: com les xarxes es formen i creixen, i com són aquestes regles de creixement relacionats amb l'estructura global. Finalment, tindrem en compte algorismes i la dinàmica en les xarxes. En l'última part del curs es presentaran els problemes relacionats amb la propagació de malalties i virus informàtics en les xarxes, la forma de detectar l'estructura comunitats en les xarxes, i com funciona l'algorisme PageRank de Google.

Professors

Responsable

  • Sergio Gómez Jiménez ( )

Altres

  • Alexandre Arenas ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
0.5
Aprenentatge dirigit
0.5
Aprenentatge autònom
5.33

Competències

Competències Tècniques Generals

Genèriques

  • CG3 - Capacitat per a la modelització, càlcul, simulació, desenvolupament i implantació en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca, desenvolupament i innovació en tots els àmbits relacionats amb la Intel·ligència Artificial.

Competències Tècniques de cada especialitat

Acadèmiques

  • CEA11 - Capacitat de comprendre les tècniques avançades d'Intel·ligència Computacional, i saber dissenyar, implementar i aplicar aquestes tècniques en el desenvolupament d'aplicacions, serveis o sistemes intel·ligents.

Professionals

  • CEP2 - Capacitat de resoldre els problemes de presa de decisions de les diferents organitzacions, integrant eines intel·ligents.

Competències Transversals

ús solvent dels recursos d'informació

  • CT4 - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació de l'àmbit d'especialitat, i valorar de forma crítica els resultats d'aquesta gestió.

Raonament

  • CT6 - Capacitat d'avaluar i analitzar de manera raonada i crítica sobre situacions, projectes, propostes, informes i estudis de caracter cientific-tecnic. Capacitat d'argumentar les raons que expliquen o justifiquen aquestes situacions, propostes, etc.

Analisis i sintesis

  • CT7 - Capacitat d'anàlisi i resolució de problemes tècnics complexos.

Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.

Objectius

  1. Detectar sistemes susceptibles de ser representats mitjançant xarxes complexes
    Competències relacionades: CG3, CEP2, CB6,
  2. Saber com estudiar i caracteritzar l'estructura de xarxes complexes
    Competències relacionades: CEA11, CT4, CT7,
  3. Conèixer i saber implementar models de xarxes complexes
    Competències relacionades: CT7, CB6,
  4. Conèixer les principals dinàmiques sobre xarxes complexes
    Competències relacionades: CT4, CT7,
  5. Saber com implementar i validar simulacions Montecarlo
    Competències relacionades: CT7,
  6. Saber aplicar els coneixements assolits per l'extracció d'informació de sistemes que es poden descriure mitjantçant xarxes complexes
    Competències relacionades: CEA11, CEP2, CT4, CT6,

Continguts

  1. Introducció
    Exemples de xarxes complexes en molts àmbits de coneixement. Tipus de xarxes complexes.
  2. Estructura de xarxes complexes
    Principals característiques topològiques i estructurals de les xarxes complexes: distribució de grau, small-world, transitivitat, assortativity, estructura de comunitats, centralitat. Algorismes de detecció de comunitats.
  3. Models de xarxes complexes
    Xarxes aleatòries Erdös-Renyi, model de Barabasi-Albert, model de Watts-Strogatz, model de configuració.
  4. Dinàmiques en xarxes complexes
    Dinàmiques més importants en xarxes complexes: propagació d'epidèmies, sincronització, difusió, jocs evolutius, percolació. Simulacions Montecarlo. Transicions de fase.

Activitats

Activitat Acte avaluatiu


Introducció

Introducció
Objectius: 1
Continguts:
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Estructura de xarxes complexes

Desenvolupament del tema
Objectius: 2
Continguts:
Teoria
12h
Problemes
0h
Laboratori
2.5h
Aprenentatge dirigit
2h
Aprenentatge autònom
10h

Models de xarxes complexes

Desenvolupament del tema
Objectius: 3
Continguts:
Teoria
6h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
2h
Aprenentatge autònom
20h

Dinàmiques en xarxes complexes

Desenvolupament del tema
Objectius: 4 5
Continguts:
Teoria
10h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
2h
Aprenentatge autònom
10h

Projecte

Projecte de xarxes complexes
Objectius: 1 2 3 4 5 6
Continguts:
Teoria
0h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
1h
Aprenentatge autònom
40h

Lliurament de pràctiques sobre estructura de xarxes complexes

Lliurament de pràctiques sobre estructura de xarxes complexes
Objectius: 2
Setmana: 4
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Lliurament de pràctiques sobre models de xarxes complexes

Lliurament de pràctiques sobre models de xarxes complexes
Objectius: 3
Setmana: 8
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Lliurament de pràctiques sobre detecció de comunitats

Lliurament de pràctiques sobre detecció de comunitats
Objectius: 2
Setmana: 11
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Lliurament de pràctiques sobre simulació de dinàmiques

Lliurament de pràctiques sobre simulació de dinàmiques
Objectius: 4 5
Setmana: 15
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Entrevista del projecte

Entrevista del projecte
Objectius: 1 6
Setmana: 18
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Metodologia docent

Classes magistrals, pràctiques amb ordinador, resolució de problemes pràctics

Mètode d'avaluació

Resolució de problemes pràctics
Desenvolupament d'un projecte sobre xarxes complexes

Bibliografia

Bàsica:

Web links

Capacitats prèvies

Capacitats prèvies en Algorísmica i Programació:
- Tipus abstractes de dades i cost computacional
- Grafs, arbres i algorismes