Chapter16. network evolution graph

투빅스 12기 배유나

Evolving Networks:

시간이 지남에 따라(시간의 함수로) 변화하는 네트워크

노드, 링크의 추가 및 제거로 네트워크가 자연스럽게 확장된다.

1. 네트워크 전체적 관점

2. 서브 구조, 하위 그래프 관점

3. 노드 관점, 전체 네트워크에서 노드 및 링크의 비율

Macroscopic of Evolution of Networks

의문 3가지 .

1. 시간이 지남에 따른 노드수와 엣지 수의 관계는 어떻게 되느냐?

2. 네트워크가 커지면 직경은 어떻게 변하느냐?

3. 네트워크가 성장함에 따라 degree 분포는 어떻게 evolve하는가?

의문 1. 시간이 지남에 따른 노드수와 엣지 수의 관계는 어떻게 되느냐?

Densification Power Law

정상적인 네트워크의 그래프 노드와 엣지 수가 로그 스케일 상에서 선형함수의 형태를 가진다.

엣지의 수는 노드의 수보다 빨리 증가한다. -> average degree(엣지수/노드수) 증가한다.

-> densification power law에 반한다.

의문 2. 네트워크가 커지면 직경은 어떻게 변하느냐?

why ? 그래프 진화, 성장 -> 노드 간 거리 축소(감소)

by 1번 의문 결과,

노드 수 증가 < 엣지 수 증가

-> average degree 증가 (연결성 증가) -> 밀도의 증가

2번의문의 파생적 의문

직경의 감소는 단지 밀도의 결과인가?

압축 랜덤 그래프의 지름이 증가함 -> 지름이 줄어드는 것 이상의 것이 있다!

비슷한 감소 양상 보임

-> densification 뿐만 아니라 degree distribtion이 diameter 감소 일으킴.

의문 3. 네트워크가 성장함에 따라 degree 분포는 어떻게 evolve하는가?

degree 분포의 시간적 진화와 그래프의 밀도 사이의 연관성

How does degree distribution evolve to allow for densification?

실제 네트워크에서 나타나는 degree distribution은 power law distribution(heavy tail)을 띈다.

그래프 사이즈가 증가하므로, r_t 감소

(이부분 동영상 강의로 이해안되서.... 논문 읽음)

(By. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations)

Most of the recent models of network evolution capture the growth process in a way that incorporates two pieces of “conventional wisdom:”

(A) Constant average degree assumption: The average node degree in the network remains constant over time. (Or equivalently, the number of edges grows linearly in the number of nodes.)

(B) Slowly growing diameter assumption: The diameter is a slowly growing function of the network size, as in “small world”

Recent work has given tight asymptotic bounds on the diameter of preferential attachment networks [6, 9]; depending on the precise model, these bounds grow logarithmically or even slower than logarithmically in the number of nodes. How are assumptions (A) and (B) reflected in data on network growth? Empirical studies of large networks to date have mainly focused on static graphs, identifying properties of a single snapshot or a very small number of snapshots of a large network. For example, despite the intense interest in the Web’s link structure, the recent work of Ntoulas et al. [25] noted the lack of prior empirical research on the evolution of the Web.

Thus, while one can assert based on these studies that, qualitatively, real networks have relatively small average node degrees and diameters, it has not been clear how to convert these into statements about trends over time.

기존 연구는 정적 그래프에서 1. node's degrees 2. distance between pairs of nodes(지름)을 중점으로 연구.

실제 네트워크는 시간이 지나면서 진화한다 (노드의 추가 및 삭제)

따라서, 최근 네트워크 진화 모델은 기존의 위 두가지 통합하는 방식으로 성장과정을 포착한다.

1) constant average degree assumption

: 네트워크 average node degreee가 유지된다.

2) sowly growing diameter assumption

: 네트워크 사이즈가 증가한다.

-> 새 노드가 추가되면, 기존 네트워크에 일정한 수의 아웃링크에 부착된 네트워크 구축

-> 뚜렷한 점증적 asympotic 한계 보인다.....

-> 현재까지 대규모 네트워크에 대한 경험적 연구는 주로 정적 그래프, 단일 스냅샷 또는 대규모 네트쿼그의 매우 작은 스냅샷에서 속성을 식별했기에...... (이유)

-> 시간경과에 따른 경향에 대한 진술로 전환!

present work : 1) Densification lows & 2) Shrinking diameters

여러 도메인의 다양한 네트워크 연구하며, 시간에 따른 근본적인 네트워크 속성 변화에 초점

Forest Fire Model

정교한 모델, 네트워크가 성장하면서, 밀도, 유효직경 감소가 동시에 보인다.

-> 기존방식에서 존재한 edges를 burning해 그 네트워크에 새로운 노드를 부착하는 방식!

-> 밀도화, 거리, degree distribution에 현실적 양상 보임! (우리가 원하는 것!)

초기 그래프 G , 새로운 노드를 V_1~V_k를 연결한ㄴ 결과 그래프 G final 이 다음 패턴 모두 준수하도록

v 를 G의 노드에 연속적으로 연결하는 단순 랜덤화 프로세스 설계

(다음 패턴 1. heavy tailed distributions for in, out degrees

2. densification power law

3. shrinking effective diameter)

begin with, some intution enderpinned CGA

-> 각 노드는 네트워크 일부분에 "Center of gravity"가짐,

다른 노드와 연결된 확률은 이 center of gravity로부터 거리에 따라 급격히 감소

+) 새로운 노드가 매우 많은 수의 아웃링크 생산

-> 더 왜곡된 out-degree distribution 야기

-> 지름 감소, 이전에 상이한 네트워크 부분을 연결하는 교량 역할

직관적 비유)

공식화하여 Forest Fire Model에 적용

• r : 인 링크 prob은 아웃 링크 prob보다 r배 적다.

따라서, Forest Fire Model의 링크 "burning"은 w에서 시작되어 w_1~w_x로 퍼지고, 소멸할 때까지 재귀적 반복

ex) 논문 참조,

v : 새로운 논문 저자

그 참조 부분집합 논문에 따라, w_1~w_x 답습 -> 이러한 논문에 대한 참조를 계속 축적

모델 특징)

특정 노드가 큰 "conflagration"(충돌) 일으켜, 많은 edges를 burning(퍼트리다)

-> 프로세스가 끝나기 전 많은 이웃링크 형성

1) heavy- tailed in-degrees

: 어느 노드(ambassador)에서 시작하든, 고도로 연결된 노드는 새 노드가 쉽게 도달 가능

2) communities

: "copying" 새 노드가 2ambassador 이웃 몇 모방하고, 반복

3) heavy-tailed out-degrees

: 링크 재귀적 형성 -> 새 노드가 많은 엣지 burn 가능 -> large out-degree

4) Densification power law

: 새 노드는 그 ambassador과 많은 연계 있을것, 멀리가면 link 감소

-> community guided attachment와 유사

5) Shrinking diameter

: 두 매개변수 p, r 변화 -> 밀도 (a>1)를 나타내는 그래프 만들 수 있다.

이 그림들을 보면, 앞쪽과 뒤로 타는 매개 변수에 따라 숲이 Fire Model은 희박하거나 밀도가 높은 그래프를 생성할 수 있으며, 증가하거나 감소하는 유효 직경을 가지고 있다.

안쪽과 바깥쪽 모두에 대해 두꺼운 꼬리를 나타낸다.

Microscopic Evolution of Networks

네트워크 거시적 속성 : 집합으로 이어지는 개별노드 arrival & edge 생성 과정에 대한 ㄱ연

최근, 복잡한 네트워크 진화에 매우 다양한 모델이 제안되었다.

-> 실제 데이터에서 관측된 통계적 네트워크 특성을 재현

(글로벌 네트워크 통계와 패턴 재현하는 충실도로 네트워크의 좋은 정도를 평가)

많은 경우, power law node degree 분포와 같은 글로벌 구조 초래하는 개별노드 동작을 정의하는데 목표

-> 가령 heavy-tailed degree distribution은 이런 관측을 초래하는 가장자리 생성 프로세스 가설을 만들었다. (저번에 배운 forest fire model 같은)

가장자리 생성 프로세스는 많다( cgg 등) 그러나 이 모두는 heavy- tailed degree distribution은 초래하지만,

그중 어느 것이 현실을 가장 잘 표현하는 지는 명확하지 않아......(한계)

-> 글로벌 네트워크 구조에만 초점 맞춘다음 관찰된 거시적 네트워크 구조를 어떤 종류의 미시적 노드 행동이 재현할 것인가에 대한 가설이 아니라

-> 직접 미시적 노드 동작에 초점을 맞춘다!!!

: 수백만 개의 개별 edge 도착 순서를 연구 -> 글로벌 네트워크 구조를 발생시키는 미세한 프로세스를 직접 평가하고 비

Microscopic Evolution

: 일련의 스냅샷을 사용해 패턴을 글로벌 규모로 고려했던 대형 네트워크 진화연구 (기존)

<-> 정확한 엣지 도착 시쿼스를 연구해, 글로벌 네트워크 패턴과 통계를 직접 담당하는 미세화된 네트워크 진화과정을 직접 관찰, 모델링이 가능하다!

Microscopic 진화의 2가지 의

의문 1. temporal network(특정시점의 네트워크)에서 어떻게 path 정의하고 walks ?

1) Temporal Path

엣지의 순서 (연결 루트?)

temporal path 효율적 ? -> shortest

1. TPSP-Dijkstra algorithm

의문 2. 네트워크 중심성 척도를 temporal network에도 어떻게 적용?

Temporal Centrality

그래프 이에서 중심성이란 그래에서 노드(node)의 상대적 중요성을 나타내는 척도이다.

Temporal Closeness: 네트워크 내 다른 노드들과 얼마나 가깝냐

-> 다른 모든 노드들과의 최단거리 합

Temporal PageRank

pagerank : 전체 그래프에서 각 노드의 중요도 알아냄

-> 시간적 요소 추가, 시간이 지나면 노드별 중요도가 바뀌지 않을가?

흐리멍텅한 엣지 (시간지나 사라진거)

a 노드!

-- 과거 : 연결된 엣지 많음 -> 중요한 노드

-- 현재 : a 와 연결된 엣지 많이 삭제 -> 중요도가 낮아졌다

Temporal Walk

Temporal pagerank & paths

시간이 지나면서 해당 노드와 연결된 확률 계산

|감마| = 해당 시점에서 가능한 모든 엣지의 수

베타는 0~1사이 확률이므로, 감마가 커지면 베타^감마는 작아짐.

-> 감마 커지면 (해당 시점에 갈 수 있는 엣지의 수가 많으면) transition prob은 줄어든다.

• path : 노드 연속 연결

• walk : 종횡무진 움직임 탐색

𝑡 → ∞로 가면, the temporal PageRank 정적 PageRank에 수렴한다.

Temporal PageRank is running regular PageRank on a time- augmented graph

As 𝑡 → ∞, 𝛽|tu | becomes the uniform distribution : 수렴 정적인 그래프가 된다 .