Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | computacion |
| Título: | Métricas de complejidad de grafos para clasificación en múltiples dominios |
| Título alternativo: | Graph complexity measures for multi-domain network classification |
| Autor: | Tabacman, Maximiliano |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la Web: | 2016-09-02 |
| Fecha de defensa: | 2016-05-02 |
| Fecha en portada: | 2015 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Krasnogor, Natalio; Loiseau, Irene |
| Jurado: | Lin, Min Chih; Moscato, Pablo; Gutiérrez, Marisa |
| Idioma: | Inglés |
| Palabras clave: | GRAFOS; REDES; COMPLEJIDAD; CLASIFICACION; METRICAS; AUTOMATIZACION; ALGORITMOS; MULTIPLES DOMINIOSGRAPHS; NETWORKS; COMPLEXITY; CLASSIFICATION; MEASURES; AUTOMATION; ALGORITHMS; MULTI-DOMAIN |
| Tema: | computación/teoría de grafos
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n5978_Tabacman |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5978_Tabacman.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n5978_Tabacman |
| Ubicación: | Dep.COM 005978 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Tabacman, Maximiliano. (2015). Métricas de complejidad de grafos para clasificación en múltiples dominios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n5978_Tabacman |
Resumen:
El objetivo de esta tesis es investigar y ofrecer nuevas ideas para clasificarredes complejas basadas en sus propiedades topológicas de gran escala. Estamos interesados en estudiar las propiedades de redes de diferentesdominios, y encontrar características comunes que son compartidas por lasredes en cada una de ellas. Con las mismas pretendemos desarrollar algoritmosy técnicas que aprovechen los elementos comunes, para automatizarla clasificación de redes en sus respectivos dominios. Esta informacióntambién será de utilidad para determinar si una red artificial presenta lascaracterísticas esperadas para el dominio al que pretende pertenecer. Revisamos un gran número de métricas de complejidad encontradas enla literatura. De ellas, elegimos 13 que luego derivan en un total de 43métricas. Creamos un conjunto de redes de distintas fuentes, con 240 redesdistribuidas en 11 dominios. Aplicamos un análisis exhaustivo a lasmedidas obtenidas para ellas, analizamos su correlación y distribución estadística, e intentamos predecir las posibilidades de clasificación que tendríaun algoritmo automático a la hora de discriminarlas correctamente en susrespectivos dominios. Intentamos determinar si las mediciones obtenidas pueden ser usadaspara 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 latarea de clasificación de distinguir el dominio al que pertenece cada red. Además, para entender el potencial que tienen para clasificar dominiosde redes, usamos el generador de grafos CiGRAM para crear un conjuntode 160 redes artificiales distribuidas en 8 dominios a modo de ejemplo. Analizamos su distribución estadística y ejecutamos los experimentospropuestos, donde algunos de los algoritmos logran una precisión de hasta 80%. Adicionalmente, observamos que es fácil interpretar los resultados queofrece el sistema BioHEL, ya que su salida está compuesta de reglas legiblespor una persona, que explican cómo clasificar redes en base a los valores delas métricas calculadas. Finalmente, aplicamos los experimentos propuestos usando las técnicasde clasificación revisadas, con los valores de métricas calculados para lasredes reales elegidas. Observamos una clasificación de menor precisióncon respecto a lo obtenido para las redes artificiales, y continuamos conescenarios experimentales adicionales para estudiar posibles mejoras, comoeliminación de outliers y particionamiento manual de los conjunto de entrenamientoy prueba. Luego de ejecutarlos, a pesar de que en promedio losresultados siguen siendo peores a los obtenidos para las redes artificiales,un subconjunto de los experimentos presenta una precisión de 80% comohabíamos obtenido anteriormente. Nuestras conclusiones permiten confirmar que es posible clasificar redesde distintos dominios considerando únicamente las mediciones obtenidas deun conjunto específico de métricas de complejidad, y también ofrecemosposibles mejoras a ser aplicadas en investigaciones futuras.
Abstract:
The objective of this thesis is to research and offer insights into the possibilitiesof classifying complex networks based on their large scale topologicalfeatures. We are interested in studying the properties of networks from differentdomains, and find common characteristics that may be shared by thenetworks in each of them. With them, we aim to develop algorithms andtechniques that take advantage of the shared features, to automate the classification of networks to their respective domains. This information wouldalso be useful in determining if an artificial network shares the expectedcharacteristics of its intended domain. We research and review a large number of complexity measures from theliterature. From them, we choose 13 that are then derived to reach a totalof 43 measures. We created a network data set from different sources, with 240 networks distributed across 11 domains. Exhaustive analysis is appliedto the measurements obtained from them, to analyze their correlation andstatistical distribution, and attempt to predict the classification possibilitiesan automated algorithm might have of correctly discriminating between thedomains. We attempt to determine if the measures computed can be used as discriminatorsbetween the domains under study. To that end, we present 3different classification algorithms from the literature (K Nearest Neighbors, Support Vector Machines and the Evolutionary Rule Learning system BioHEL[9]). The measures obtained are used as the input for the classificationtask of distinguishing the domain to which each network belongs. Furthermore, to understand their potential ability to correctly classifynetwork domains, we use the CiGRAM graph generator to build a setof 160 artificial networks distributed across 8 sample domains. We analyzetheir statistical distribution, and run the experiments proposed, where someof the algorithms presented achieve up to 80% accuracy. Moreover, weobserve the ease of interpretation in the results offered by the BioHELsystem, since its output is composed of human readable rules that explainhow to classify the networks based on their computed measures. Finally, we apply the proposed experiments using the classification techniquesreviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtainedfor the artificial networks, and continue with additional experimentalscenarios to study possible improvements, such as outlier elimination, andmanual partitioning of the training and testing sets. After running them,we observe that despite the average results are still below those obtainedfor artificial networks, a subset of the experiments present the previouslyattained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into differentdomains just by considering the measurements obtained from a speciFinally, we apply the proposed experiments using the classification techniquesreviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtainedfor the artificial networks, and continue with additional experimentalscenarios to study possible improvements, such as outlier elimination, andmanual partitioning of the training and testing sets. After running them,we observe that despite the average results are still below those obtainedfor artificial networks, a subset of the experiments present the previouslyattained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into differentdomains just by considering the measurements obtained from a specificset of complexity measures, and we also offer a number of possible improvementsin future related research.
Citación:
---------- APA ----------
Tabacman, Maximiliano. (2015). Métricas de complejidad de grafos para clasificación en múltiples dominios. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n5978_Tabacman
---------- CHICAGO ----------
Tabacman, Maximiliano. "Métricas de complejidad de grafos para clasificación en múltiples dominios". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/tesis_n5978_Tabacman
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5978_Tabacman.pdf
