Algoritmo de Brandes

Algoritmo para encontrar nodos importantes en un gráfico

En teoría de redes , el algoritmo de Brandes es un algoritmo para calcular la centralidad de intermediación de los vértices de un grafo . El algoritmo fue publicado por primera vez en 2001 por Ulrik Brandes . ^[1] La centralidad de intermediación, junto con otras medidas de centralidad , es una medida importante en muchas redes del mundo real, como las redes sociales y las redes de computadoras . ^{[2] [3] [4]}

Definiciones

Existen varias métricas para la centralidad de un nodo, una de ellas es la centralidad de intermediación . ^[5] Para un nodo en un gráfico conectado , la centralidad de intermediación se define como: ^{[6] [7]} ${\displaystyle v}$

${\displaystyle C_{B}(v)=\sum _{s\in V}\sum _{t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

donde es el número total de caminos más cortos de nodo a nodo y es el número de estos caminos que pasan por . Para un gráfico no ponderado, se considera que la longitud de un camino es el número de aristas que contiene. ${\displaystyle \sigma _{st}}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle \sigma _{st}(v)}$ ${\displaystyle v}$

Por convención, siempre que , ya que el único camino es el camino vacío. Además, si es o , ya que los caminos más cortos no pasan por sus puntos finales. ${\displaystyle \sigma _{st}=1}$ ${\displaystyle s=t}$ ${\displaystyle \sigma _{st}(v)=0}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle t}$

La cantidad

${\displaystyle \delta _{st}(v)={\frac {\sigma _{st}(v)}{\sigma _{st}}}}$

se conoce como la dependencia de pares de , y representa la proporción de los caminos más cortos que pasan por . La centralidad de intermediación es simplemente la suma de las dependencias de pares sobre todos los pares. Además de la dependencia de pares, también es útil definir la dependencia (única) de , con respecto a un vértice en particular : ${\displaystyle st}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle s}$

${\displaystyle \delta _{s}(v)=\sum _{t\in V}\delta _{st}(v)}$,

con lo cual podemos obtener la formulación concisa

${\displaystyle C_{B}(v)=\sum _{s\in V}\delta _{s}(v)}$.

Algoritmo

El algoritmo de Brandes calcula la centralidad de intermediación de todos los nodos de un grafo. Para cada vértice , hay dos etapas. ${\displaystyle s}$

Ruta más corta de una sola fuente

El número de caminos más cortos entre y cada vértice se calcula mediante una búsqueda en amplitud . La búsqueda en amplitud comienza en y se registra la distancia más corta de cada vértice desde , dividiendo el gráfico en capas discretas. Además, cada vértice lleva un registro del conjunto de vértices que en la capa anterior apuntan a él, . Descrito en la notación de constructor de conjuntos , se puede escribir como: ${\displaystyle \sigma _{sv}}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle d(v)}$ ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle p(v)}$

${\displaystyle p(v)=\{u\in V\mid (u,v)\in E\land d(u)+1=d(v)\}}$.

Esto se presta a una fórmula iterativa simple para : ${\displaystyle \sigma _{sv}}$

${\displaystyle \sigma _{sv}=\sum _{u\in p(v)}\sigma _{su}}$,

que esencialmente establece que, si está en la profundidad , entonces cualquier camino más corto en la profundidad extendido por un solo borde a se convierte en un camino más corto a . ${\displaystyle v}$ ${\displaystyle d(v)}$ ${\displaystyle d(v)-1}$ ${\displaystyle v}$ ${\displaystyle v}$

Retropropagación

Brandes demostró la siguiente fórmula recursiva para las dependencias de vértices: ^[1]

${\displaystyle \delta _{s}(u)=\sum _{v\mid u\in p(v)}{\frac {\sigma _{su}}{\sigma _{sv}}}\cdot (1+\delta _{s}(v))}$,

donde la suma se toma sobre todos los vértices que están a una arista más alejada que . Este lema elimina la necesidad de sumar explícitamente todas las dependencias de pares. Usando esta fórmula, la dependencia única de en un vértice en profundidad está determinada por la capa en profundidad . Además, el orden de suma es irrelevante, lo que permite un enfoque de abajo hacia arriba comenzando en la capa más profunda. ${\displaystyle v}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle d(u)}$ ${\displaystyle d(u)+1}$

Resulta que las dependencias de de todos los demás vértices se pueden calcular en el tiempo. Durante la búsqueda en amplitud, el orden en el que se visitan los vértices se registra en una estructura de datos de pila . Luego, el paso de retropropagación extrae repetidamente los vértices, que se ordenan naturalmente por su distancia desde , en orden descendente. ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle O(|E|)}$ ${\displaystyle s}$

Para cada nodo emergente , iteramos sobre sus predecesores : se suma la contribución de hacia , es decir, ${\displaystyle v}$ ${\displaystyle u\in p(v)}$ ${\displaystyle v}$ ${\displaystyle \delta _{s}(u)}$

${\displaystyle {\frac {\sigma _{su}}{\sigma _{sv}}}\cdot (1+\delta _{s}(v))}$.

Fundamentalmente, cada capa propaga sus dependencias por completo, antes de pasar a la capa con menor profundidad, debido a la naturaleza de la búsqueda en amplitud. Una vez que la propagación llega de nuevo a , cada vértice ahora contiene . Estos simplemente se pueden agregar a , ya que ${\displaystyle s}$ ${\displaystyle v}$ ${\displaystyle \delta _{s}(v)}$ ${\displaystyle C_{B}(v)}$

${\displaystyle C_{B}(v)=\sum _{s\in V}\delta _{s}(v)}$.

Después de iteraciones de ruta más corta de fuente única y retropropagación , cada una contiene la centralidad de intermediación para . ${\displaystyle |V|}$ ${\displaystyle C_{B}(v)}$ ${\displaystyle v}$

Pseudocódigo

El siguiente pseudocódigo ilustra el algoritmo de Brandes en un gráfico dirigido no ponderado. ^[8]

El algoritmo Brandes( Graph ) es  para cada  u  en  Graph.Los vértices  hacen CB[ u ] ← 0 para cada  s  en  Graph.Vertices  , haga  para cada  v  en  Graph.Vertices  , haga δ[ v ] ← 0 // Dependencia única de s en v prev[ v ] ← lista vacía // Predecesores inmediatos de v durante BFS σ[ v ] ← 0 // Número de caminos más cortos de s a v (s implícito) dist[ v ] ← null // No se conocen rutas inicialmente, σ[ s ] ← 1 // excepto el vértice inicial distribución[ s ] ← 0 Q ← cola que contiene solo s // Búsqueda en amplitud S ← pila vacía // Registra el orden en el que se visitan los vértices // Rutas más cortas de una sola fuente mientras  Q no esté vacío , haga  u ← Q .dequeue() S .push( u ) para cada  v  en  Graph.Neighbours [ u ] hacer  si dist[ v ] = null  entonces dist[ v ] ← dist[ u ] + 1 Q .enqueue( v ) si dist[ v ] = dist[ u ] + 1 entonces σ[ v ] ← σ[ v ] + σ[ u ] prev[ v ].append( u ) // Propagación hacia atrás de dependencias mientras  S no esté vacío, haga  v ← S .pop() para cada  u  en prev[ v ] haga δ[ u ] ← δ[ u ] + σ[ u ] / σ[ v ] * (1 + δ[ v ]) si  u ≠ s  entonces CB[ v ] ← CB[ v ] + δ[ v ] // Reducido a la mitad para grafos no dirigidos devolver CB

Duración del programa

El tiempo de ejecución del algoritmo se expresa en términos del número de vértices y el número de aristas . ${\displaystyle |V|}$ ${\displaystyle |E|}$

Para cada vértice , realizamos una búsqueda en amplitud, que lleva tiempo. Como el gráfico está conectado, el componente subsume el término, ya que el número de aristas es al menos . ${\displaystyle s}$ ${\displaystyle O(|V|+|E|)}$ ${\displaystyle |E|}$ ${\displaystyle |V|}$ ${\displaystyle |V|-1}$

En la etapa de retropropagación, cada vértice se extrae de la pila y se itera sobre sus predecesores. Sin embargo, dado que cada entrada predecesora corresponde a una arista en el gráfico, esta etapa también está limitada por . ${\displaystyle O(|E|)}$

Por lo tanto, el tiempo de ejecución total del algoritmo es , una mejora en los límites de tiempo alcanzados por algoritmos anteriores. ^[1] Además, el algoritmo de Brandes mejora la complejidad espacial de los algoritmos ingenuos, que normalmente requieren espacio. El algoritmo de Brandes solo almacena como máximo predecesores, junto con datos para cada vértice, lo que hace que su complejidad espacial adicional sea ${\displaystyle O(|V||E|)}$ ${\displaystyle O(|V|^{3})}$ ${\displaystyle O(|V|^{2})}$ ${\displaystyle |E|}$ ${\displaystyle O(|V|+|E|)}$

Variantes

El algoritmo se puede generalizar a grafos ponderados utilizando el algoritmo de Dijkstra en lugar de la búsqueda en amplitud. Cuando se opera en grafos no dirigidos, la centralidad de intermediación se puede dividir por 2, para evitar el doble conteo de la contraparte invertida de cada camino. También existen variantes para calcular diferentes medidas de centralidad, incluyendo la intermediación con caminos en longitud máxima , la intermediación de aristas , la intermediación de carga y la intermediación de tensión . ^[8] ${\displaystyle k}$

Referencias

1. Brandes, Ulrik (junio de 2001). "Un algoritmo más rápido para la centralidad de intermediación". The Journal of Mathematical Sociology . 25 (2): 163–177. doi :10.1080/0022250X.2001.9990249. ISSN  0022-250X . Consultado el 10 de mayo de 2024 .
2. Wasserman, Stanley; Faust, Katherine (1994). Análisis de redes sociales: métodos y aplicaciones. Análisis estructural en las ciencias sociales. Cambridge: Cambridge University Press. doi :10.1017/cbo9780511815478. ISBN 978-0-521-38707-1.
3. Borgatti, Stephen P.; Everett, Martin G. (1 de octubre de 2006). "Una perspectiva grafo-teórica sobre la centralidad". Redes sociales . 28 (4): 466–484. doi :10.1016/j.socnet.2005.11.005. ISSN  0378-8733 . Consultado el 10 de mayo de 2024 .
4. Kleinberg, Jon M. (1 de septiembre de 1999). "Fuentes autorizadas en un entorno hipervinculado". Revista de la ACM . 46 (5): 604–632. doi :10.1145/324133.324140. ISSN  0004-5411 . Consultado el 10 de mayo de 2024 .
5. Sabidussi, Gert (1 de diciembre de 1966). «El índice de centralidad de un grafo». Psychometrika . 31 (4): 581–603. doi :10.1007/BF02289527. ISSN  1860-0980. PMID  5232444 . Consultado el 10 de mayo de 2024 .
6. Freeman, Linton C. (1977). "Un conjunto de medidas de centralidad basadas en la intermediación". Sociometría . 40 (1): 35–41. doi :10.2307/3033543. ISSN  0038-0431. JSTOR  3033543.
7. Anthonisse, JM (1 de enero de 1971). "La prisa en un grafo dirigido". Stichting Mathematisch Centrum .
8. Brandes, Ulrik (mayo de 2008). "Sobre variantes de la centralidad de intermediación de la ruta más corta y su cálculo genérico". Redes sociales . 30 (2): 136–145. doi :10.1016/j.socnet.2007.11.001. ISSN  0378-8733 . Consultado el 10 de mayo de 2024 .