Xarxes Socials i Complexes

Esteu aquí

Crèdits
6
Tipus
  • MIRI: Complementària d'especialitat (Computació Avançada)
  • MDS: Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
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.

Professorat

Responsable

  • Ramon Ferrer Cancho ( )

Altres

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

Hores setmanals

Teoria
2
Problemes
0
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
4

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.

Continguts

  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

Metodologia docent

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ètode d'avaluació

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.

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Programming
Algorithms and data structures
Linear algebra
Probability and Statistics