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 |
| Filiación: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Computación
|
| Publicación: | 2016-09-02 |
| Defensa: | 2016-05-02 |
| Grado Obtenído: | Doctoral |
| Título Obtenído: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Krasnogor, Natalio; Loiseau, Irene |
| Consejero: | 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: | text; 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 |
| Identificador: | 87011E1 |
| Ubicación: | Dep.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. (2016). 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 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.
Abstract:
The objective of this thesis is to research and offer insights into the possibilities of classifying complex networks based on their large scale topological features. We are interested in studying the properties of networks from different domains, and find common characteristics that may be shared by the networks in each of them. With them, we aim to develop algorithms and techniques that take advantage of the shared features, to automate the classification of networks to their respective domains. This information would also be useful in determining if an artificial network shares the expected characteristics of its intended domain. We research and review a large number of complexity measures from the literature. From them, we choose 13 that are then derived to reach a total of 43 measures. We created a network data set from different sources, with 240 networks distributed across 11 domains. Exhaustive analysis is applied to the measurements obtained from them, to analyze their correlation and statistical distribution, and attempt to predict the classification possibilities an automated algorithm might have of correctly discriminating between the domains. We attempt to determine if the measures computed can be used as discriminators between the domains under study. To that end, we present 3 different 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 classification task of distinguishing the domain to which each network belongs. Furthermore, to understand their potential ability to correctly classify network domains, we use the CiGRAM graph generator to build a set of 160 artificial networks distributed across 8 sample domains. We analyze their statistical distribution, and run the experiments proposed, where some of the algorithms presented achieve up to 80% accuracy. Moreover, we observe the ease of interpretation in the results offered by the BioHEL system, since its output is composed of human readable rules that explain how to classify the networks based on their computed measures. Finally, we apply the proposed experiments using the classification techniques reviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtained for the artificial networks, and continue with additional experimental scenarios to study possible improvements, such as outlier elimination, and manual partitioning of the training and testing sets. After running them, we observe that despite the average results are still below those obtained for artificial networks, a subset of the experiments present the previously attained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into different domains just by considering the measurements obtained from a speciFinally, we apply the proposed experiments using the classification techniques reviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtained for the artificial networks, and continue with additional experimental scenarios to study possible improvements, such as outlier elimination, and manual partitioning of the training and testing sets. After running them, we observe that despite the average results are still below those obtained for artificial networks, a subset of the experiments present the previously attained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into different domains just by considering the measurements obtained from a specific set of complexity measures, and we also offer a number of possible improvements in future related research.
Citación:
---------- APA ----------
Tabacman, Maximiliano. (2016). 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
---------- 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, 2016. http://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
