pgr_betweennessCentrality

pgr_betweennessCentrality - Calcula la centralidad intermedia relativa mediante el algoritmo de Brandes

Adentro: Boost Graph

Disponibilidad

• Versión 3.7.0

  • Nueva función experimental:

    • pgr_betweennessCentrality

Descripción

El algoritmo Brandes aprovecha los grafos dispersos para evaluar la puntuación de centralidad intermedia de todos los vértices.

La centralidad de interrelación mide hasta qué punto un vértice se encuentra en las rutas más cortas entre todos los demás pares de vértices. Los vértices con una alta centralidad entre pares pueden tener una influencia considerable en una red gracias a su control sobre los caminos más cortos que pasan entre ellos.

La eliminación de estos vértices afectará a la red al perturbarla, ya que la mayoría de los caminos más cortos entre vértices pasan por ellos.

Esta implementación funciona tanto para grafos dirigidos como no dirigidos.

• Tiempo de ejecución: \(\Theta(VE)\)

• Espacio de ejecución: \(\Theta(VE)\)

• Lanza cuando no hay aristas en el grafo

Firmas

Resumen

pgr_betweennessCentrality(SQL de aristas, [directed])

Regresa el conjunto de (vid, centrality)

Ejemplo:

Para un grafo dirigido con aristas \(\{1, 2, 3, 4\}\).

SELECT * FROM pgr_betweennessCentrality(
'SELECT id, source, target, cost, reverse_cost
FROM edges where id < 5'
) ORDER BY vid;
 vid | centrality
-----+------------
   5 |          0
   6 |        0.5
   7 |          0
  10 |       0.25
  15 |          0
(5 rows)

Explicación

• La centralidad intermedia está entre paréntesis.

• Los vértices de las hojas tienen una centralidad intermedia \(0\).

• La centralidad de entrecruzamiento del vértice \(6\) es mayor que la del vértice \(10\).

  • Al eliminar el vértice \(6\) se crearían tres componentes.

  • Al eliminar el vértice \(10\) se crearán dos componentes del grafo.

Parámetros

Parámetro	Tipo	x Defecto	Descripción
SQL de aristas	TEXT		SQL de aristas descritas más adelante.

Parámetros opcionales

Columna	Tipo	x Defecto	Descripción
directed	BOOLEAN	true	Cuando true el gráfo se considera Dirigido Cuando false el gráfo se considera No Dirigido.

Consultas Internas

SQL aristas

Columna	Tipo	x Defecto	Descripción
source	ENTEROS		Identificador del primer vértice de la arista.
target	ENTEROS		Identificador del segundo vértice de la arista.
cost	FLOTANTES		Peso de la arista (source, target)
reverse_cost	FLOTANTES	-1	Peso de la arista (target, source) Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

Columna	Tipo	Descripción
vid	BIGINT	Identificador del vértice.
centrality	FLOAT	Puntuación relativa de centralidad entre vértices (estará en el rango [0,1])

Ver también

• Boost: Centralidad de intermediación

• Las consultas utilizan la red Datos Muestra.

Índices y tablas

• Índice

• Página de Búsqueda