Logo UAB

Anàlisi de Grafs i Xarxes

Codi: 106567 Crèdits: 6
2024/2025
Titulació Tipus Curs
2504392 Intel·ligència Artificial / Artificial Intelligence OB 2

Professor/a de contacte

Nom:
Josep Lladós Canet
Correu electrònic:
josep.llados@uab.cat

Equip docent

Cristina Perez Sola

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

Per a una millor seguiment de l'assignatura, és recomanable haver superat les assignatures de segon semestre de primer any " Enginyeria de Dades" i de primer semestre de segon any “Fonaments d'Aprenentatge Automàtic”. També és recomanable tenir competències bàsiques de programació adquirides en les assignatures prèvies de “Fonaments de Programació”.


Objectius

Les estructures de grafs són de gran utilitat en representació de dades a partir de les seves relacions. Els grafs son un llenguatge general per descriure i analizar entitats amb relacions/interaccions. Són de gran utilitat en la representació i navegació de xarxes socials, el modelatge de molècules, la representació geogràfica per programari de navegació, biometria, representació de coneixement, representació d’escenes, etc. A més, la teoria de grafs ofereix una metodologia robusta i matemàticament fonamentada per caracteritzar, recórrer o analitzar aquest tipus d'estructures. En aquesta assignatura es cobreixen els següents objectius: Adquirir coneixements en teoría básica de grafs, optimització de recorreguts, algorismes sobre grafs, mineria de dades per a grafs, grafs dinàmics, difusió i propagació de la informació en xarxes, cerca a internet, anàlisi de xarxes socials, comunitats i perfils d'usuaris públics, sistemes de recomanació.


Competències

  • Analitzar i resoldre problemes de manera efectiva, i generar propostes innovadores i creatives per aconseguir els objectius.
  • Conèixer i utilitzar de manera eficient les tècniques i eines de representació, manipulació, anàlisi i gestió de dades a gran escala.
  • Introduir canvis en els mètodes i els processos de l’àmbit de coneixement per donar respostes innovadores a les necessitats i demandes de la societat. 
  • Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.

Resultats d'aprenentatge

  1. Analitzar i resoldre problemes de manera efectiva, i generar propostes innovadores i creatives per aconseguir els objectius.
  2. Aplicar tècniques de mineria de dades específiques per a grafs, seleccionant adequadament els algoritmes en funció de l’objectiu de l’anàlisi, el volum de les dades a processar i les capacitats de processament disponibles.
  3. Conèixer les eines bàsiques de manipulació de diferents tipus de dades estructurades, semiestructurades i no estructurades.
  4. Ponderar els riscos i les oportunitats de les propostes de millora tant pròpies com alienes.
  5. Proposar noves maneres de mesurar l’èxit o el fracàs de la implementació de propostes o idees innovadores.
  6. Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes destacats d'índole social, científica o ètica.
  7. Utilitzar adequadament els mètodes de visualització de dades.

Continguts

Tema 1. Introducció. Definicions, conceptes, representacions.

Tema 2. Mètriques en grafs. Algorismes de centralitat i prestigi (Degree Centrality, Closeness Centrality, Betweenness Centrality).

Tema 3. Generació de grafs sintètics. Grafs aleatoris. Síntesi de grafs.

Tema 4. Visualització de grafs. Algorismes d'anàlisi de layout. Visuaització amb NetworkX. Visualització amb Gephi.

Tema 5. Cerca i recorreguts. Graph tranversal (Breadth First Search, Depth Firs Search), Shortest Path, A*, Minimum Spanning Tree, Random Walk.

Tema 6. Cerca a internet. Ranking i rellevància per models web. Algorisme PageRank. Crawling. Sistemes de recomanació.

Tema 7. Algorismes per detecció de comunitats i nodes influents. Operacions i mesures de comunitats. Graph clustering. Subgrups comuns. 

Tema 8. Propagació d’etiquetes i difusió en grafs. Models de difusió. Models epidemiològics. Belief propagation. Message passing.

Tema 9. Principis de Machine Learning basat en grafs. Matching, kernels i embeddings.

Tema 10. Cas pràctic.


Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes de problemes 15 0,6 1, 2, 7, 5, 6, 3, 4
Classes de teoria 30 1,2 2, 7, 6, 3
Seminaris i pràctiques 15 0,6 1, 2, 7, 5, 3, 4
Tipus: Supervisades      
Preparació problemes/seminaris 15 0,6 1, 2, 7, 5, 6, 3, 4
Tutories 15 0,6 1, 2, 7, 5, 6, 3, 4
Tipus: Autònomes      
Estudi / preparació examen 25 1 1, 2, 7, 5, 6, 3, 4
Treball personal 30 1,2 1, 2, 7, 5, 6, 3, 4

L'assignatura consta de 4 hores setmanals presencials (dues sessions de 2 hores cadascuna). Les classes es realitzaran en un aula amb ordinadors (o es recomanarà que l’estudiantat disposi de portàtil a l’aula). No es distingeix entre horaris de teoria, problemes i pràctiques de laboratori en horaris i aula diferenciats, sinó que s’aniran alternant segons convingui a la mateixa aula. De manera general, es dedicarà una setmana a cada tema (en alguns temes seran dues setmanes). Per cada tema s’introduiran els conceptes teòrics, partint de materials que es recomanarà haver mirat prèviament, alternant amb activitats més aplicades (resolució de problemes o seminaris). Es fomentarà la participació activa en la resolució de problemes/exercicis, treballant-los a l’aula, i fomentant l’exposició i el debat analítics dels resultats. Algunes sessions, principalment les últimes del curs, consistiran en seminaris de treball més pràctic, on es plantejarà un problema a resoldre de caràcter més general, que requereixi el disseny i implementació d’una solució a partir de la combinació dels conceptes teòrics. Per facilitar el seguiment, el primer dia de curs es distribuirà un calendari detallat de sessions.

Sessions de teoria. Consisteix en classes magistrals amb material multimèdia disponible al Campus Virtual de la UAB. L’objectiu principal d’aquestes classes és introduir les nocions bàsiques que han de permetre a l’alumne/a agafar una visió real de la teoria de grafs i la seva aplicació en sistemes de cerca d’informació, en particular a internet. Per fomentar sessions més interactives, i validar que s’adquireixen els coneixements, es distribuiran prèviament materials a través del campus virtual, recomanant que s’hagin mirat prèviament a la sessió. Durant la sessió de teoria, s’introduiran activitats pràctiques (resolució d’exercicis o casos pràctics més extensos), i altres activitats de seguiment (qüestionaris interactius).

Sessions de problemes. Durant el curs s’alternaran les sessions de classes magistrals amb la resolució d’exercicis en front de l’ordinador, amb eines de suport com ara l’entorn NetworkX. Seran exercicis que permetran monitoritzar la comprensió dels continguts teòrics. Es proporcionarà una col·lecció d’exercicis com a base de treball. Tot i no ser una divisió estricta, de les dues sessions setmanals, una es dedicarà més a continguts teòrics, i una altra a treballar problemes del tema corresponent. Hi podrà haver avaluació del lliurament d’algun exercici (anunciant prèviament quins són els que els estudiants hauran de lliurar).

Seminaris / casos pràctics. Algunes sessions es dedicaran a resoldre un problema més ampli i general, que requereixi la combinació de diverses eines vistes en els temes corresponents. En els seminaris es promou fonamentalment la capacitat d’anàlisi i síntesi, així com el raonament crític i la presa de decisions de l’alumne front a la resolució del problema. Hi haurà un cas pràctic que correspon a l’últim tema del curs. A mig curs pot haver un cas pràctic més curs que cobreixi els primers temes.

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.


Avaluació

Activitats d'avaluació continuada

Títol Pes Hores ECTS Resultats d'aprenentatge
Dos examens parcials 50% 4 0,16 1, 2, 7, 5, 6, 3, 4
Presentació treballs pràctics i seminaris 50% 1 0,04 1, 2, 7, 5, 3, 4

L’avaluació de l’assignatura (sobre 10 punts) constarà de les següents proves avaluatòries:

Exàmens parcials (N1). Es faran dos exàmens parcials durant el curs (E1 i E2). Els exàmens contindran tant preguntes de conceptes teòrics com exercicis de l’estil dels que s’hauran fet a classe. La nota mínima per superar cada examen és de 5. En cas que no se superi un dels dos parcials, es disposarà d’un examen de recuperació a final de curs de la part no superada. Correspon a un 50% de la nota final.

Proves basades en exercicis a classes de problemes (N2). Se solucionaran qüestionaris, que poden ser on-line, i/o resolució de problemes addicionals als vistos a classe. Forma part de l’avaluació continuada, i per tant no és recuperable. Correspon a un 10% de la nota final.

Lliurament d'un petit projecte a partir del treball dels seminaris. En els seminaris s’abordarà un cas pràctic de forma tutoritzada. S’haurà de lliurar al final el resultat del treball. Aquest treball es farà en grup. Forma part de l’avaluació continuada i no té recuperació, però es consideraran mecanismes de recuperació o compensació en determinats casos. Correspon a un 40% de la nota final.

La nota final de l’assignatura es calcularà de la següent manera:

NF=0,5*N1+0,1*N2+0,4*N3

Per aprovar l’assignatura és necessari haver aconseguit una puntuació mínima de 5 en totes les qualificacions, així com en les proves parcials per alliberar matèria que s'estableixin al llarg del curs. A criteri dels professors/res es podrà, però, establir compensacions entre les notes N1, N2 i N3.

L'assignatura serà avaluada com a No Avaluable només en el cas que l'alumne no s'hagi presentat a cap de les proves d'avaluació contemplades ni hagi lliurat totalment o parcialment els treballs.

En cas de no superar l'assignatura degut a que alguna de les activitats d'avaluació no arriba a la nota mínima requerida, la nota numèrica de l'expedient serà el valor menor entre 4.5 i la mitjana ponderada de les notes. Amb les excepcions de que s'atorgarà la qualificació de "no avaluable" als/les estudiants que no participin en cap de les activitats d'avaluació, i de que la nota numèrica de l'expedient serà el valor menor entre 3.0 i la mitjana ponderada de les notes en cas que l'estudiant hagi comès irregularitats en un acte d'avaluació (i per tant no serà possible l'aprovat per compensació).

S'atorgaran les Matrícules d'Honor dins dels màxims admesos per la normativa de la UAB (en funció del número de matriculats) a les notes més altes iguals o superiors a 9.

Per a cada activitat d’avaluació, s’indicarà un lloc, data i hora de revisió en la que l'estudiant podrà revisar l’activitat amb el professor/a. En aquest context, es podran fer reclamacions sobre la nota de l’activitat, que seran avaluades pel professorat responsable de l’assignatura. Si l'estudiant no es presenta a aquesta revisió, no es revisarà posteriorment aquesta activitat.

Veure apartat "PLAGI" sobre mesures en casos d'irregularitats per plagi en les activitats d'avaluació.

RECUPERACIONS:

Examens parcials (N1). Es faran dos exàmens parcials de teoria alliberatoris durant hores lectives. Els alumnes que no superin aquesta prova (amb nota igual o superior a 5), disposaran d'un examen de recuperació en la data d'avaluació final programada per la titulació.

Proves basades en exercicis i en cas pràctic (N2 i N3). El treball d’exercicis i pràctic s'avalua en forma d'avaluació continuada durant el seguiment a classe. Per tant no hi haurà cap activitat de recuperació al final del curs.

DATES D'AVALUACIÓ:

Les dates d'avaluació i lliurament de treballs es publicaran al campus virtual i poden estar subjectes a canvis de programació per motius d'adaptació a possibles incidències. Sempre s'informarà al campus virtual sobre aquests canvis ja que s'entén que és el mecanisme habitual d'intercanvi d'informació entre professorat i estudiants.

ALUMNES REPETIDORS:

No es guarden notes parcials (teoria o pràctiques) d'un curs per l'altre. Tanmateix, a criteri del professor i en funció de les avaluacions de cursos previs, es podran establir compensacions. Aquesta informació s'anunciarà el dia de la presentació de l'assignatura, i al campus virtual.

PLAGI:

Sense perjudici d'altres mesures disciplinàries que s'estimin oportunes, i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per un estudiant que puguin conduir a una variació de la qualificació es qualificaran amb un zero (0). Les activitats d'avaluació qualificades d'aquesta forma i per aquest procediment no seran recuperables. Si és necessari superar qualsevol d'aquestes activitats d'avaluació per aprovar l'assignatura, aquesta assignatura quedarà suspesa directament, sense oportunitat de recuperar-la en el mateix curs. Aquestes irregularitats inclouen, entre d'altres:

  • la còpia total o parcial d'una pràctica, informe, o qualsevol altra activitat d'avaluació;
  • deixar copiar;
  • presentar un treball de grup no fet íntegrament pels membres del grup;
  • presentar com a propis materials elaborats per un tercer, encara que siguin traduccions o adaptacions, i en general treballs amb elements no originals i exclusius de l'estudiant;
  • tenir dispositius de comunicació (com telèfons mòbils, smart watches, etc.) accessibles durant les proves d'avaluació teòriques-pràctiques individuals (exàmens).

En resum: copiar, deixar copiar o plagiar en qualsevol de les activitats d'avaluació equival a un SUSPENS amb nota inferior a 3,0.

ACLARIMENT FINAL:

Per qualsevol dubte o discrepància, prevaldrà la informació més actualitzada que es comunicarà el dia de la presentació de l'assignatura i que es publicarà al campus virtual.


Bibliografia

Els continguts de l’assignatura explicats a classe s’extreuen de diferents fonts. Molts materials són en línia, extrets de materials multimèdia, vídeos, etc. Durant el curs, es proporcionaran els materials de confecció pròpia necessaris per al seguiment de l’assignatura a través del campus virtual. També es proporcionaran enllaços a documentació en línia, programari per als exercicis pràctics, etc. en format lliure.

Llibres en línia d’interès:


Programari

Per a la resolució dels problemes i casos pràctics s’utilitza programari obert com ara Gephi, i la llibreria NetworkX en Python. Alguns exercicis de classe es distribuiran amb la plataforma Google Colab.


Llista d'idiomes

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 711 Anglès segon quadrimestre tarda
(PLAB) Pràctiques de laboratori 711 Anglès segon quadrimestre tarda
(PLAB) Pràctiques de laboratori 712 Anglès segon quadrimestre tarda
(TE) Teoria 71 Anglès segon quadrimestre tarda