Винеровский разъем

В теории сетей соединитель Винера — это средство максимизации эффективности соединения указанных «вершин запроса» в сети. Учитывая связный неориентированный граф и набор вершин запроса в графе, минимальный соединитель Винера представляет собой индуцированный подграф , который соединяет вершины запроса и минимизирует сумму расстояний кратчайшего пути среди всех пар вершин в подграфе. В комбинаторной оптимизации проблема минимального винеровского соединителя — это проблема поиска минимального винеровского соединителя. Ее можно рассматривать как версию классической задачи о дереве Штейнера (одну из 21 NP-полной задачи Карпа ), где вместо минимизации размера дерева целью является минимизация расстояний в подграфе.

Минимальный винеровский коннектор был впервые представлен Ручанским и др. в 2015 году.

Минимальный коннектор Винера находит применение во многих областях, где существует графовая структура и интерес к изучению связей между группами людей. Например, учитывая набор пациентов, зараженных вирусным заболеванием, каких еще пациентов следует проверить, чтобы найти виновника? Или, учитывая набор интересующих белков, какие другие белки участвуют в путях с ними?

Разъем Винера был назван в честь химика Гарри Винера, который впервые ввел индекс Винера .

Определение проблемы

Индекс Винера представляет собой сумму расстояний по кратчайшим путям в (под)графе. С использованием $d(u,v)$ для обозначения кратчайшего пути между $u$ и $v$, индекс Винера (под)графа $S$, обозначенный $W(S)$, определяется как

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

Задача о минимальном винеровском соединителе определяется следующим образом. Дан неориентированный и невзвешенный граф с множеством вершин. $V$ и набор кромок $E$ и набор вершин запроса $Q\subseteq V$, найди разъем $H\subseteq V$ минимального индекса Винера. Более формально, проблема состоит в том, чтобы вычислить

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

то есть найти разъем $H$ минимизирующее сумму кратчайших путей в $H$.

Связь с деревом Штейнера

Оптимальные решения задачи дерева Штейнера и минимального соединителя Винера могут различаться. Определим набор вершин запроса Q как Q = { v ₁ , ..., v ₁₀ }. Единственным оптимальным решением проблемы дерева Штейнера является сам Q , имеющий индекс Винера 165, тогда как оптимальным решением проблемы минимального соединителя Винера является Q ∪ { r ₁ , r ₂ }, который имеет индекс Винера 142.

Проблема минимального соединителя Винера связана с проблемой дерева Штейнера . В первом случае целевой функцией при минимизации является индекс Винера соединителя, тогда как во втором целевая функция представляет собой сумму весов ребер соединителя. Оптимальные решения этих проблем могут различаться при условии одного и того же графа и набора вершин запроса. Фактически, решение проблемы дерева Штейнера может быть сколь угодно плохим для проблемы минимального соединителя Винера; график справа представляет собой пример.

Вычислительная сложность

Твердость

Задача является NP-сложной и не допускает схемы аппроксимации за полиномиальное время, если только P = NP . Это можно доказать, используя неаппроксимируемость вершинного покрытия в графах ограниченной степени. Хотя схемы аппроксимации с полиномиальным временем не существует, существует аппроксимация с постоянным коэффициентом полиномиального времени - алгоритм, который находит разъем, индекс Винера которого находится в пределах постоянного мультипликативного коэффициента индекса Винера оптимального разъема. С точки зрения классов сложности минимальная задача винеровского соединителя находится в APX , но не в PTAS, если только P = NP .

Точные алгоритмы

Исчерпывающий перебор всех возможных подмножеств вершин с целью найти ту, которая индуцирует коннектор с минимальным индексом Винера, дает алгоритм, который находит оптимальное решение в $2^{O(n)}$ время (то есть экспоненциальное время ) на графах с n вершинами. В особом случае, когда имеется ровно две вершины запроса, оптимальным решением является кратчайший путь, соединяющий две вершины, поэтому проблему можно решить за полиномиальное время путем вычисления кратчайшего пути. Фактически, для любого фиксированного постоянного числа вершин запроса оптимальное решение может быть найдено за полиномиальное время.

Алгоритмы аппроксимации

Существует алгоритм аппроксимации с постоянным коэффициентом для задачи минимального винеровского соединителя, работающий во времени. $O(q(m\log n+n\log ^{2}n))$ на графе с n вершинами, m ребрами и q вершинами запроса примерно столько же времени требуется для вычисления расстояний кратчайшего пути от вершин запроса до каждой другой вершины в графе. Центральный подход этого алгоритма состоит в том, чтобы свести проблему к проблеме дерева Штейнера, взвешенной по вершинам, которая допускает аппроксимацию с постоянным коэффициентом в определенных случаях, связанных с проблемой минимального соединителя Винера.

Поведение

Минимальный коннектор Винера ведет себя как центральность посредничества .

Когда вершины запроса принадлежат одному и тому же сообществу, вершины, не относящиеся к запросу, которые образуют минимальный коннектор Винера, как правило, принадлежат к одному и тому же сообществу и имеют высокую центральность внутри сообщества. Такие вершины, скорее всего, будут влиятельными вершинами, играющими руководящую роль в сообществе. В социальной сети эти влиятельные вершины могут быть хорошими пользователями для распространения информации или для целевой кампании вирусного маркетинга.

Когда вершины запроса принадлежат разным сообществам, вершины, не относящиеся к запросу, которые образуют минимальный соединитель Винера, содержат вершины, смежные с ребрами, соединяющими разные сообщества. Эти вершины закрывают структурную дыру в графе и очень важны.

Приложения

Минимальный соединитель Винера полезен в приложениях, в которых требуется узнать о взаимосвязях между набором вершин графа. Например,

• в биологии наборы белков в сети белок-белкового взаимодействия , он дает представление о том, как связаны
• в социальных сетях (таких как Twitter ) он демонстрирует сообщества, к которым принадлежит набор пользователей, и то, как эти сообщества связаны,
• в компьютерных сетях это может быть полезно для определения эффективного способа маршрутизации многоадресного сообщения к набору пунктов назначения.