Anàlisi de Grafs i Cerca d'Informació
Codi: 104363 Crèdits: 6| Titulació | Tipus | Curs | Semestre |
|---|---|---|---|
| 2503758 Enginyeria de Dades | OB | 2 | 1 |
Professor/a de contacte
- Nom:
- Josep Lladós Canet
- Correu electrònic:
- Josep.Llados@uab.cat
Utilització d'idiomes a l'assignatura
- Llengua vehicular majoritària:
- català (cat)
- Grup íntegre en anglès:
- No
- Grup íntegre en català:
- Sí
- Grup íntegre en espanyol:
- No
Altres indicacions sobre les llengües
Molts dels materials distribuits són en anglès.Equip docent
- Josep Lladós Canet
- Pau Riba Fierrez
- Jordi Herrera Joancomarti
Prerequisits
Per a una millor seguiment de l'assignatura, és necessari haver superat l'assignatura de segon semestre de primer any "Grafs, topologia i geometria discreta" on s'explica la teoria bàsica de grafs, optimització de recorreguts, algorismes sobre grafs i complexitat dels algorismes i problemes. Durant el semestre, l'assignatura d'Estructures de Dades proporciona coneixements complementaris sobre les estructures de dades per a l'emmagatzematge i gestió de grafs.
Objectius
Les estructures de grafs són de gran utilitat en representació de dades a partir de les seves relacions. 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 (reconeixement d'empremtes dactilars), representació de coneixement en Intel·ligència Artificial, 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 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 les dades de forma eficient per al desenvolupament de sistemes intel·ligents amb capacitat d’aprenentatge autònom i/o per mineria de dades.
- Desenvolupar un pensament i un raonament crític i saber comunicar-los de manera efectiva, tant en les llengües pròpies com en anglès.
- Prevenir i solucionar problemes, adaptar-se a situacions imprevistes i prendre decisions.
- 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
- 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 per processar i les capacitats de processament disponibles.
- Desenvolupar un pensament i un raonament crític i saber comunicar-los de manera efectiva, tant en les llengües pròpies com en anglès.
- Escollir els algoritmes que permeten recollir dades en forma de graf en funció de l'impacte que produeixen sobre les característiques de les dades capturades
- Prevenir i solucionar problemes, adaptar-se a situacions imprevistes i prendre decisions.
- 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.
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. Plataforma 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.
Tema 7. Algorismes per detecció de comunitats i nodes influents. Graph clustering. Subgrups comuns. Reputació.
Tema 8. Propagació d’etiquetes i difusió en grafs. Models de difusió. Models epidemiològics. Belief propagation. Message passing.
Tema 9. Reconeixement basat en grafs. Matching, kernels i embeddings.
Tema 10. Cas pràctic: grafs i xarxes socials.
Metodologia
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 sobre grafs i xarxes socials. A mig curs pot haver un cas pràctic més curs que cobreixi els primers temes.
CLASSES ONLINE
Atesa la situació d’incertesa provocada per la COVID-19, i la possibilitat que no tota la docència es pugui desenvolupar en modalitat presencial, les sessions anteriors poden haver d’adaptar-se a modalitat on-line a través de plataformes de videoconferència. Qualsevol modificació que afecti al format i horaris, s’informarà a través del campus virtual i a l’inici del curs.
Activitats formatives
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Classes de problemes | 15 | 0,6 | 1, 2, 3, 4, 5 |
| Classes de teoria | 30 | 1,2 | 1, 3, 5 |
| Seminaris / casos pràctics | 15 | 0,6 | 1, 2, 3, 4, 5 |
| Tipus: Supervisades | |||
| Preparació problemes/seminaris | 15 | 0,6 | 1, 2, 3, 4, 5 |
| Tutories | 15 | 0,6 | 1, 2, 3, 4, 5 |
| Tipus: Autònomes | |||
| Estudi / preparació examen | 22,5 | 0,9 | 1, 2, 3, 4, 5 |
| Treball personal | 30 | 1,2 | 1, 2, 3, 4, 5 |
Avaluació
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 20% 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 30% de la nota final.
La nota final de l’assignatura es calcularà de la següent manera:
NF=0,5*N1+0,2*N2+0,3*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.
Activitats d'avaluació
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Dues proves parcials | 50% | 3 | 0,12 | 1, 3, 5 |
| Proves basades en casos pràctics als seminaris | 30% | 3 | 0,12 | 1, 2, 3, 4, 5 |
| Proves basades en exercicis a la classe de problemes | 20% | 1,5 | 0,06 | 1, 2, 3, 4, 5 |
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.