Xarxes Socials i Complexes

Crèdits
6
Tipus
  • MDS: Optativa
  • MIRI: Complementària d'especialitat (Computació Avançada)
  • MEI: Optativa
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Web
www.cs.upc.edu/~CSN/
Networks are structures that show up where there is any kind of interaction: in social behavior, in biological, physical or chemical processes, among many others. Important real-world processes such as the spread of disease or people's buying patterns can be explained through the use and study of networks. This course will cover the fundamental aspects of networks: what are they and how can we measure them? What are their characteristics and properties? What type of processes are they able to carry out? How can we model them? Can we predict their behavior?

Summary of syllabus: (1) Network description: structural properties, types of networks, finding structure in networks. (2) Computational models of networks. (3) Processes on networks: search, diffusion, rumour spreading, etc.

Professorat

Responsable

  • Ramon Ferrer Cancho (rferrericancho@cs.upc.edu)

Altres

  • Argimiro Arratia Quesada (argimiro@cs.upc.edu)
  • Marta Arias Vicente (marias@cs.upc.edu)

Hores setmanals

Teoria
2
Problemes
0
Laboratori
1
Aprenentatge dirigit
0.4
Aprenentatge autònom
6.6

Competències

Competències Tècniques de cada especialitat

Computació avançada

  • CEE3.1 - Capacitat per a identificar barreres computacionals i analitzar la complexitat de problemes computacionals en diversos àmbits de la ciència i la tecnologia; així com per representar problemes d'alta complexitat en estructures matemàtiques que puguin ser tractades eficientment amb esquemes algorítmics.
  • CEE3.2 - Capacitat per utilitzar un espectre ampli i variat de recursos algorítmics per resoldre problemes d'alta dificultat algorísmica.
  • CEE3.3 - Capacitat per entendre les necessitats computacionals de problemes de disciplines diferents de la informàtica i efectuar contribucions significatives en equips multidisciplinaris que facin servir la computació.

    • Específiques comunes

  • CEC1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CEC2 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG3 - Capacitat per al modelatge matemàtic, càlcul i disseny experimental en centres tecnològics i d'enginyeria d'empresa, particularment en tasques de recerca i innovació en tots els àmbits de la Informàtica.

    • Competències Transversals

    Treball en equip

  • CTR3 - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.

    • Ús solvent dels recursos d'informació

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

    • Actitud adequada davant el treball

  • CTR5 - Tenir motivació per a la realització professional i per a afrontar nous reptes, tenir una visió àmplia de les possibilitats de la carrera professional en l'àmbit de l'enginyeria en informàtica. Sentir-se motivat per la qualitat i la millora contínua, i actuar amb rigor en el desenvolupament professional. Capacitat d'adaptació als canvis organitzatius o tecnològics. Capacitat de treballar en situacions de carència d'informació i/o amb restriccions temporals i/o de recursos.

    • Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

    • 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.
  • CB8 - Que els estudiants sàpiguen comunicar les seves conclusions i els coneixements i raons darreres que les sustenten- a públics especialitzats i no especialitzats d'una manera clara i sense ambigüitats.
  • CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma.

    • Objectius

    1. Aprendre, mitjançant la pràctica, el procés de preparació i escriptura d'un article científic
      Competències relacionades: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB8, CEC1, CEC2, CTR3, CTR4, CTR5, CTR6,
    2. Aprendre els índexs, mètodes i models bàsics del camp conegut avui com a ciència de xarxes.
      Competències relacionades: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB9, CEC1, CEC2, CTR5, CTR6,

    Continguts

    1. Introducción. ¿Qué son las redes? Medidas y modelos sencillos para redes.
      - Exemples de xarxes reals: xarxes socials, xarxes d'informació, xarxes tecnològiques i xarxes biològiques.
      - Terminologia: punts (vèrtexs, nodes, llocs, actors) i línies (arestes, arcs, enllaços, lligams,...).
      - Tipus de xarxes: xarxes no ponderades/ponderades, xarxes no dirigides/dirigides,...
      - Propietats clàssiques de les xarxes: el fenomen del món petit (mètriques de distància), distribució de graus heterogènia (distribució de graus de llei de potència, alta agrupació o transitivitat).
      - Models de xarxes clàssics: el model Erdös-Rényi, el model Watts-Strogatz, el model Barabási-Albert.
    2. La distribució de graus d'una xarxa i la seva anàlisi
      - La distribució de grau empírica i teòrica. Grau no dirigit, grau dins i grau fora.
      - Distribucions teòriques: família zeta, distribució binomial.
      - Ajust de la distribució de grau: ajust visual, regressió lineal i no lineal i màxima versemblança.
      - Introducció a la selecció de models estàndard: parsimònia versus qualitat d'ajust, criteri d'informació d'Akaike.
    3. Mesures de xarxes
      - Mètriques de distància: camins geodèsics, mètriques de distància locals (distància geodèsica mitjana, centralitat de proximitat), mètriques de distància globals (diàmetre, distància geodèsica mitjana, centralitat de proximitat mitjana). Algoritmes per calcular la distància.
      - Mètriques de clústering: transitivitat, clústering (mètriques diferents). Algoritmes per calcular la clústering.
      - Correlacions de grau: barreja assortativa enfront dissortativa per grau, mètriques de correlació de grau (correlació de Pearson vs. correlació de rang de Spearman, grau mitjà dels veïns més propers).
    4. Proves estadístiques de mesures de xarxa
      - Introducció a les proves d'hipòtesis: proves qualitatives versus quantitatives, famílies d'hipòtesis nul·les (model d'Erdös-Renyi, model de configuració, model de commutació,...), valors p.
      - Introducció a les proves de Monte Carlo: esquema general, generadors de nombres aleatoris uniformes, permutació uniformement aleatòria, gràfic aleatori d'Erdös-Rényi amb nombre constant i variable d'arestes.
      - El model de configuració o d'adaptació.
      - El model de commutació.
    5. Mesures avançades per a xarxes. Centralitat.
      Centralitat:
      - Nocions qualitatives de centralitat d'un node.
      - Definicions quantitatives de centralitat: centralitat de grau, centralitat de proximitat, centralitat d'intermediació, centralitat de vector propi i PageRank (google).
    6. Trobar l'estructura de comunitats a les xarxes
      - Introducció a l'estructura comunitària.
      - Com quantificar la qualitat d'una estructura comunitària: densitat intra-clúster versus inter-clúster. Altres mètriques: conductància, expansió, densitat interna, ràtio de tall, tall normalitzat, fracció de grau de sortida de Flake... i modularitat.
      - Mètodes per a la detecció de l'estructura comunitària: algoritmes de clústering jeràrquic (clústering jeràrquic aglomeratiu, mesures de similitud de nodes), algoritme de Girvan-Newman, algoritmes d'optimització de modularitat (la Q de modularitat, algoritmes per maximitzar la modularitat, el mètode de Louvain, optimització de modularitat espectral), algoritmes de partició de grafs (algoritmes de bisecció mínima, algoritme de Kernighan-Lin) i mètode de percolació de cliques.
    7. El problema de l'arranjament lineal mínim
      - Linear arrangements of networks: linear/Euclidean distance, metrics (mean dependency length).
      - Mean dependency length in trees: expectation in random linear arrangements, lower bounds, upper bounds (non-crossing trees),...
      - The minimum linear arrangement problem: cost function and complexity.
      - The minimum linear arrangement of trees: algorithms, particular cases.
      - Introduction to crossing theory for trees. Number of crossings: upper bound, expectation in random linear arrangements (the particular case of uniformly random trees).
    8. Dinàmica de xarxes
      Introduction to network dynamics:
      - Classic models that generate networks: the Barabáasi-Albert model (growth and preferential attachment), copying models, fitness based models and optimization models.
      - The Barabási-Albert model. The statistical properties: vertex degree as a function of time, the power-law degree distribution.
      - The copying model. The statistical properties: vertex degree as a function of time and degree distribution.
      - Fitness models. Fitness functions and degree distribution.
      - Optimization models. Trade-off between geodesic distance and link density. Cost function.

      Advanced network models:
      - Modifications of the Barabási-Albert model
      - Liu et al's hybrid model.
      - Bianconi-Barabási hybrid model.
      - Dorogovtsev-Mendes model (accelerated growth).
      - Other models.
    9. Mostreig en xarxes
      - Introduction to sampling: motivation and importance and goals.
      - Sampling strategies: random node selection, random edge selection, crawling-based.
      - Biases of sampling strategies.
      - How to compensate for biases or how to reduce them.
    10. Difusió d'epidèmies en xarxes
      - Introduction to the dynamics of epidemics: relevant questions and the full mixing assumption.
      - Classic epidemic models (full mixing): the SI model (the logistic growth equation), the SIR model and the SIS model. Thresholding phenomena.
      - Epidemic models over networks: homogeneous network models, scale-free network model for SIS and a general network model for SIS. Thresholding phenomena.
    11. Percolació i resiliència en xarxes
      - Introduction to percolation: percolation in lattices, giant cluster.
      - Network resilience upon node removal:
      - Uniform node removal: the configuration model (thresholding phenomena), Erdös-Rényi networs, scale-free networks.
      - Non-uniform node removal: random versus targeted attack, exponential versus scale-free network. Size of the giant cluster.
    12. Altres processos dinàmics en xarxes: passejos aleatoris i processos de difusió; búsqueda en redes.
      Other dynamic processes over networks: random walks and diffusion processes; search on networks

    Activitats

    Activitat Acte avaluatiu


    Desenvolupament teòric dels temes 1 a 12 del curs


    Objectius: 2
    Teoria
    30h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    15h

    Treball de laboratory sobre temes teòrics


    Objectius: 1 2
    Teoria
    0h
    Problemes
    0h
    Laboratori
    15h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    30h

    Projecte de recerca


    Objectius: 1 2
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    6h
    Aprenentatge autònom
    54h

    Metodologia docent

    Les sessions de teoria les durà a terme principalment el professor, ja sigui mitjançant la pissarra o projectant diapositives.

    El treball de laboratori es farà davant de l'ordinador. S'espera que els estudiants treballin en els seus deures i el professor explicarà tot el necessari per seguir la classe al principi de la sessió. Cada sessió de laboratori anirà acompanyada d'una guia completa que descriurà el treball que els estudiants han de fer.

    Tot el material rellevant per al curs estarà disponible al lloc web del curs.

    Mètode d'avaluació

    No hi haurà examen en aquest curs. La qualificació es fa completament mitjançant informes de diverses tasques al llarg del curs.

    S'espera que els estudiants lliurin 7 informes de treballs de laboratori aproximadament dues setmanes després de la sessió de laboratori corresponent, que compten per al 50% de la nota final. També tindrem un projecte de curs que els estudiants lliuraran cap al final del curs que representa el 50% de la nota final.
    Per cada informe de laboratori no lliurat, hi ha una penalització de 0,5 punts a la nota final. Per tant, si un estudiant no lliura 2 informes, es restarà 1 punt de la nota final. Les notes són sobre 10.

    La fórmula per calcular la nota final és, per tant:

    F = max[0, 0,1 * (L1 + L2 + L3 + L4 + L5) + 0,5 * CP - 0,5 * P]

    on Li, per a i=1..5, representa la nota dels 5 millors informes de laboratori, CP representa la nota del projecte de curs i P és el nombre d'informes de laboratori no lliurats.

    F és una nota entre 0 i 10.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    Programació
    Algoritmes i estructures de dades
    Àlgebra lineal
    Probabilitat i estadística