Redes Sociales y Complejas

Usted está aquí

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

Otros

  • Argimiro Arratia Quesada ( )
  • Marta Arias Vicente ( )

Horas semanales

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

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.

Contenidos

  1. Introduction. What are networks? Simple measures and models for networks
    - Examples of real networks: social networks, information networks, technological networks and biological networks.
    - Terminology: points (vertices, nodes, sites, actors) and lines (edges, arcs, links, bonds, ties,...).
    - Types of networks: unweighted/weighted networks, undirected/directed networks, ...
    - Classic network properties: the small-world phenomenon (distance metrics), heterogeneous degree distribution (power-law degree distribution, high clustering or transitivity.
    - Classic network models: the Erdös-Rényi model, the Watts-Strogatz model, the Barabási-Albert model.
  2. The degree distribution of a network and its analysis
    - The empirical and the theoretical degree distribution. Undirected degree, in-degree and out-degree.
    - Theoretical distributions: zeta family, binomial distribution.
    - Fitting of the degree distribution: visual fitting, linear and non-linear regression and maximum likelihood.
    - Introduction to standard model selection: parsimony versus quality of fit, Akaike information criterion.
  3. Measures of networks
    - Distance metrics: geodesic paths, local distance metrics (mean geodesic distance, closeness centrality), global distance metrics (diameter, mean geodesic distance, mean closeness centrality). Algorithms for computing distance.
    - Clustering metrics: transitivity, clustering (different metrics). Algorithms for computing clustering.
    - Degree correlations: assortative vs disassortative mixing by degree, degree correlation metrics (Pearson correlation vs Spearman rank correlation, mean degree of nearest neighbours.
  4. Statistical testing of network measures
    - Introduction to hypothesis testing: qualitative versus quantitative testing, families of null hypotheses (Erdös-Renyi model, configuration model, switching model,...), p-values.
    - Introduction to Monte Carlo testing: general scheme, uniform random number generators, uniformly random permutation, random Erdös-Rényi graph with constant and variable number of edges.
    - The configuration or matching model.
    - The switching model.
  5. Advanced measures for networks. Centrality.
    Centrality:
    - Qualitative notions of centrality of a node.
    - Quantitative definitions of centrality: degree centrality, closeness centrality, betweenness centrality, eigenvector centrality and PageRank (google).
  6. Finding community structure in networks
    - Introduction to community structure.
    - How to quantify the quality of a community structure: intra-cluster versus inter-cluster density. Other metrics: conductance, expansion, internal density, cut ratio, normalized cut, Flake's out degree fraction .... and modularity.
    - Methods for detection of community structure: hierarchical clustering algorithms (agglomerative hierarchical clustering, node similarity measures), Girvan-Newman algorithm, modularity optimization algorithms (the modularity Q, algorithms to maximize modularity, the Louvain method, spectral modularity optimization), graph partitioning algorithms (minimum bisection algorithms, Kernighan-Lin algorithm) and clique percolation method.
  7. The Minimum Linear Arrangement problem
    - 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. Network dynamics
    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. Sampling in networks
    - 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. Epidemic spreading in networks
    - 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. Percolation and network resilience
    - 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. Other dynamic processes over networks: random walks and diffusion processes; search on networks
    Other dynamic processes over networks: random walks and diffusion processes; search on networks

Metodología docente

The theory sessions will be done primarily by the professor using either the blackboard or projected slides.

The lab work will be done in front of the computer. Students are expected to be working on their assignment, and the professor will explain all that is necessary to follow the class in the beginning of the session. Each lab session will be accompanied by a thorough guide describing the work that the students need to do.

All the material relevant for the course will be available from the course's website.

Método de evaluación

There will be no exam in this course. Grading is done entirely through reports on various tasks throughout the course.

Students are expected to hand in 7 lab work reports about two weeks after its corresponding lab session, which count toward 50% of the final grade. We will also have a course project that the students will hand in towards the end of the course that accounts for 50% of the final grade.

The formula to compute the final grade is therefore:

0.1 * ( L1 + L2 + L3 + L4 + L5) + 0.5 * CP - (0.25 * P)

where Li, for i=1..5, stands for the grade for the best 5 lab reports, CP stands for grade of the course project, and P is the nr of lab reports not handed in.

For each lab report not handed in, there is a penalty of 0.25 points towards the final grade. So, if a student does not hand in 2 reports, then 0.5 points will be deducted from the final grade. Grades are over 10.

Bibliografía

Básica:

Complementaria:

Web links

Capacidades previas

Programming
Algorithms and data structures
Linear algebra
Probability and Statistics