Conector Wiener

En teoría de redes , el conector de Wiener es un método para maximizar la eficiencia en la conexión de vértices de consulta específicos en una red. Dado un grafo conectado y no dirigido, y un conjunto de vértices de consulta, el conector de Wiener mínimo es un subgrafo inducido que conecta los vértices de consulta y minimiza la suma de las distancias de los caminos más cortos entre todos los pares de vértices del subgrafo. En optimización combinatoria , el problema del conector de Wiener mínimo consiste en encontrar dicho conector. Puede considerarse una versión del clásico problema del árbol de Steiner (uno de los 21 problemas NP-completos de Karp ), donde, en lugar de minimizar el tamaño del árbol, el objetivo es minimizar las distancias en el subgrafo. ^{[ 1 ] [ 2 ]}

El conector de Wiener mínimo fue presentado por primera vez por Ruchansky et al. en 2015. ^{[ 3 ]}

El conector mínimo de Wiener tiene aplicaciones en muchos ámbitos donde existe una estructura de grafo y un interés en conocer las conexiones entre conjuntos de individuos. Por ejemplo, dado un conjunto de pacientes infectados con una enfermedad viral, ¿qué otros pacientes deberían examinarse para encontrar al causante? O dado un conjunto de proteínas de interés, ¿qué otras proteínas participan en las mismas vías metabólicas?

El conector Wiener recibió su nombre en honor al químico Harry Wiener, quien introdujo por primera vez el índice Wiener .

El índice de Wiener es la suma de las distancias de los caminos más cortos en un (sub)grafo.${\displaystyle d(u,v)}$para denotar el camino más corto entre${\displaystyle u}$y${\displaystyle v}$, el índice de Wiener de un (sub)grafo${\displaystyle S}$, denotado${\displaystyle W(S)}$, se define como

${\displaystyle W(S)=\sum _{(u,v)\in S}d(u,v)}$.

El problema del conector de Wiener mínimo se define de la siguiente manera. Dado un grafo no dirigido y no ponderado con un conjunto de vértices${\displaystyle V}$y conjunto de bordes${\displaystyle E}$y un conjunto de vértices de consulta${\displaystyle Q\subseteq V}$, encontrar un conector${\displaystyle H\subseteq V}$del índice mínimo de Wiener. Más formalmente, el problema consiste en calcular

${\displaystyle \operatorname {*} {arg\,min}_{H}W(H\cup Q)}$,

es decir, encontrar un conector${\displaystyle H}$que minimiza la suma de los caminos más cortos en${\displaystyle H}$.

El problema del conector de Wiener mínimo está relacionado con el problema del árbol de Steiner . En el primero, la función objetivo de la minimización es el índice de Wiener del conector, mientras que en el segundo, la función objetivo es la suma de los pesos de las aristas del conector. Las soluciones óptimas a estos problemas pueden diferir, dado el mismo grafo y conjunto de vértices de consulta. De hecho, una solución para el problema del árbol de Steiner puede ser arbitrariamente mala para el problema del conector de Wiener mínimo; el grafo de la derecha proporciona un ejemplo.

El conector de Wiener mínimo se comporta como la centralidad de intermediación .

Cuando los vértices de consulta pertenecen a la misma comunidad, los vértices que no son de consulta y que forman el conector de Wiener mínimo tienden a pertenecer a la misma comunidad y a tener una alta centralidad dentro de ella. Es probable que dichos vértices sean vértices influyentes que desempeñan roles de liderazgo en la comunidad. En una red social , estos vértices influyentes podrían ser buenos usuarios para difundir información o para ser el objetivo de una campaña de marketing viral. ^{[ 5 ]}

Cuando los vértices de consulta pertenecen a comunidades diferentes, los vértices que no son de consulta y que forman el conector de Wiener mínimo contienen vértices adyacentes a aristas que unen las distintas comunidades. Estos vértices cubren un hueco estructural en el grafo y son importantes. ^{[ 6 ]}

El conector de Wiener mínimo es útil en aplicaciones en las que se desea conocer la relación entre un conjunto de vértices en un grafo. Por ejemplo,

• En biología , proporciona información sobre cómo se relaciona un conjunto de proteínas en una red de interacción proteína-proteína ,
• En las redes sociales (como Twitter ), muestra las comunidades a las que pertenece un conjunto de usuarios y cómo se relacionan estas comunidades.
• En redes informáticas , puede resultar útil para identificar una forma eficiente de enrutar un mensaje multicast a un conjunto de destinos.