untitled

Métricas de complejidad de grafos para clasificación en múltiples dominios


Graph complexity measures for multi-domain network classification

Tabacman, Maximiliano

Director(a):
Krasnogor, Natalio - Loiseau, Irene
 
Institución otorgante:
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Fecha:
2016-05-02
Tipo de documento: 
Tesis Doctoral
 
Formato:
text; pdf
Idioma:
Inglés
Temas:
Computación / Teoría de Grafos - GRAFOS - REDES - COMPLEJIDAD - CLASIFICACION - METRICAS - AUTOMATIZACION - ALGORITMOS - MULTIPLES DOMINIOS
Descripción:
El objetivo de esta tesis es investigar y ofrecer nuevas ideas para clasificar redes complejas basadas en sus propiedades topológicas de gran escala. Estamos interesados en estudiar las propiedades de redes de diferentes dominios, y encontrar características comunes que son compartidas por las redes en cada una de ellas. Con las mismas pretendemos desarrollar algoritmos y técnicas que aprovechen los elementos comunes, para automatizar la clasificación de redes en sus respectivos dominios. Esta información también será de utilidad para determinar si una red artificial presenta las características esperadas para el dominio al que pretende pertenecer. Revisamos un gran número de métricas de complejidad encontradas en la literatura. De ellas, elegimos 13 que luego derivan en un total de 43 métricas. Creamos un conjunto de redes de distintas fuentes, con 240 redes distribuidas en 11 dominios. Aplicamos un análisis exhaustivo a las medidas obtenidas para ellas, analizamos su correlación y distribución estadística, e intentamos predecir las posibilidades de clasificación que tendría un algoritmo automático a la hora de discriminarlas correctamente en sus respectivos dominios. Intentamos determinar si las mediciones obtenidas pueden ser usadas para discriminar los distintos dominios estudiados. Para ello, presentamos 3 tipos de algoritmos de clasificación de la literatura (K Nearest Neighbors, Support Vector Machines y el sistema de Evolutionary Rule Learning BioHEL[9]). Las mediciones son utilizadas como valores de entrada para la tarea de clasificación de distinguir el dominio al que pertenece cada red. Además, para entender el potencial que tienen para clasificar dominios de redes, usamos el generador de grafos CiGRAM para crear un conjunto de 160 redes artificiales distribuidas en 8 dominios a modo de ejemplo. Analizamos su distribución estadística y ejecutamos los experimentos propuestos, donde algunos de los algoritmos logran una precisión de hasta 80%. Adicionalmente, observamos que es fácil interpretar los resultados que ofrece el sistema BioHEL, ya que su salida está compuesta de reglas legibles por una persona, que explican cómo clasificar redes en base a los valores de las métricas calculadas. Finalmente, aplicamos los experimentos propuestos usando las técnicas de clasificación revisadas, con los valores de métricas calculados para las redes reales elegidas. Observamos una clasificación de menor precisión con respecto a lo obtenido para las redes artificiales, y continuamos con escenarios experimentales adicionales para estudiar posibles mejoras, como eliminación de outliers y particionamiento manual de los conjunto de entrenamiento y prueba. Luego de ejecutarlos, a pesar de que en promedio los resultados siguen siendo peores a los obtenidos para las redes artificiales, un subconjunto de los experimentos presenta una precisión de 80% como habíamos obtenido anteriormente. Nuestras conclusiones permiten confirmar que es posible clasificar redes de distintos dominios considerando únicamente las mediciones obtenidas de un conjunto específico de métricas de complejidad, y también ofrecemos posibles mejoras a ser aplicadas en investigaciones futuras.
Identificador:
http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5978_Tabacman
Identificador único:
http://repositoriouba.sisbi.uba.ar/h/3465
Derechos:
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/2.5/ar/
Licencia de uso:
Licencia Creative Commons

Descargar texto: Tesis_5978_Tabacman.oai

Cita bibliográfica:

Tabacman, Maximiliano  (2016-05-02).     Métricas de complejidad de grafos para clasificación en múltiples dominios.  (Tesis Doctoral).    Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires.    [consultado:  ] Disponible en el Repositorio Digital Institucional de la Universidad de Buenos Aires:  <http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5978_Tabacman>