Modelos de Conectividad
Métricas sobre grafos
Carlos Aguirre Maeso
Escuela Politécnica superior
Métricas.
●
●
●
Muchas propiedades de los grafos van a depender
del valor de ciertas métricas o de funciones que
combinan los valores de diversas metricas.
En general las metricas seran útiles para clasificar
grafos.
A cada grafo se le asignara un tipo (o varios) de
res en función de los valores que tomen sus
metricas
Tamaño y orden
●
●
●
Se define orden |V| como el número de nodos que
tiene el grafo
Se define tamaño |E| como el número de ramas del
grafo
Un grafo se define disperso si |E| << |V|(|V|-1)/2
Tamaño y orden
●
●
Se define el coeficiente de dispersión de un grafo
G como
2*|E|/|V|(|V|-1)
Grado de los nodos.
●
●
●
●
Se define el grado de un nodo <k> como el
número de vecinos que tiene el nodo.
Si el grafo es dirigido se distingue entre el grado
de salida <k>out y el grado de entrada <k>in
Se define el grado medio del grafo como la media
del grado de los nodos.
El grado medio tambien se puede calcular 2|E|/|V|
Grado de los nodos.
●
●
Un grafo cuyos nodos tengan todos el mismo
grado se denomina regular.
Un grafo regular con k= |V|-1 se denomina
completo.
Distribución de grado.
●
Se puede representar la distribucion de los grados
de los nodos del grafo.
–
En el eje x se representan los posibles grados
–
En el eje y se representan cuantos nodos tienen ese
grado dividido entre el numero total del nodos del
grafo
Distribución de grado.
●
●
Un grafo regular corresponde a una distribución a
una distribución de masa concentrada en un punto.
Un grafo aleatorio tiene una distribución
correspondiente a una poisson.
Distribución de grado.
●
●
●
Un caso especial es la distribución libre de escala.
Corresponde a una recta cuando se pinta en escala
logaritmica-logaritmica.
Los grafos con esta distribución de grados se
denominan libres de escala.
Distribución de grado.
Libre de escala
Poisson
Conexidad.
●
●
●
Una componente conexa de un grafo es un
conjunto maximal de nodos tal que existe al menos
un camino que conecta ambos nodos.
Un grafo con una componente conexa se denomina
conexo.
La componente conexa de mayor tamaño se
denomina la componente gigante B del grafo.
Conexidad.
●
●
●
En un grafo conexo |B| = |V|.
En grafos no conexos se puede considerar el
tamaño de la componente gigante.
Tambien se puede considerar la distribución del
tamaño de las componentes conexas.
Caminos
●
Se llama distancia entre dos nodos a la longitud
del camino mas corto que los une.
●
Se llama diámetro del grafo a la mayor distancia
entre dos nodos del grafo.
Caminos
●
Se denomina camino característico de un grafo al
valor medio de la distancia entre todas las parejas
de nodos del grafo
●
Se llama diámetro del grafo a la mayor distancia
entre dos nodos del grafo.
●
El diámetro es una cota superior para el camino
característico.
Caminos
●
El camino carácterístico se suele calcular en dos
pasos.
–
a) Para cada nodo i se calcula la distancia media a los
demas nodos del grafo.
–
b) Se calcula el valor medio de los valores anteriores
de cada nodo.
Indice de clusterizacion.
●
El indice de clusterización es el valor medio del
indice de clusterización de cada nodo
●
Donde Ei es el numero de conexiones que existen
entre los vecinos del nodo
Subgrafos
●
La probabilidad crítica pc(N) de encontrar algunos
subgrafos es:
Bi-conexidad.
●
●
Una componente bi-conexa es un conjunto
maximal de nodos tales que para cualquier par de
nodos existen al menos dos caminos que los unen.
El número de componentes biconexas indica la
redundancia en caminos del grafo.
Descargar

Tema 4