> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter15..md). # Chapter15. Outbreak Detection in Networks ### Outbreak detection Outbreak : 발생, 발발, 돌발 (출처 : Wiki) 이번 강의에서는 어떤 사건의 발생을 예측, 감시하는 시스템을 배운다. 낯선 주제이지만 예시를 들어보면 직관적인 문제이다. 어느 마을에는 수도관이 밑의 그림처럼 복잡하게 연결되어있다. 이 때 특정 노드에서 수질감염이 일어났다고 하자. 수도관이 연결되어있기 때문에 오염된 물은 퍼져나갈 것이고, 그림에서는 이를 빨간 색 영역으로 표시되어있다. ![](/files/-M7I8gwBuYrDYeO8iCtZ) 모든 집집마다 센서를 달아서 당장 어느 집이 문제인지 예측하면 좋으련만, 실제로는 몇 천, 몇 만이 될지 모르는 모든 수도관 하나하나마다 그 일을 할 수 있을까? 그래서 어디에 센서를 달아야 가장 효율적으로 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을 하기 때문에 어느 지점에서 오염이 일어났느냐에 따라 전파되는 구간이 저마다 다르다. ![](/files/-M7IDXLBYk_ufoMM8NPD) ![](/files/-M7IDwRghhwUOjRDXpTA) 둘 째 그림 중 빨간 구간에서의 오염이 여타 구간보다 많은 영향을 끼칠 것이라는 것을 알 수 있다. 그렇다면 간단히 생각해서 빨간 구간에 센서를 설치한다면 효율적으로 Outbreak Detection을 할 수 있을거라는 기대가 생긴다. ![](/files/-M7IEpLqtIbVs25LYaL1) #### 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 ![](/files/-M7IgwSOQKlCXWlhfzXv) **Reward (one of the follwing three)** 1. detection에 걸리는 시간을 최소화 2. detected propagation를 최대한 많이 탐색 3. (예시에 맞춰보자면) 감염된 사람의 수 최소화 **Cost (context dependent)** * 연결이 너무 많으면 탐색에 시간이 오래 걸림 * E.g. 각종 신문사의 뉴스를 한 데 모아놓은 네이버뉴스에서 Outbreak Detection을 하기 위해서 모든 글을 읽을 수 있을까? * 원격지에 센서를 설치하는 방법은 비용이 많이 든다? ![](/files/-M7Ij0oA_oAo24pdsryR) #### 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**이라고 한다. (참고 : ) ![](/files/-M7IpqpchiZeazNOtlQI) 이제 아래의 비슷한 예시를 가지고 Submodular를 살펴보자. (출처 : ) ![](/files/-M8RDMxkKq0nsGmIP4q6) 건물에 화재를 예방할 센서를 부착하고자 한다. Marginal gain은 새로운 센서를 부착했을 때, 효용의 크기라고 이해하면 될 것 같다. 기존 센서 집합 A가 주어졌을 때 새로운 센서 s가 설치 되었을 때 우리의 목적함수 f값은 수식으로 다음과 같다. $$F(s|A) = F(A\cup{s}) - F(A)$$ ![](/files/-M8RDZ1tB8Lu8uOHoTXf) 그러나 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이기 때문에 배경 원리를 그대로 가지고 간다. ![](/files/-M8RJpPWf8dnmPwBeejR) ![](/files/-M8RM1yjDafr8qDm8zSp) 이번 목표는 우리의 목적함수 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를 최적화하면 어떨까? ![](/files/-M8UoQzegJTVAHgz-zgX) 이 경우도 문제점이 있다. 다음의 예시를 보 ![](/files/-M8Uop76ZvxYgQCf4x_-) #### 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 ![](/files/-M8Uv3xQbFOU68m6FYCn) ## Speeding-up Hill-Climbing Lazy Evaluations ![](/files/-M8UwOaRLMoAgRd0AVxJ) 이제 Hill-Climbing의 속도를 높여보자. 기존 방법이었다면 i째 round의 센서 집합 S가 있을 때, 다음 센서를 고르는 방법은 marginal gain은 최대화하는 센서를 골랐다. 그러나 여기서 submodularity property를 다시 살펴보면 A가 B의 subset일 때 A의 margin gain은 항상 크다는 공식이 있다. 그러니까 round가 흐를 수m센서 u를 뭘 고르든 arginal benefit은 항상 작아진다는 점에 주목하자 ![](/files/-M8VA8gF4DjM5-w6Ilh8) 이진탐색에도 사용되는 upper-bound라는 원리를 사용하는 건데, 어렵게 수식같은 거 없어도 이해는 된다. 먼저 S1 = {a}인 상태에서 gain을 구했고, 나머지에서 탐색을 할 차례이다. 남은 것들 중에서 내림차순으로 sort하자. ![](/files/-M8VBVLTwucUWBvxhjv2) 그리고 첫 째 노드의 margin을 구한다. ![](/files/-M8VEU6A9_dlrQB6gwUt) d노드까지 S에 포함시킬 때 실제 효용량 다른 노드들의 gain보다 작아졌다. 이러면 알고리즘의 해가 아니게 되었으니 지금 구한 gain을 기준으로 다시 sort하자. 이번엔 b가 제일 위에 올라왔다. ![](/files/-M8VF1RDi9rNIHySdgDQ) gain을 구해보니 b의 값이 다른 노드들과 비교했을 때 가장 컸다. 아까 말한 upper-bound를 따져보면 분명 gain은 무조건 감소하는 값이다. 따라서 다른 후보군 중에서 b보다 gain이 클 경우는 아예 없기 때문에 b를 채택하여 S에 추가한다. ![](/files/-M8VFlIQdzkw0jpVj-Rn) 이 방식을 반복하면 계산량을 아주 많이 줄일 수 있다. ![](/files/-M8VG5P04TCw8iasT9bp) ## Data Dependent Bound on the Solution Quality Greedy 알고리즘의 solution quality를 얘기할 차례이다. 이 알고리즘은 항상 정답이 아닌 근사치를 제공하곤 한다. submodular의 경우 (1-1/e) bound가 존재한다. 무조건 정답을 제공하지 않는다는 점에서 걱정이 드니까 우리는 "이 데이터에서 greedy 알고리즘이 1-1/e 보다 몇 퍼센트 더 나은 해답을 제공할거야" 라는 확신을 받았으면 좋겠다는 희망을 가지게 된다. ![](/files/-M8VO_SHIqHaz6c5NExv) 증명에 따라서 f(OPT)는 항상 f(S) + 델타 i들의 합이다. 포인트는 우항의 값들은 실제로 우리가 구할 수 있으니까 최적해는 무조건 이 값보다 같거나 작을 것이라고 추론할 수 있다.