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  |