조밀도 하위그래프

컴퓨터 과학에서 고도로 연결된 서브그래프의 개념은 자주 나타난다.이 개념은 다음과 같이 공식화할 수 있다.Let ${\displaystyle G=(E,V)}$ be an undirected graph and let ${\displaystyle S=(E_{S},V_{S})}$ be a subgraph of ${\displaystyle G}$. Then the density of ${\displaystyle S}$ is defined to be ${\displaystyle d(S)={ E_{S} \over$$V_{S}}$

가장 밀도가 높은 서브그래프 문제는 최대 밀도의 서브그래프를 찾는 것이다.1984년 앤드루 V. 골드버그는 다항 시간 알고리즘을 개발하여 최대 흐름 기법을 이용하여 최대 밀도 서브그래프를 찾아냈다.이것은 1989년^[1] 갈로, 그리고리아디스, 타르잔에 의해 개선되어 $O{\displaystyle (n}$ m ${\displaystyle \log }$ ${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}{}^{}}$/ ${\displaystyle m}$)${\displaystyle O(nm\log(n^{2}\!/m)}$회$$ 운행되었다.최적의 솔루션을 찾기 위한 간단한 LP는 2000년에 Charikar에 의해 제공되었다.^[2]

Densest k 하위 그래프

가장 밀도가 높은 서브그래프 문제에는 많은 변화가 있다.그 중 하나가 가장 밀도가 높은 k 서브그래프 문제인데, 여기서 목적은 정확히 k 정점에서 최대 밀도 서브그래프를 찾는 것이다.이 문제는 clique 문제를 일반화하므로 일반 그래프에서는 NP-hard이다. {\$displaystyle \epsilon >0$^[3]에 대해$$ $n{\displaystyle {}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/${\displaystyle {4\mathrm{}}^{}}$ + ${\displaystyle {ϵ}^{}}$ ${\$의 비율 내에서 가장 밀도가 높은 k 하위 그래프에 근접한 다항 알고리즘이 존재하지만, $n{\displaystyle {}^{}}$ ${\displaystyle {1\mathrm{}}^{}}$/ ${\displaystyle {\mathrm{polylog}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ⁡ n ⁡{n${\\$ n$^{1/!$$\operatorname {polyloglog}n}$ - 지수 시간 가설이 거짓이 아닌 한 다항 시간에서의 근사치$$.^[4]Under a weaker assumption that ${\displaystyle {\mathsf {NP}}\nsubseteq \bigcap _{\epsilon >0}{\mathsf {BPTIME}}(2^{n^{\epsilon }})}$, no PTAS exists for the problem.^[5]

문제는 초당적 그래프와 화음 그래프에서 NP-hard로 남아있지만 나무와 분할 그래프의 경우 다항식이다.^[6]문제가 (적절한) 구간 그래프와 평면 그래프에서 NP-하드인지 다항식인지는 공개되지만, 하위 그래프를 연결해야 하는 문제의 변동은 평면 그래프에서 NP-하드다.^[7]

최대 k개까지의 밀도

최대 $k{\displaystyle }$ ${\displaystyle k}$ 문제에서$$ 가장 밀도가 높은 목적은 최대 $k{\displaystyle }$ ${\displaystyle k}$ 정점에서$$ 최대 밀도 하위 그래프를 찾는 것이다.Anderson과 Chellapilla는 이 문제에 대해 $\alpha {\displaystyle }$ ${\$${\displaystyle {displaystyle\mathrm{}}^{}}$ $alpha }$ - 근사치가$$ 있을 경우$,$ 가장 밀도가 높은 $k{\displaystyle }$ ${\displaystyle k}$ 서브그래프$$ 문제에 대한 근사치가$$ $발생$한다는 것을 보여주었다.

최소 k 하위 그래프 밀도

최소 $k{\displaystyle }$ ${\displaystyle k}$ 문제는$$ 대부분의 $k{\displaystyle }$ ${\displaystyle k}$ 하위 그래프$$ 문제와 유사하게 정의된다.문제는 NP-완전이지만 다항식 시간에는 2-대략을 인정한다.^[8][9]더욱이, 이 근사 알고리즘이 본질적으로 최선의 방법이라는 증거가 있다: 스몰 세트 확장 가설(유일한 게임 추측과 밀접하게 관련된 계산 복잡성 가정)을 가정하면, e의 경우 문제를${\displaystyle }$(${\displaystyle 2}$ -${\displaystyle )}$ ) ${\displaystyle (2-\epsilon )}$인자로$$ 추정하는 것은 NP-힘이다.매우 상수 > ${\displaystyle \epsilon >0$^[10]

K-클리크 밀도 하위 그래프

Charalampos Tsurakis는 $k{\displaystyle }$ ${\displaystyle k}$ -clike$$ densest subgraph 문제를 소개했다.This variation of the densest subgraph problem aims to maximize the average number of induced ${\displaystyle k}$ cliques ${\displaystyle d_{k}(S)={ C_{k}(S) \over V_{S} }}$, where ${\displaystyle C_{k}(S)}$ is the set of ${\displaystyle k}$-c$S{\displaystyle }$ ${\displaystyle S}$에 의해 유도된 주류$.$ 가장 밀도가 높은 서브그래프 문제는 $k{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle k=2}$에 대한 특수한 경우로서 얻어진다$.$ 이러한 일반화는 대규모 실세계 네트워크에서 큰 근위차를 추출하기 위해 경험적으로 성공적인 다시간 접근법을 제공한다.

로컬 최상위 k 밀도 하위 그래프

Chin 등에서는 그래프에서 가장 밀도가 높은 서브그래프 발견의 문제를 소개했는데, 각각은 그래프에서 가장 높은 밀도를 달성하는데, 이것은 같은 밀도나 더 큰 밀도를 가진 어떤 수퍼그래프에도 포함되어 있지 않으며, 밀도가 가장 높은 서브그래프를 나머지 지역 밀도 서브그래프와 느슨하게 연결되어 있는 서브그래프를 포함하고 있다.가장 밀도가 높은 서브그래프 문제는 ${\displaystyle \mathrm{k}}$= 1 ${\displaystyle k=1}$의 특수한 경우로 파악된다는 점에 유의하십시오$.$ 그래프의 로컬 밀도가 가장 높은 서브그래프 집합은 다항식 시간으로 계산할 수 있다.

참조

추가 읽기