Una teoria de l'agrupament espectral
Una teoria de l'agrupament espectral
Data
21 novembre 2018
h. 15.30 h
h. 15.30 h
Ubicació
Aula Màster del Campus Nord,
UPC
UPC
abstracte
Els algorismes d'agrupament espectral troben clústers en una xarxa determinada mitjançant l'explotació de propietats dels vectors propis de les matrius associades a la xarxa. Com a primer pas, es calcula una incrustació espectral, és a dir, un mapeig de nodes a punts en un espai real de dimensions baixes; llavors s'utilitzen algorismes d'agrupament geomètric com k-means per agrupar els punts corresponents als nodes.
Aquests algorismes funcionen tan bé que, en determinades aplicacions no relacionades amb l'anàlisi de xarxes, com ara la segmentació d'imatges, és útil associar una xarxa a les dades i després aplicar l'agrupació espectral a la xarxa. A més de la seva aplicació a la agrupació, les incrustacions espectrals són una eina valuosa per a la reducció de dimensions i la visualització de dades. El rendiment dels algorismes d'agrupament espectral s'ha justificat rigorosament quan s'aplica a xarxes procedents de determinats models generatius probabilistes.
Un desenvolupament més recent, que és el focus d'aquesta conferència, és una anàlisi del pitjor cas de l'agrupació espectral, que mostra que, per a cada gràfic que mostra una determinada estructura de clúster, aquesta estructura es pot trobar mitjançant algorismes geomètrics aplicats a una incrustació espectral. Aquests resultats generalitzen la desigualtat de Cheeger del graf (un resultat clàssic en la teoria de grafs espectrals) i tenen aplicacions addicionals en la teoria de la complexitat computacional i en matemàtiques pures.
Data
21 novembre 2018
h. 15.30 h
h. 15.30 h
Ubicació
Aula Màster del Campus Nord,
UPC
UPC
abstracte
Els algorismes d'agrupament espectral troben clústers en una xarxa determinada mitjançant l'explotació de propietats dels vectors propis de les matrius associades a la xarxa. Com a primer pas, es calcula una incrustació espectral, és a dir, un mapeig de nodes a punts en un espai real de dimensions baixes; llavors s'utilitzen algorismes d'agrupament geomètric com k-means per agrupar els punts corresponents als nodes.
Aquests algorismes funcionen tan bé que, en determinades aplicacions no relacionades amb l'anàlisi de xarxes, com ara la segmentació d'imatges, és útil associar una xarxa a les dades i després aplicar l'agrupació espectral a la xarxa. A més de la seva aplicació a la agrupació, les incrustacions espectrals són una eina valuosa per a la reducció de dimensions i la visualització de dades. El rendiment dels algorismes d'agrupament espectral s'ha justificat rigorosament quan s'aplica a xarxes procedents de determinats models generatius probabilistes.
Un desenvolupament més recent, que és el focus d'aquesta conferència, és una anàlisi del pitjor cas de l'agrupació espectral, que mostra que, per a cada gràfic que mostra una determinada estructura de clúster, aquesta estructura es pot trobar mitjançant algorismes geomètrics aplicats a una incrustació espectral. Aquests resultats generalitzen la desigualtat de Cheeger del graf (un resultat clàssic en la teoria de grafs espectrals) i tenen aplicacions addicionals en la teoria de la complexitat computacional i en matemàtiques pures.
Luca Trevisan, Universitat de Berkeley (EUA)
Bioesbós
Luca trevisan és professor d'enginyeria elèctrica i ciències de la computació a la UC Berkeley i científic sènior al Simons Institute for the Theory of Computing. Luca va estudiar a la Universitat Sapienza de Roma, va ser postdoctoral al MIT i al DIMACS, i va estar a la facultat de la Universitat de Columbia, UC Berkeley i Stanford, abans de tornar a Berkeley el 2014. La investigació de Luca és en ordinador teòric. ciència, i se centra en la complexitat computacional i els algorismes de gràfics. Luca va rebre el premi STOC'97 Danny Lewin (millor treball estudiantil), el premi Oberwolfach 2000 i la beca Sloan 2000. Va ser un ponent convidat al Congrés Internacional de Matemàtics de 2006.