Teoria general de grafos

Conceptos de teoría de grafos

Lazos orientados vs no orientados
• Relaciones no orientadas
– Asistir a una reunión con – Se comunica diariamente con

• Relaciones orientadas
– Deja dinero a

• Lazo orientados lógicamente vs empíricamente
– En la práctica, incluso las relaciones recíprocas o no orientadas pueden ser no simétricas a causa del error de medición

Bob Biff

BonnieBetty Betsy

Intensidad de una relación
• Podemos asignar valores a lazos representando atributos cuantitativosJane
– – – – – – Intensidad de la relación 6 Capacidad informativa del lazo Volúmenes de flujo o tráfico a través del lazo Bob Distancias entre nodos Probabilidades de pasar información 3 Frecuencia de interacción
1

8

Betsy

Matrices adyacentes
Amistad Jim Jim Jill 1 Jen 0Joe 1 Jill Jen Joe 1 0 1 - 1 0 1 1 0 1 -

Jill Jen
1 9 3

Jim

Proximidad Jim Jill Jen Joe Jim - 3 9 2 Jill 3 - 1 15 Jen 9 1 3 Joe 2 15 3 -

3

15 2

Joe

Densidad
• Proporcion de pares vinculados
– Numero de lazos divido por el numero de pares
• No. de pares = n(n-1)/2 • = 7(6)/2 = 21

T S

– 11/21

Longitud & Distancia
• La longitud de un camino es el número de enlaces• La distancia entre dos nodos es la longitud del camino más corto (geodésico)
3 10 12 11 8 9 2 7

1

6

4

5

Matriz de Distancias Geodésicas
a a b c d e f g 0 1 2 3 2 3 4 b 1 0 1 2 1 2 3 c 2 1 0 1 1 2 3 d 3 2 1 0 2 3 4 e 2 1 1 2 0 1 2 f 3 2 2 3 1 0 1 g 4 3 3 4 2 1 0

Componentes
• Conjunto máximo de series de nodos en el cual cada nodo puede alcanzar cualquier otro a través dealgún camino (sin importar cuán largo sea) • Una red conectado sólo tiene un componente
Las relaciones definen diferentes redes. Los componentes no.

Una red con 4 componentes
A quién te diriges de forma que puedas decir ‘I ran it by ____, and she says ...’

Adquisición reciente Adquisición antigua Compañía original

Datos tomados de Cross, Borgatti y Parker 2001.

Caminosindependientes
• Un conjunto de caminos es nodoindependiente si no comparten nodos (excepto al inicio y al final)
– Son línea-independiente si no comparten líneas
T S

• 2 caminos nodo-independientes de S a T • 3 caminos línea-independientes de S a T

Puntos de corte
• Nodos que si se quitan desconectan la red

Bob Biff Bill

Bonnie

Betty Betsy

e b

Puente
q

s

• Un lazo que si sequita g desconecta la red
d p f h c i j

m

a

l

k n r o

Puente local de grado k
• Un lazo que conecta nodos que de otro modo estarían al menos k pasos separados
A B

Transitividad de Granovetter
A B

C D

Medidas de Centralidad

Una Red ...

Cuatro Aspectos de la Centralidad
Eigenvector
Grado nodal

Cercanía

Grado de intermediación

Datos cortesía de DavidKrackhardt

Grado nodal / Volumen de lazos
• Número de lazos relacionados con un nodo dado – Sumas de filas de una matriz de adyacencia simétrica • Índice de exposición a lo que está circulando a través de la red – Red de rumores: el actor central tendrá más probabilidades de escuchar un dado rumor • Puede ser interpretado como la oportunidad de influir o ser influido directamente • Prediceuna variedad de resultados como la resistencia a virus a el poder, el liderazgo, la satisfacción en el trabajo o el conocimiento.

Grado de Cercanía
a b 1 0 1 2 1 2 3 c 2 1 0 1 1 2 3 d 3 2 1 0 2 3 4 e 2 1 1 2 0 1 2 f 3 2 2 3 1 0 1 g 4 3 3 4 2 1 0 C 15 10 10 15 9 12 17

• Suma de las distancias al resto de nodos
– Se calcula como las sumas de fila de una matriz simétrica de distanciasgeodésicas – Es una medida inversa de la centralidad

a b c d e f g

0 1 2 3 2 3 4

• Índice del tiempo de llegada esperado a un nodo dado de lo que está circulando a través de la red
– Red de rumores: el jugador central se entera primero

Intermediación
• Con qué frecuencia un nodo aparece en el camino más corto que conecta otros dos nodos
– Se calcula de la siguiente forma:

gikj bk = ∑...