Graph clustering and the nuclear Wasserstein metric

Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización con...

Full description

Autores:
Roux Uribe, Daniel de
Tipo de recurso:
Fecha de publicación:
2018
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/35098
Acceso en línea:
http://hdl.handle.net/1992/35098
Palabra clave:
Optimización matemática - Investigaciones
Matemáticas
Rights
openAccess
License
http://creativecommons.org/licenses/by-nc-sa/4.0/
id UNIANDES2_7df838b0e7a90faac44a7545bfb5303e
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/35098
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
spelling Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.http://creativecommons.org/licenses/by-nc-sa/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Velasco Gregory, Mauriciovirtual::16346-1Roux Uribe, Daniel de59f49b5e-d9be-4a5e-abd2-e8f3ceafb1de500Peña Briceño, Javier FranciscoRiascos Villegas, Alvaro José2020-06-10T09:34:51Z2020-06-10T09:34:51Z2018http://hdl.handle.net/1992/35098u821432.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización convexa. Damos garantías teóricas exactas para este problema cuando la métrica de Wasserstein es inducida por la norma nuclear y G se distribuye según el modelo estocástico por bloques. Finalmente presentamos nuestra implementación en Julia del algoritmo propuesto y mostramos su desempeño numérico en datos sintéticos.We study the problem of learning the cluster structure of a random graph G from an independent sample. We propose a Wasserstein robust formulation of this optimization problem and prove that it can be reformulated as a tractable convex optimization problem. We give theoretical exact recovery guarantees for this problem when the Wasserstein metric is induced by the nuclear norm and G is distributed according to the stochastic block model. Finally we present our Julia implementation of the proposed algorithm and show its numerical performance on synthetic data.Magíster en MatemáticasMaestríav, 52 hojasapplication/pdfengUniandesMaestría en MatemáticasFacultad de CienciasDepartamento de Matemáticasinstname:Universidad de los Andesreponame:Repositorio Institucional SénecaGraph clustering and the nuclear Wasserstein metricTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesishttp://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/TMOptimización matemática - InvestigacionesMatemáticasPublication32f6d723-63ca-49a1-a1ac-67b61e2a007avirtual::16346-132f6d723-63ca-49a1-a1ac-67b61e2a007avirtual::16346-1https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0001493107virtual::16346-1ORIGINALu821432.pdfapplication/pdf1335668https://repositorio.uniandes.edu.co/bitstreams/1a839f72-d523-472d-b8ab-ef71938452d8/download07661828cc1e005e899297d083aed4f7MD51THUMBNAILu821432.pdf.jpgu821432.pdf.jpgIM Thumbnailimage/jpeg6570https://repositorio.uniandes.edu.co/bitstreams/414cf041-10f9-4842-b5df-ef1a5becbe03/downloaddadb6fd41cad3dd8bf121aaf8062d658MD55TEXTu821432.pdf.txtu821432.pdf.txtExtracted texttext/plain92900https://repositorio.uniandes.edu.co/bitstreams/afa14998-3554-430b-b971-871088620a4f/downloadb0b5dc9198640093ef241bd42f1c3381MD541992/35098oai:repositorio.uniandes.edu.co:1992/350982024-05-15 11:00:08.579http://creativecommons.org/licenses/by-nc-sa/4.0/open.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co
dc.title.es_CO.fl_str_mv Graph clustering and the nuclear Wasserstein metric
title Graph clustering and the nuclear Wasserstein metric
spellingShingle Graph clustering and the nuclear Wasserstein metric
Optimización matemática - Investigaciones
Matemáticas
title_short Graph clustering and the nuclear Wasserstein metric
title_full Graph clustering and the nuclear Wasserstein metric
title_fullStr Graph clustering and the nuclear Wasserstein metric
title_full_unstemmed Graph clustering and the nuclear Wasserstein metric
title_sort Graph clustering and the nuclear Wasserstein metric
dc.creator.fl_str_mv Roux Uribe, Daniel de
dc.contributor.advisor.none.fl_str_mv Velasco Gregory, Mauricio
dc.contributor.author.none.fl_str_mv Roux Uribe, Daniel de
dc.contributor.jury.none.fl_str_mv Peña Briceño, Javier Francisco
Riascos Villegas, Alvaro José
dc.subject.keyword.es_CO.fl_str_mv Optimización matemática - Investigaciones
topic Optimización matemática - Investigaciones
Matemáticas
dc.subject.themes.none.fl_str_mv Matemáticas
description Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización convexa. Damos garantías teóricas exactas para este problema cuando la métrica de Wasserstein es inducida por la norma nuclear y G se distribuye según el modelo estocástico por bloques. Finalmente presentamos nuestra implementación en Julia del algoritmo propuesto y mostramos su desempeño numérico en datos sintéticos.
publishDate 2018
dc.date.issued.none.fl_str_mv 2018
dc.date.accessioned.none.fl_str_mv 2020-06-10T09:34:51Z
dc.date.available.none.fl_str_mv 2020-06-10T09:34:51Z
dc.type.spa.fl_str_mv Trabajo de grado - Maestría
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TM
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/1992/35098
dc.identifier.pdf.none.fl_str_mv u821432.pdf
dc.identifier.instname.spa.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.spa.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url http://hdl.handle.net/1992/35098
identifier_str_mv u821432.pdf
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.es_CO.fl_str_mv eng
language eng
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv http://creativecommons.org/licenses/by-nc-sa/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.es_CO.fl_str_mv v, 52 hojas
dc.format.mimetype.es_CO.fl_str_mv application/pdf
dc.publisher.es_CO.fl_str_mv Uniandes
dc.publisher.program.es_CO.fl_str_mv Maestría en Matemáticas
dc.publisher.faculty.es_CO.fl_str_mv Facultad de Ciencias
dc.publisher.department.es_CO.fl_str_mv Departamento de Matemáticas
dc.source.es_CO.fl_str_mv instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
instname_str Universidad de los Andes
institution Universidad de los Andes
reponame_str Repositorio Institucional Séneca
collection Repositorio Institucional Séneca
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/1a839f72-d523-472d-b8ab-ef71938452d8/download
https://repositorio.uniandes.edu.co/bitstreams/414cf041-10f9-4842-b5df-ef1a5becbe03/download
https://repositorio.uniandes.edu.co/bitstreams/afa14998-3554-430b-b971-871088620a4f/download
bitstream.checksum.fl_str_mv 07661828cc1e005e899297d083aed4f7
dadb6fd41cad3dd8bf121aaf8062d658
b0b5dc9198640093ef241bd42f1c3381
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1812134059234557952

Publicaciones similares