Métricas de complejidad de grafos para clasificación en múltiples dominios
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Tesis doctoral publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
2016
|
| Materias: | |
| Acceso en línea: | https://hdl.handle.net/20.500.12110/tesis_n5978_Tabacman https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5978_Tabacman_oai |
| Aporte de: |
| Sumario: | 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. |
|---|