Винеровский каркас
Винеровский каркас — это средство максимизации эффективности соединений «выделенных вершин» в сети. Он назван в честь химика Гарри Винера, предложившего индекс Винера. Если дан связный неориентированный граф и выделенный набор вершин в графе, минимальным каркасом Винера называется порождённый подграф, который соединяет выделенные вершины, минимизируя при этом сумму длин кратчайших путей среди всех пар вершин в подграфе. В комбинаторной оптимизации задача о минимальном винеровском каркасе — это задача поиска минимального винеровского каркаса. Задачу можно рассматривать как версию классической задачи Штейнера о минимальном дереве (одной из 21 NP-полных задач Карпа), где вместо минимизации размера дерева целью является минимизация расстояний в подграфе. Минимальный винеровский каркас впервые представили в 2015 году Ручански, Бончи и др. Минимальный винеровский каркас имеет приложения во многих областях, где имеется структура графа и целью изучения являются связи между набором индивидуальных элементов. Например, если есть набор пациентов, поражённых вирусной инфекцией, какие другие пациенты должны быть проверены, чтобы найти источник заражения? Или, если дан набор исследуемых протеинов, какие другие протеины участвуют в их путях взаимодействия? Описание задачиИндекс Винера — это сумма кратчайших путей в (под)графе. Если обозначить через d ( u , v ) {displaystyle d(u,v)} кратчайший путь между u {displaystyle u} и v {displaystyle v} , индекс Винера (под)графа S {displaystyle S} , обозначаемый как W ( S ) {displaystyle W(S)} , определяется как W ( S ) = ∑ ( u , v ) ∈ S d ( u , v ) {displaystyle W(S)=sum _{(u,v)in S}d(u,v)} .Задача о минимальном винеровском каркасе формулируется следующим образом. Пусть дан неориентированный невзвешенный граф с набором вершин V {displaystyle V} и набором рёбер E {displaystyle E} , и пусть в этом графе выделен набор вершин Q ⊆ V {displaystyle Qsubseteq V} . Задача заключается в нахождении соединяющего выделенные вершины подграфа H ⊆ V {displaystyle Hsubseteq V} с минимальным индексом Винера. Более формально, задача заключается в вычислении * a r g m i n H W ( H ∪ Q ) {displaystyle operatorname {*} {arg,min}_{H}W(Hcup Q)} ,то есть в нахождении каркаса H {displaystyle H} который минимизирует кратчайшие пути в H {displaystyle H} . Связь с деревом ШтейнераЗадача о минимальном винеровском каркасе связана с задачей Штейнера о минимальном дереве. В первом случае целевой функцией является индекс Винера в каркасе, а во втором случае целевой функцией является сумма весов рёбер в каркасе. Оптимальные решения этих задач могут отличаться для одно и того же графа и набора выделенных вершин. Фактически, решение задачи Штейнера о минимальном дереве может быть произвольно плохим для задачи минимизации винеровского каркаса. Граф справа даёт пример такого несовпадения. Вычислительная сложностьТрудностьЗадача NP-трудна и не допускает приближённую схему полиномиального времени, если только не P = NP. Это можно доказать с помощью неаппроксимируемости вершинного покрытия в графах ограниченной степени. Хотя нет аппроксимационной схемы полиномиального времени, имеется аппроксимация полиномиального времени с постоянной точностью — алгоритм, который находит каркас, индекс Винера которого не отличается более чем на постоянный множитель от оптимального решения. В терминах классов сложности задача нахождения минимального винеровского каркаса имеет сложность APX, но не PTAS, если только не P = NP. Точные алгоритмыПолный перебор всех возможных подмножеств вершин для получения того, который порождает каркас с минимальным индексом Винера, даёт алгоритм, который находит оптимальное решение за время 2 O ( n ) {displaystyle 2^{O(n)}} (то есть, экспоненциальное время) для графов с n вершинами. В специальном случае, когда имеется ровно две выделенные вершины, оптимальным решением является кратчайший путь, соединяющий две вершины, так что задача может быть решена за полиномиальное время путём вычисления кратчайшего расстояния. Фактически, для любого фиксированного числа выделенных вершин оптимальное решение может быть найдено за полиномиальное время. Аппроксимационные алгоритмыСуществует аппроксимационный алгоритм с постоянной точностью для задачи о винеровском каркасе, работающий за время O ( q ( m log n + n log 2 n ) ) {displaystyle O(q(mlog n+nlog ^{2}n))} на графе с n вершинами, m рёбрами и q выделенными вершинами, примерно с тем же временем работы, которое нужно для вычисления кратчайших расстояний от выделенных вершин до всех других вершин в графе. Центральным местом в этом алгоритме является сведение задачи к задаче поиска дерева Штейнера с взвешенными вершинами, которая позволяет аппроксимацию с постоянной точности, в частности для случаев, связанных с задачей нахождения минимального винеровского каркаса. ПоведениеМинимальный винеровский каркас ведёт себя подобно степени посредничества. Когда выделенные вершины принадлежат тому же сообществу, невыделенные вершины, которые образуют минимальный винеровский каркас, имеют тенденцию принадлежать тому же сообществу и имеют высокую центральность в сообществе. Такие вершины наиболее вероятно будут вершинами, играющими лидирующие роли в сообществе. В социальной сети эти влиятельные вершины могут быть хороши для распространения информации или как цели в виртуальной маркетинговой кампании. Когда выделенные вершины принадлежат разным сообществам, невыделенные вершины, которые формируют минимальный винеровский каркас, содержат вершины, смежные рёбрам, которые являются мостами для различных сообществ. Эти вершины образуют структурную дыру в графе и являются важными. ПриложенияМинимальный винеровский каркас полезен в приложениях, в которых хотят изучить связи между набором вершин в графе. Например,
|
