Плотный подграф - Dense subgraph

Пример графа с плотностью и его самый плотный подграф, индуцированный вершинами и красным с плотностью${\ displaystyle G}$${\ displaystyle d_ {G} = 1,375}$${\ displaystyle b, c, d, e}$${\ displaystyle h}$${\ displaystyle 1.4}$

В информатике часто появляется понятие сильно связанных подграфов. Это понятие можно формализовать следующим образом. Пусть будет в неориентированный граф , и пусть будет подграф из . Затем плотность от определяется как . ${\ Displaystyle G = (E, V)}$${\ Displaystyle S = (E_ {S}, V_ {S})}$${\ displaystyle G}$${\ displaystyle S}$${\ displaystyle d (S) = {| E_ {S} | \ over | V_ {S} |}}$

Самая плотная проблема подграфа - это найти подграф максимальной плотности. В 1984 году Эндрю В. Голдберг разработал алгоритм полиномиального времени для поиска подграфа максимальной плотности с использованием метода максимального потока . Это было улучшено Галло, Григориадисом и Тарьяном в 1989 году, чтобы работать вовремя. Простая ЛП для поиска оптимального решения была дана Чарикаром в 2000 году. ${\ Displaystyle О (нм \ журнал (п ^ {2} / м))}$

Самый плотный подграф k

Существует множество вариаций проблемы самого плотного подграфа. Одна из них - это задача о наиболее плотных k подграфах, цель которой - найти подграф максимальной плотности ровно на k вершинах. Эта проблема обобщает проблему клики и, таким образом, является NP-трудной для общих графов. Существует полиномиальный алгоритм, аппроксимирующий самый плотный подграф k в соотношении для каждого , в то время как он не допускает -аппроксимацию за полиномиальное время, если только гипотеза экспоненциального времени не является ложной. При более слабом предположении, что для проблемы не существует PTAS . ${\ displaystyle n ^ {{\ frac {1} {4}} + \ epsilon}}$${\ displaystyle \ epsilon> 0}$${\ displaystyle n ^ {\ frac {1} {\ operatorname {polylog} n}}}$${\ displaystyle {\ mathsf {NP}} \ nsubseteq \ bigcap _ {\ epsilon> 0} {\ mathsf {BPTIME}} (2 ^ {n ^ {\ epsilon}})}$

Проблема остается NP-сложной для двудольных графов и хордовых графов, но является полиномиальной для деревьев и расщепленных графов . Неизвестно, является ли проблема NP-трудной или полиномиальной в (собственных) интервальных графах и планарных графах ; однако вариант задачи, в которой требуется связность подграфа, NP-труден для плоских графов.

Густая в большинстве K подграфа

Задача задачи с максимальной плотностью - найти подграф с максимальной плотностью не более чем на вершинах. Андерсон и Челлапилла показали, что если существует приближение для этой проблемы, то это приведет к приближению для проблемы с наиболее плотным подграфом. ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle \ alpha}$${\ Displaystyle \ Theta (\ альфа ^ {2})}$${\ displaystyle k}$

Густой по крайней мере , K подграф

Самая плотная по крайней мере проблема определяется аналогично самой плотной по крайней мере проблеме подграфа. Задача NP-полная, но допускает 2-аппроксимацию за полиномиальное время. Более того, есть некоторые свидетельства того, что этот алгоритм аппроксимации, по сути, является наилучшим из возможных: если предположить гипотезу о расширении малого множества (предположение о вычислительной сложности, тесно связанное с гипотезой уникальных игр ), тогда NP-трудно аппроксимировать проблему с точностью до множителя для каждая константа . ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle (2- \ epsilon)}$${\ displaystyle \ epsilon> 0}$

K -кликовый плотнейший подграф

Харалампос Цуракакис представил задачу о -кликом плотнейшем подграфе. Этот вариант задачи о наиболее плотном подграфе направлен на максимальное увеличение среднего числа индуцированных клик , где - множество -клик, индуцированных . Обратите внимание, что проблема с наиболее плотным подграфом получается как частный случай для . Это обобщение обеспечивает эмпирически успешный многоразовый подход для извлечения крупных клик из крупномасштабных реальных сетей. ${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle d_ {k} (S) = {| C_ {k} (S) | \ over | V_ {S} |}}$${\ Displaystyle C_ {k} (S)}$${\ displaystyle k}$${\ displaystyle S}$${\ displaystyle k = 2}$

Локально топ- k самый плотный подграф

Qin et al. представил проблему обнаружения топ-k локально плотных подграфов в графе, каждый из которых достигает наивысшей плотности в своей локальной области в графе: он не содержится ни в каком суперграфе с такой же или большей плотностью, и он не содержит подграфов с плотностью слабо связан с остальной частью локального наиболее плотного подграфа. Отметим, что задача о наиболее плотном подграфе получается как частный случай для . Набор локально плотных подграфов в графе может быть вычислен за полиномиальное время. ${\ displaystyle k = 1}$

использованная литература

дальнейшее чтение