AlgoritmosMtodos basados en grafos

Carlos Aguirre MaesoCarlos.Aguirre@uam.es

Escuela Politcnica SuperiorUniversidad Autnoma de Madrid

Introduccin.La teora de grafos ha sido utilizada recientemente

para: Clasificacin automtica de secuencias de protenas. Deteccin de jerarquas de protenas. Anlisis de redes genticas. Reconstruccin de redes genticas grandes obtenidas mediante modificacin de genes.

Teora de grafos.Un grafo G es un par de conjuntos (V,E)

V={v1,v2,....vn} es el conjunto de vrtices E={(vi,vj),(vi,vj)......} es un conjunto de pares no ordenados de elementos de V. E se denomina conjunto de ramas del grafo El numero de nodos se denomina orden del grafo. El nmero de ramas se denomina tamao del grafo.

v1v2v3

v4v5

v6v7

v8V={v1,v2,v3,v4,v5,v6,v7,v8}E={(v1,v2),(v1,v3),(v2,v4),(v3,v5),(v4,v6),(v5,v7),(v6,v8),(v7,v8),(v2,v5),(v4,v5),(v6,v7)}

Ejemplo de grafo (Orden 8 y tamao 11).

Un bucle es una rama que empieza y termina en el mismo nodo (vi,vi).

Cuando dos ramas conectan el mismo par de vrtices se denominan paralelas.

Un grafo con bucles se denomina pseudografo. Un grafo con ramas paralelas pero sin bucles se denomina multigrafo.

Un grafo sin bucles ni ramas paralelas se denomina grafo simple.

Bucles y ramas paralelas.

Bucles y ramas paralelas.

v1 v2v3

v4v5

v6v7 v8Bucle

Ramas paralelas

Se puede considerar que los enlaces entre nodos son dirigidos (vi,vj) = (vj,vi).

Los grafos dirigidos se denominan tambin digrafos.

v1 v2v3

v4v5

v6v7 v8

Grafos dirigidos.

A cada rama del grafo se le puede asociar un nmero.

El nmero asociado a cada rama puede indicar entre otras cosas una distancia, una capacidad, un valor temporal, etc

v1 v2v3

v4v5

v6v7 v8

2 1 5 7-16104 12 9 2

Grafos ponderados.

Los grafos dirigidos y ponderados poseen ramas dirigidas a las que se asocia un nmero.

v1 v2v3

v4v5

v6v7 v8

2 1 5 7-16104 12 9 2

Grafos dirigidos y ponderados.

Dos nodos de un grafo son vecinos o adyacentes si existe una rama que los conecta.

El grado de un nodo es el nmero vecinos que tiene dicho nodo.

En los grafos dirigidos se calcula el grado de entrada y el grado de salida.

En los grafos ponderados, el grado se puede promediar por el nmero asociado a las ramas.

Un grafo se dice que es regular si todos los nodos tienen el mismo grado.

Grado de un nodo.

Grado del nodo V2.

v1 v2v3

v4v5

v6v7 v8

v1 v2v3

v4v5

v6v7 v8

Grado 3

Grado de entrada 2Grado de salida 1

Un grafo G=(V,E) es un sugrafo de un grafo G=(V,E) si V es un subconjunto de V y E es un subconjunto de E..

v1 v2v3

v4v5

v6v7 v8

v2v3 v5

v6v7 v8

GG

Subgrafos.

Un subgrafo G=(V,E) de un grafo G=(V,E) se dice que es abarcador si V=V.

v1 v2v3

v4v5

v6v7 v8

v2v3 v5

v6v7 v8

GG

v1 v4Subgrafos.

Un paseo de un nodo u a un nodo v es una secuencia de vrtices {v0,v1,....vk} con v1=u vk=v y (vi-1,vi) rama del grafo.

El nmero de ramas del paseo es su longitud. Un paseo en el cual no se repiten ramas se denomina rastro.

Un paseo en el cual todos los vertices {v0,v1,....vk} son distintos se denomina camino. Un camino mnimo entre dos nodos es aquel de menor longitud de entre todos los posibles caminos entre ambos nodos.

Paseos, caminos, circuitos y ciclos.

v1 v2v3

v4v5

v6v7 v8

C={v1,v2,v5,v3,v1,v2,v4,v6,v7,v8} k=9v1 v2

v3v4v5

v6v7 v8

C={v1,v3,v5,v2,v4,v5,v7,v8} k=7

Paseo

Rastro

v1 v2v3

v4v5

v6v7 v8

C={v1,v2,v5,v4,v6,v7,v8} k=6v1 v2

v3v4v5

v6v7 v8

C={v1,v2,v4,v6,v8} k=4

Camino

Camino mnimo

Un paseo cerrado es un paseo {v0,v1,....vk} tal que v0=vk. Un paseo cerrado en el que no se repiten ramas es un circuito.

Un ciclo es un circuito en el que no se repiten vrtices.

Paseos, caminos, circuitos y ciclos.

Paseos, caminos, circuitos y ciclos.

v1 v2v3

v4v5

v6v7 v8

Ciclo

C={v1,v2,v4,v6,v8,v7,v5,v3,v1} k=7

Un grafo es conexo si para cada par de nodos del grafo existe al menos un camino que los une.

v1v3

v2v4 v5

v1v3

v2v4 v5

Grafo conexo Grafo no conexo

Conexidad.

Una componente conexa de un grafo es cada uno de los subgrafos maximales conexos

v1v3

v2v4 v5

Componentes conexas

Conexidad.

Un punto de articulacin es un nodo que desconecta un grafo conexo.

Un corte es un conjunto de ramas que desconecta un grafo conexo,

Si un corte esta compuesto por una nica rama, se denomina puente.

Un corte mnimo de un grafo es el mnimo nmero de ramas que al ser eliminadas desconectan el grafo.

Conexidad.

v3 v4 v5 v7v1 v2 v6

Punto de articulacinCorte

v8PuenteConexidad.

Un grafo sin ciclos (acclico) se denomina bosque. Un arbol es un grafo acclico conexo. Cada componente conexa de un bosque, es un rbol.

Bosques y rboles.

Bosques y rboles.

v2v3 v5

v6v7 v8

G

v1 v4v2v3

v5v6v7

v8G

v1 v4

Un subgrafo abarcador acclico de un grafo G se denomina un bosque abarcador.

Un subgrafo abarcador conexo acclico de un grafo G se denomina un arbol abarcador.

Bosques y rboles.

Bosques y rboles.

v1 v2v3

v4v5

v6v7 v8

G

v1 v2v3

v4v5

v6v7 v8

G

rbol abarcador

Representacin de grafosHay dos formas estndar de representar un grafo en

un ordenador. Matriz de adyacencia. Lista de adyacencia.

v1 v2v3

v4v5

v6v7 v8

0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0

Matriz de adyacencia Lista de adyacencia12345678

2 3 511 452 5 62 3 4 74 7 85 66 7 8

Matriz de Adyacencia

Consume mucha memoria. Fcil de aadir o eliminar

ramas Fcil saber si existe la rama

(a,b). Lento enumerar los vecinos

de un nodo.

Lista de adyacencia

Consumo limitado de memoria.

Costoso aadir o eliminar ramas.

Costoso saber si existe la rama (a,b).

Rpido enumerar los vecinos de un nodo.

Clasificacin de grafos Los grafos se clasifican en funcin de unas determinadas mtricas topolgicas.

Las mtricas mas empleadas son: Tamao |E| y orden |V| Dispersin (|E|/|V|) Distribucin del grado de los nodos Grado medio () Coeficiente de agrupamiento (C) Camino carcteristico (L)

Coeficiente de agrupamiento El coeficiente de agrupamiento (C) es un valor mtrico local que mide el nivel de agrupamiento de los nodos.

Clculo de C Para cada nodo v del grafo se obtiene su vencidario, es decir, el

cojunto de nodos que son vecinos de v, el tamao del vecindario coincide con el grado de v (kv)

Se calcula el coeficiente Nv/(kv(kv-1)) donde Nves el numero de ramas que hay entre los vecinos de v.

El valor anterior se promedia entre todos los nodos del grafo

vCv= 6/(4*3)=1/2

Camino caractersto El camino caracterstico (L) es un valor mtrico global que mide el nivel grado de separacion de los nodos.

Clculo de C Para cada nodo v se calcula la distancia promedio a todos los demas

nodos del grafo, Lv= k=1d(v,vk)/(|V|-1) Se calcula el promedio del valor anterior entre todos los nodos del

grafo L= v=1 Lv/|V| . |V||V|

Algunas topologias. Las topologas mas frecuentes son:

Grafos aleatorios Grafos regulares Mundo pequeo Grafos libres de escala

Grafos aleatorios Fueron estudiados principalmente

por Erdos y Renyi en los aos 50. Cada rama del grafo existe con

una determinada probabilidad p. Erdos y Renyi estudiaron los

valores de las metricastopolgicas para diferentes valores de $p$.

Para la grafos dispersos (p pequea) se puede comprobar que tanto C (aproximadamente 0) como L (aproximadamemteLn(|V|) son pequeos

Grafos Regulares Son los mejor conocidos de forma

analtica Existen expresiones cerradas para

todas las mtricas. Para la grafos dispersos se puede

comprobar que tanto C (aprximadamente 0.75) como L (aproximadamente |V|/) son grandes

Mundo pequeo (Watts y Strogatz 1998) Son grafos que presentan altos

valores de C (aprox .8) y bajos valores de L (aprox ln(|V|).

Se obtienen introduciendo pequeo nmero de atajos en un grafo regular

Representan bien un gran nmero de redes tales como redes sociales.

Libre de escala (Albert y Barabasi 1999) Son grafos que presentan bajos valores de C (aprox 0) y bajos valores de

L (aprox ln(|V|). Se obtienen mediante crecimiento de la red y enlace preferencial Cuando la distribucin de los nodos se dibuja en escala log-log aparece

una lnea recta. Representan bien un gran nmero de redes tales como internet o redes

de reacciones qumicas.

0.0043.89Aleatorio 0.01863.409Libre de escala 0.62614.2Mundo Pequeo 0.643125.438Anillo RegularMetricas

|V|=2000 k=8

Algortmos sobre grafos El algoritmo de bsqueda en anchura permite calcular un camino mnimo entre dos nodos de un grafo.

Dijkstra es una versin del algoritmo anterior para grafos ponderados.

Ambos algoritmos funcionan tanto en grafos dirigidos como no dirigidos.

Los algoritmos nos permiten calcular las mtricas sobre el grafo.

BusquedaAnchura(V,E,s)Para cada vertice u en V-svisitado[u]=FALSE, d[u]=infinito,p[u]=NIL

visitado[s]=TRUE,d[s]=0,p[s]=NILEncueue(Q,s)While(NoVacia(Q))u=Head(Q)para cada v en adj(u)if visitado[v]=FALSEd[v]=d[u]+1,p[v]=uEnqueue(Q,v)visitado[v]=TRUE

Dequeue(Q)

2

3

4

51

0 i i iT F F F FN N N N Ndvisitadop 1Q iU=11 2 3 4 5

12345

2 3 421 351 2 53 4

2

3

4

51

0 1 i iT T F F FN 1 N N Ndvisitadop 1 2Q iU=11 2 3 4 5

12345

2 3 421 351 2 53 4

2

3

4

51

0 1 i iT T T F FN 1 1 N Ndvisitadop 1 2Q 13U=11 2 3 4 5

12345

2 3 421 351 2 53 4

1

2

3

4

51

0 1 2 iT T T T FN 1 1 2 Ndvisitadop 2 3Q 1U=21 2 3 4 5

12345

2 3 421 351 2 53 4

1

2

3

4

51

0 1 2 iT T T T FN 1 1 2 Ndvisitadop 2 3Q 14U=21 2 3 4 5

12345

2 3 421 351 2 53 4

1

2

3

4

51

0 1 2 2T T T T TN 1 1 2 3dvisitadop 3 4Q 15U=21 2 3 4 5

12345

2 3 421 351 2 53 4

2

3

4

51

0 1 2 2T T T T TN 1 1 2 3dvisitadop 4 5Q 1U=31 2 3 4 5

12345

2 3 421 351 2 53 4

2

3

4

51

0 1 2 2T T T T TN 1 1 2 3dvisitadopQ 1U=31 2 3 4 5

12345

2 3 421 351 2 53 4

CLUSTERING-COEFFICIENT(w)1 n = rows[w]2 ci = 03 for i = 1 to n4 do neighbor[i]= 05 for i = 1 to n6 do k = 07 for j = 1 to n8 do if W[i][j] = 19 then neighbor[k]= j10 k = k + 11112 realedges = 013 for p = 0 to k 214 do for q = p + 1 to k 115 do if w[neighbor[p]][neighbor[q]] = 116 then realedges = realedges + 1171819 totaledges = k(k 1)/220 ci = ci + realedges/totaledges21 ci = ci/n22 return ci

DEGREE-DISTRIBUTION(w)1 n = rows[w]2 for i = 1 to n3 do dist[i] = 04 for i = 1 to n5 do numedges = 06 for j = 1 to n7 do if w[i][j] = 1 and i != j8 then numedges numedges + 1910 distnumedges = distnumedges + 111 for i = 1 to n12 do disti = disti/n13 return dist

El algoritmo de Bsqueda en profundidad permite calcular puntos de articulacin de un grafo.

El algoritmo de Ford-Fulkerson permite calcular cortes mnimos.

Aplicaciones Las tcnicas basadas en grafos se utilizan para el anlisis o clasificacin de cadenas de datos

La tcnica suele consistir en la construccin de un grafo donde los nodos son cada uno de los datos obtenidos y las ramas posibles relaciones entre los datos y la aplicacin de algn algoritmo conocido sobre este grafo.

Click Click (Sharan & Shamir) es un algoritmo de clusteringaplicado al anlisis de expresiones genticas (gene expressions).

Click tambin ha sido utilizado para clustering de conjuntos de datos de protenas (ProtoMap).

El problema de clustering consiste en partir un conjunto V en k conjuntos disjuntos V1,V2,....Vk tal que la unin de todos ellos es V.

Para comprobar la calidad del clustering se definen dos medidas Separacin entre clusters Homogeneidad de cada cluster

Click(G)si V(G)={u}

Aade {u} al conjunto de vertices aisladossi G es un cluster

Aadir G a la lista de clustersen otro caso

H, H = CorteMnimo(G)Click(H)Click(H)

Click se ha utilizado para clustering de expresiones genticas donde cada nodo es una expresin.

Dos nodos se conectan si un coeficiente de similitud entre ambas expresiones genticas es mayor que un cierto umbral.

Resultados de click cuando se aplica al conjunto de datosde la respuesta de los fibroblastos humanos al suero

ProtoMap ProtoMap es un proyecto dedicado a la clasificacin de secuencias de protenas y jerarquizacin de familias de protenas.

Cada vrtice es una secuencia y el peso de cada rama es un coeficiente de similitud entre las protenas.

Los clusters se obtienen buscando grupos de nodos altamente conectados entre s.

Los autores aplicaron el mtodo a la base de datos SWISS-PROT.

Los resultados se pueden consultar en http://www.protomap.cs.huji.ac.il

Redes de interaccin Tong et al. analizan redes de interaccin de protenas. Cada nodo del grafo es una protena. Una rama significa una interaccin entre ambas protenas.

Un k-core de un grafo G es un subgrafo G tal que el grado de cada nodo de G es al menos k.

Este algoritmo produce una jerarqua de subgrafosbasandose en el k de los k-cores obtenidos para cada posible k.

Dominio SH3 (|V|=206 |E|=394)

6-Core del dominio SH3

Cliff Cliff (Xing & Karp) ha sido utilizado para clustering de datos con un nmero alto de dimensiones.

De nuevo cada nodo es una expresin gentica (muy larga) y las ramas un coeficiente de similitud entre nodos.

Cliff usa cortes mnimos y tcnicas bayesianas para definir los clusters.