Русская Википедия:Винеровский каркас

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Назван в честь химика Шаблон:Нп2, предложившего индекс Винера.

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

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

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

Описание задачи

Индекс Винера — это сумма кратчайших путей в (под)графе. Если обозначить через <math>d(u,v)</math> кратчайший путь между <math>u</math> и <math>v</math>, индекс Винера (под)графа <math>S</math>, обозначаемый как <math>W(S)</math>, определяется как

<math>W(S) = \sum_{(u, v) \in S} d(u,v)</math>.

Задача о минимальном винеровском каркасе формулируется следующим образом. Пусть дан неориентированный невзвешенный граф с набором вершин <math>V</math> и набором рёбер <math>E</math>, и пусть в этом графе выделен набор вершин <math>Q\subseteq V</math>. Задача заключается в нахождении соединяющего выделенные вершины подграфа <math>H\subseteq V</math> с минимальным индексом Винера. Более формально, задача заключается в вычислении

<math>\operatorname*{arg\,min}_H W(H\cup Q)</math>,

то есть в нахождении каркаса <math>H</math> который минимизирует кратчайшие пути в <math>H</math>.

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

Файл:SteinerExample nicer.pdf
Оптимальное решение задачи о дереве Штейнера и задачи о винеровском каркасе могут отличаться. Определим выделенные вершины Q как Q = {v1, …, v10}. Единственным оптимальным решением задачи о дереве Штейера является само Q, которое имеет индекс Винера 165, в то время как оптимальным решением задачи о винеровском каркасе будет Q ∪ {r1, r2}[1], которое имеет индекс Винера 142.

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

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

Трудность

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

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

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

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

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

Поведение

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

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

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

Приложения

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Обратите внимание, что это не дерево!
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Винеровский_каркас&oldid=9406716