Chapter15. Outbreak Detection in Networks

CS224w by 신윤종

Outbreak detection

Outbreak : 발생, 발발, 돌발 (출처 : Wiki)

이번 강의에서는 어떤 사건의 발생을 예측, 감시하는 시스템을 배운다. 낯선 주제이지만 예시를 들어보면 직관적인 문제이다.

어느 마을에는 수도관이 밑의 그림처럼 복잡하게 연결되어있다. 이 때 특정 노드에서 수질감염이 일어났다고 하자. 수도관이 연결되어있기 때문에 오염된 물은 퍼져나갈 것이고, 그림에서는 이를 빨간 색 영역으로 표시되어있다.

모든 집집마다 센서를 달아서 당장 어느 집이 문제인지 예측하면 좋으련만, 실제로는 몇 천, 몇 만이 될지 모르는 모든 수도관 하나하나마다 그 일을 할 수 있을까? 그래서 어디에 센서를 달아야 가장 효율적으로 Outbreak Detection을 할 수 있는지 알아보자는 것이 주제이다.

General Problem

• Dynamic process spreading하는 Graph가 주어졌을 때, process를 효율적으로 detect하는 역할을 해낼 Node의 집합을 구하자

• Many other applications

  • Epidemics

  • Influence propagation

  • Network security

Water Network : Utility

마을의 수도관 그래프가 주어졌다고 하자. 수도관은 현재 Dynamic process spreading을 하기 때문에 어느 지점에서 오염이 일어났느냐에 따라 전파되는 구간이 저마다 다르다.

둘 째 그림 중 빨간 구간에서의 오염이 여타 구간보다 많은 영향을 끼칠 것이라는 것을 알 수 있다. 그렇다면 간단히 생각해서 빨간 구간에 센서를 설치한다면 효율적으로 Outbreak Detection을 할 수 있을거라는 기대가 생긴다.

Problem Setting

• Given Graph G(V, E)

• Given Outbreaks spread data

  • 이웃노드들 u에 전파하는 매 outbreak i 마다 time T(u, i) data를 알고있다고 하

• Goal : reward를 최대화 시키는 subset of nodes S를 선택하자

  • B = budget

Reward (one of the follwing three)

1. detection에 걸리는 시간을 최소화

2. detected propagation를 최대한 많이 탐색

3. (예시에 맞춰보자면) 감염된 사람의 수 최소화

Cost (context dependent)

• 연결이 너무 많으면 탐색에 시간이 오래 걸림

  • E.g. 각종 신문사의 뉴스를 한 데 모아놓은 네이버뉴스에서 Outbreak Detection을 하기 위해서 모든 글을 읽을 수 있을까?

  • 원격지에 센서를 설치하는 방법은 비용이 많이 든다?

Objectives for Outbreak Detection

• Penalty $π_i(t)$ for detecting outbreak i at time t

  • Time to detection(DT) : 오염을 발견하는데 얼마나 걸렸는가?

    • Penalty : $π_i(t) = t$
  • Detection likelihood (DL) : 얼마나 많은 오염을 발견하였는가?

    • Penalty : $π_i(t) = 0, π_i(∞) = 1$ (binary outcome)
  • Population affected (PA) : 얼마나 적은 사람이 오염된 물을 마셨는가?

    • Penalty : i째 Outbreak의 time t마다 감염된 노드의 숫자

• Observation : 어떤 목적함수를 쓰든 시간이 얼마나 적게 걸리든 손해가 없음 (monotone)

  • DT : 빨라야 하는 것이 당연한 이치

  • DL : 얼마나 걸리든 발견했냐 안했냐의 차이 뿐이다.

  • PA : 빨리 발견할 수록 감염 수가 적을 것이다.

Structure of the Problem

앞서 배운 목적함수를 그대로 사용하는 것이 아닌 penalty reduction 함수 f를 정의하여 사용한다. 이해하기 쉬운 예시를 보자.

아래 그림의 왼쪽 그래프에서 주황색 부분이 이전까지 설치한 센서2개로 커버할 수 있는 반경이다. 그리고 현재 새로운 센서가 설치되어 회색 부분을 커버할 수 있게 되었다. 주황색 부분과 별로 겹치지 않으면서 그래프의 넓은 반경을 커버하고 있다.

반대로 오른쪽 그림은 이전과 똑같은 센서가 설치되지만 이미 대부분 기존센서가 커버할 수 있는 상황이다. 이럴 때는 새로운 센서가 도움이 되지 않는다고 해석할 수 있다. 강의에서는 우리의 목적함수를 저번에 강의에서도 언급되었던 Submodular로 소개한다.

아래의 예시에서 N개의 센서 중 어떤 것을 설치할 지에 대한 경우의 수 집합의 크기는은 $2^N$이다. (the family of all subsets of N) 모든 경우의 수마다 penalty값이 나오는 함수 f를 우리는 이미 정의했으니 f : $2^N$→ $R$이다. 그리고 이 함수를 Set function이라고 한다. (참고 : http://www.iasi.cnr.it/~ventura/Cargese13/Lectures%20slides/Mccormick_Cargese%20intro.pdf)

이제 아래의 비슷한 예시를 가지고 Submodular를 살펴보자. (출처 : http://people.csail.mit.edu/stefje/mlss/cadiz_part1.pdf)

건물에 화재를 예방할 센서를 부착하고자 한다. Marginal gain은 새로운 센서를 부착했을 때, 효용의 크기라고 이해하면 될 것 같다. 기존 센서 집합 A가 주어졌을 때 새로운 센서 s가 설치 되었을 때 우리의 목적함수 f값은 수식으로 다음과 같다.

$F(s|A) = F(A\cup\{s\}) - F(A)$

그러나 B케이스에서 5개나 설치되있는 상태에 새로운 센서 s를 설치해보자. 그림으로만 봐도 효용이 떨어짐을 알 수 있다. 이렇듯 센서 집합에서 A가 B의 부분집합일 때, A에 s가 추가되는 것과 B에 s가 추가되는 것 사이에서 항상 A케이스에서 s의 효용이 커진다. 이를 수식적으로 표현하면

$F(A\cup\{s\}) - F(A) >= F(B\cup\{s\}) - F(B)$

정리하자면 A가 B의 subset일 때, 위의 조건을 만족하는 함수가 Submodular set function이라고 한다. 이번 강의에서 다루는 목적함수가 Submodular이기 때문에 배경 원리를 그대로 가지고 간다.

이번 목표는 우리의 목적함수 f가 Submodular라는 점을 증명하는 것이다. 우리의 목적함수는 time penalty도 중요하므로 새로운 센서 x가 outbreak를 발견하는 시기를 3가지 케이스로 나눠보자. 기준은 Submodular에서 설명할 때 썼던 집합 B와 A(A < B)를 사용하겠다.

1. T(B i) <= T(A, i) < T(x, i) : x가 가장 늦게 발견. 센서 x가 무쓸모!

2. T(B i) <= T(x, i) <= T(A, i) : x가 B와 A사이. A케이스보다 나은 상황을 만들어주지만, B의 경우에서는 아니라는 것.

3. T(x, i) < T(B, i) <= T(A, i) : x가 제일 빨리 발견함.

• A는 B의 subset이므로 항상 B가 A보다 앞에 있음!

• Submodular의 combination인 f(S)도 똑같은 Submodular이다.

• 이러한 3가지 케이스를 살펴보았을 때 우리의 목적함수는 Submodular이다!

우리의 Submodular를 최적화하는 전통적 방법은 Hill-climbing이다 저번 강의에서 소개되었는데, 이 방법은 2가지 문제점이있다.

1. unit cost case에서만 작동한다. 저번 강의에서는 k명의 influencer를 골랐듯 sensor s의 cost c(s) 같은 사례에 적용하는 거다.

2. Hill-climbing is slow. 매 반복마다 모든 노드 marginal gain을 계산해야한다. $O(|V| · K)$for placing K sensors

CELF : Algorithm for opt. submodular

Submodualr를 최적화하기 위한 Hill-climbing의 개선안으로 cost를 완전히 무시하고 reward를 최대화 하는 방식으로 센서를 설치할 수 있다. 그러나 이런 식은 금방 budget을 낭비해버릴 것이다.

Idea : benefit-cost ratio를 최적화하면 어떨까?

이 경우도 문제점이 있다. 다음의 예시를 보

Benefit - cost ratio의 한계점

2개의 센서 s1과 s2를 설치한다고 하자. c(s1)은 super cheep하고, c(s2)는 예산을 전부 쏟아부어야 한다. Outbreak는 딱 하나있고 benefit은 f(s1) = 2엡실론(엄청 작은 값), f(s2) = B라고할 때 . benefit-cost ratio를 살펴보자.

f(s1) / c(s1) = 2이고 f(s2) / c(s2) = 1이니까 우리의 알고리즘은 당연히 s1을 선택한다. 결국 reward가 B인데도 불구하고 2엡실론의 reward를 취하게 된다. 엡실론에 0을 대입하면 아무것도 얻지 못하는 상황인 것이다.

정리하자면 가성비를 따지기 위한 benefit-cost 비율은 cost가 낮은 노드를 맹목적으로 선택한다.

CELF (Cost-Effective Lazy Forward-selection)

two pass greddy algorithm. 두 가지 greedy 알고리즘을 사용하여 두 알고리즘의 결과 중 높은 값을 취한다. 앞서 배운 각각의 알고리즘이 단점이 명확함에도 불구하고 이 방법으로 정답과 매우 근사하게 최적화할 수 있다.

• Set (solution) $S`$: Use benefit-cost greedy
• Set (solution) $S``$: Use unit-cost greedy

Speeding-up Hill-Climbing Lazy Evaluations

이제 Hill-Climbing의 속도를 높여보자. 기존 방법이었다면 i째 round의 센서 집합 S가 있을 때, 다음 센서를 고르는 방법은 marginal gain은 최대화하는 센서를 골랐다.

그러나 여기서 submodularity property를 다시 살펴보면 A가 B의 subset일 때 A의 margin gain은 항상 크다는 공식이 있다. 그러니까 round가 흐를 수m센서 u를 뭘 고르든 arginal benefit은 항상 작아진다는 점에 주목하자

이진탐색에도 사용되는 upper-bound라는 원리를 사용하는 건데, 어렵게 수식같은 거 없어도 이해는 된다. 먼저 S1 = {a}인 상태에서 gain을 구했고, 나머지에서 탐색을 할 차례이다. 남은 것들 중에서 내림차순으로 sort하자.

그리고 첫 째 노드의 margin을 구한다.

d노드까지 S에 포함시킬 때 실제 효용량 다른 노드들의 gain보다 작아졌다. 이러면 알고리즘의 해가 아니게 되었으니 지금 구한 gain을 기준으로 다시 sort하자. 이번엔 b가 제일 위에 올라왔다.

gain을 구해보니 b의 값이 다른 노드들과 비교했을 때 가장 컸다. 아까 말한 upper-bound를 따져보면 분명 gain은 무조건 감소하는 값이다. 따라서 다른 후보군 중에서 b보다 gain이 클 경우는 아예 없기 때문에 b를 채택하여 S에 추가한다.

이 방식을 반복하면 계산량을 아주 많이 줄일 수 있다.

Data Dependent Bound on the Solution Quality

Greedy 알고리즘의 solution quality를 얘기할 차례이다. 이 알고리즘은 항상 정답이 아닌 근사치를 제공하곤 한다. submodular의 경우 (1-1/e) bound가 존재한다.

무조건 정답을 제공하지 않는다는 점에서 걱정이 드니까 우리는 "이 데이터에서 greedy 알고리즘이 1-1/e 보다 몇 퍼센트 더 나은 해답을 제공할거야" 라는 확신을 받았으면 좋겠다는 희망을 가지게 된다.

증명에 따라서 f(OPT)는 항상 f(S) + 델타 i들의 합이다. 포인트는 우항의 값들은 실제로 우리가 구할 수 있으니까 최적해는 무조건 이 값보다 같거나 작을 것이라고 추론할 수 있다.