Redes Sociales y Complejas

Créditos
6
Tipos
  • MDS: Optativa
  • MIRI: Complementaria de especialidad (Computación Avanzada)
  • MEI: Optativa
Requisitos
Esta asignatura no tiene requisitos , pero tiene capacidades previas
Departamento
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.

Profesorado

Responsable

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

Otros

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

Horas semanales

Teoría
2
Problemas
0
Laboratorio
1
Aprendizaje dirigido
0.4
Aprendizaje autónomo
6.6

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.1 - Capacidad para identificar barreras computacionales y analizar la complejidad de problemas computacionales en diversos ámbitos de la ciencia y la tecnología; así como para representar problemas de alta complejidad en estructuras matemáticas que puedan ser tratadas eficientemente con esquemas algorítmicos.
  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

    • Específicas comunes

  • CEC1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CEC2 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Técnicas Genéricas

    Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

    • Competencias Transversales

    Trabajo en equipo

  • CTR3 - Ser capaz de trabajar como miembro de un equipo, ya sea como un miembro más, o realizando tareas de dirección con la finalidad de contribuir a desarrollar proyectos con pragmatismo y sentido de la responsabilidad, asumiendo compromisos teniendo en cuenta los recursos disponibles.

    • Uso solvente de los recursos de información

  • CTR4 - Gestionar la adquisición, la estructuración, el análisis y la visualización de datos e información del ámbito de la ingeniería informática y valorar de forma crítica los resultados de esta gestión.

    • Actitud frente al trabajo

  • CTR5 - Tener motivación para la realización profesional y para afrontar nuevos retos, así como una visión amplia de las posibilidades de la carrera profesional en el ámbito de la Ingeniería en Informática. Tener motivación por la calidad y la mejora continua, y actuar con rigor en el desarrollo profesional. Capacidad de adaptación a los cambios organizativos o tecnológicos. Capacidad de trabajar en situaciones de falta de información y/o con restricciones temporales y/o de recursos.

    • Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

    • Básicas

  • CB6 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.
  • CB8 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

    • Objetivos

    1. Aprender, mediante la práctica, el proceso de preparación y redacción de un artículo científico.
      Competencias relacionadas: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB8, CEC1, CEC2, CTR3, CTR4, CTR5, CTR6,
    2. Aprender los índices, métodos y modelos básicos del campo conocido hoy como ciencia de redes.
      Competencias relacionadas: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB9, CEC1, CEC2, CTR5, CTR6,

    Contenidos

    1. Introducció. Què són les xarxes? Mesures i models simples per a xarxes
      - Ejemplos de redes reales: redes sociales, redes de información, redes tecnológicas y redes biológicas.
      - Terminología: puntos (vértices, nodos, sitios, actores) y líneas (aristas, arcos, enlaces, vínculos, etc.).
      - Tipos de redes: redes no ponderadas/ponderadas, redes no dirigidas/dirigidas, etc.
      - Propiedades clásicas de las redes: el fenómeno del mundo pequeño (métricas de distancia), distribución heterogénea del grado (distribución de grado de ley de potencias), alta agrupación o transitividad.
      - Modelos clásicos de redes: el modelo de Erdös-Rényi, el modelo de Watts-Strogatz y el modelo de Barabási-Albert.
    2. La distribución de grados de una red y su análisis
      - Distribución de grados empírica y teórica. Grado no dirigido, grado de entrada y grado de salida.
      - Distribuciones teóricas: familia zeta, distribución binomial.
      - Ajuste de la distribución de grados: ajuste visual, regresión lineal y no lineal, y máxima verosimilitud.
      - Introducción a la selección de modelos estándar: parsimonia frente a calidad de ajuste, criterio de información de Akaike.
    3. Medidas de redes
      - Métricas de distancia: rutas geodésicas, métricas de distancia local (distancia geodésica media, centralidad de cercanía), métricas de distancia global (diámetro, distancia geodésica media, centralidad de cercanía media). Algoritmos para el cálculo de la distancia.
      - Métricas de agrupamiento: transitividad, agrupamiento (diferentes métricas). Algoritmos para el cálculo del agrupamiento.
      - Correlaciones de grado: mezcla asortativa frente a disasortativa por grado, métricas de correlación de grado (correlación de Pearson vs. correlación de rangos de Spearman, grado medio de los vecinos más cercanos).
    4. Pruebas estadísticas de medidas de red
      - Introducción a la prueba de hipótesis: pruebas cualitativas frente a cuantitativas, familias de hipótesis nulas (modelo de Erdös-Rényi, modelo de configuración, modelo de conmutación, etc.), valores p.
      - Introducción a las pruebas de Monte Carlo: esquema general, generadores de números aleatorios uniformes, permutación aleatoria uniforme, grafo aleatorio de Erdös-Rényi con número constante y variable de aristas.
      - El modelo de configuración o de emparejamiento.
      - El modelo de conmutación.
    5. Medidas avanzadas para redes. Centralidad.
      Centralidad:
      - Nociones cualitativas de centralidad de un nodo.
      - Definiciones cuantitativas de centralidad: centralidad de grado, centralidad de cercanía, centralidad de intermediación, centralidad de vector propio y PageRank (Google).
    6. Encontrar la estructura de comunidades en las redes
      - Introducción a la estructura de comunidades.
      - Cómo cuantificar la calidad de la estructura de una comunidad: densidad intraclúster frente a densidad interclúster. Otras métricas: conductancia, expansión, densidad interna, índice de corte, corte normalizado, fracción de grado de Flake y modularidad.
      - Métodos para la detección de la estructura de comunidades: algoritmos de agrupamiento jerárquico (agrupamiento jerárquico aglomerativo, medidas de similitud de nodos), algoritmo de Girvan-Newman, algoritmos de optimización de la modularidad (modularidad Q, algoritmos para maximizar la modularidad, método de Louvain, optimización espectral de la modularidad), algoritmos de partición de grafos (algoritmos de bisección mínima, algoritmo de Kernighan-Lin) y método de percolación de cliques.
    7. El problema de la disposición lineal mínima
      - 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 redes
      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. Muestreo en redes
      - 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ón de epidemias en redes
      - 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ón y resiliencia de redes
      - 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. Otros procesos dinámicos en redes: paseos aleatorios y procesos de difusión; búsqueda en redes.
      Other dynamic processes over networks: random walks and diffusion processes; search on networks

    Actividades

    Actividad Acto evaluativo


    Desarrollo teórico de los temas 1 a 12 del curso


    Objetivos: 2
    Teoría
    30h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    15h

    Trabajo de laboratorio sobre temas teóricos


    Objetivos: 1 2
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    15h
    Aprendizaje dirigido
    0h
    Aprendizaje autónomo
    30h

    Proyecto de investigación


    Objetivos: 1 2
    Teoría
    0h
    Problemas
    0h
    Laboratorio
    0h
    Aprendizaje dirigido
    6h
    Aprendizaje autónomo
    54h

    Metodología docente

    Las sesiones teóricas serán impartidas principalmente por el profesor, quien utilizará la pizarra o diapositivas proyectadas.

    Las prácticas de laboratorio se realizarán frente a la computadora. Se espera que los estudiantes trabajen en su tarea, y el profesor explicará todo lo necesario para seguir la clase al comienzo de cada sesión. Cada práctica de laboratorio irá acompañada de una guía detallada que describe el trabajo que los estudiantes deben realizar.

    Todo el material relevante para el curso estará disponible en la pagina web del curso.

    Método de evaluación

    En este curso no habrá examen. La calificación se basa exclusivamente en informes sobre diversas tareas a lo largo del curso.

    Se espera que los estudiantes entreguen 7 informes de prácticas de laboratorio aproximadamente dos semanas después de su sesión correspondiente, los cuales representan el 50% de la calificación final. También habrá un proyecto final que los estudiantes entregarán al final del curso y que representa el 50% de la calificación final.
    Por cada informe de laboratorio no entregado, se restarán 0.5 puntos de la calificación final. Por lo tanto, si un estudiante no entrega 2 informes, se le descontará 1 punto de la calificación final. Las calificaciones son sobre 10.

    La fórmula para calcular la calificación final es, por lo tanto:

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

    donde L1, para i=1..5, representa la calificación de los 5 mejores informes de laboratorio, CP representa la calificación del proyecto final y P es el número de informes de laboratorio no entregados.

    F es una nota entre 0 y 10.

    Bibliografía

    Básico

    Complementario

    Web links

    Capacidades previas

    Programación
    Algoritmos y estructuras de dades.
    álgebra lineal
    Probabilidad y estadística