Agenda Vista general de las Aplicaciones Definiciones y Representación Árbol recubridor mínimo (Minimum Spanning Tree): Alg. de Prim Ruta más corta (con un solo origen): Dijkstra's Algorithm Todas los pares de Rutas más cortas Clausura transitiva (Transitive Closure) Componentes conectados
Redes de transporte, rutas más cortas: 15 segs (“naïve”) ? 10 microsegs Ruteo en transporte terrestre H. Bast et al., “Fast Routing in Road Networks with Transit Nodes”, Science 27, 2007.
La web se puede representar como gráfico dirigido Web search , web crawl: traversal (recorrido de grafo) Análisis de links, ranking: Page rank, HITS Clasificación y clustering (agrupamiento) de documentos Las topologías de Internet (redes de routers) are se modelan naturalmente como grafos Internet y la WWW
Reordernar cols/filas en matr.dispersas Para reducir/concentrar el “lleno” Particionar, eigen-vectores Diagonal pesada para menos pivoting Estructuras de datos para explotar mejor el patrón disperso Optimización Matroides, colorear grafos, spanning trees Preconditionadores Factorización incompleta Particionar dominios Grafos en multigrid Independent sets, matchings, etc. Teoría de soprte Spanning trees & graph embedding Cómputo científico B. Hendrickson, “Graphs and HPC: Lessons for Future Architectures”, http://www.er.doe.gov/ascr/ascac/Meetings/Oct08/Hendrickson%20ASCAC.pdf Image source: Yifan Hu, “A gallery of large graphs” Image source: Tim Davis, UF Sparse Matrix Collection.
Abstraer algo como grafo es útil parta analizar data con relaciones/estructura complicada. Fuentes de data: simulaciones de peta-escala, sensores en experimentos, Internet, redes de sensores Desafios: enorme tamaño de data, heterogeneidad, incertidumbre, calidad de la data Análisis de grandes cantidades de data Astrofísica: datasets masivos, variaciones en el tiempo Bioinformática: calidad de data, heterogeneidad Redes sociales: anáisis, incertidumbre Image sources: (1) http://physics.nmt.edu/images/astro/hst_starfield.jpg (2,3) www.visualComplexity.com
Estudio de la interacción entre componentes de un sistema biológico Se usan mucho los grafos: Predecir nuevas interacciones: modelado Anotación funcional de nuevas proteínas: matching, clustering Identificar rutas metabólicas: rutas, clustering Identificar nuevos complejos de proteínas: clustering, centralidad Análisis de data y Alg. de grafos en Biología Sistémica Image Source: Giot et al., “A Protein Interaction Map of Drosophila melanogaster”, Science 302, 1722-1736, 2003.
Image Source: Nexus (Facebook application) Grafos y las redes sociales Identificar comunidades: clustering Publicidad personalizada: centralidad Difusión de la información: modelado
[Krebs ’04] Análisis de redes terroristas usando información pública (luego de Torres Gemelas). Determinar líderes de los patrones de interacción: centralidad
Vista globla de las entidades arroja más luces Detectar actividades anormales isomorfismo de subgrafos exacto o aproximado Image Source: http://www.orgnet.com/hijackers.html Análisis de redes para Inteligencia y Vigilancia Image Source: T. Coffman, S. Greenblatt, S. Marcus, Graph-based technologies for intelligence analysis, CACM, 47 (3, March 2004): pp 45-47
| Página siguiente |