Винеровский каркас

Винеровский каркас — средство максимизации эффективности соединений «выделенных вершин» в сети.

Назван в честь химика Харри Винера (англ. Harry Wiener), предложившего индекс Винера.

Если дан связный неориентированный граф и выделенный набор вершин в графе, минимальным каркасом Винера называется порождённый подграф, который соединяет выделенные вершины, минимизируя при этом сумму длин кратчайших путей среди всех пар вершин в подграфе. В комбинаторной оптимизации задача о минимальном винеровском каркасе — это задача поиска минимального винеровского каркаса. Задачу можно рассматривать как версию классической задачи Штейнера о минимальном дереве (одной из 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 выделенными вершинами, примерно с тем же временем работы, которое нужно для вычисления кратчайших расстояний от выделенных вершин до всех других вершин в графе. Центральным местом в этом алгоритме является сведение задачи к задаче поиска дерева Штейнера с взвешенными вершинами, которая позволяет аппроксимацию с постоянной точности, в частности для случаев, связанных с задачей нахождения минимального винеровского каркаса.

Поведение

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

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

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

Приложения

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

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

Литература

• Natali Ruchansky, Francesco Bonchi, David Garcia-Soriano, Francesco Gullo, Nicolas Kourtellis. The Minimum Wiener Connector // SIGMOD. — 2015. — . — arXiv:1504.00513.
• Irit Dinur, Samuel Safra. On the hardness of approximating minimum vertex cover // Annals of Mathematics. — 2005. — Т. 162. — doi:10.4007/annals.2005.162.439.
• Oliver Hinz, Bernd Skiera, Christian Barrot, Jan U. Becker. Seeding Strategies for Viral Marketing: An Empirical Comparison // Journal of Marketing. — 2011. — Т. 75, № 6. — doi:10.1509/jm.10.0088.
• Tiancheng Lou, Jie Tang. Mining Structural Hole Spanners Through Information Diffusion in Social Networks // Proceedings of the 22nd International Conference on World Wide Web. — Rio de Janeiro, Brazil: International World Wide Web Conferences Steering Committee, 2013. — ISBN 9781450320351.
• Frank Hwang, Dana Richards, Dana Winter, Pawel Winter. The Steiner Tree Problem // Annals of Discrete Mathematics. — 1992.