[Graph Theory] 작은 세상 네트워크 (Small World Network)

작은 세상 네트워크 (Small World Network)

 

 

작은 세상 네트워크는 대부분의 노드가 서로의 이웃이 아니지만 주어진 노드의 이웃이 서로의 이웃일 가능성이 있는 수학적 그래프이다. 이로 인해 대부분의 인접 노드는 적은 수의 홉 또는 단계로 다른 모든 노드에서 도달할 수 있다. 특히, small-world 네트워크는 무작위로 선택된 두 노드 사이의 일반적인 거리 L (필요한 단계 수)이 네트워크의 노드 수 N의 로그 에 비례하여 증가하는 네트워크로 정의된다.

 

글로벌 클러스터링 계수는 작지 않다. 소셜 네트워크의 맥락에서 이것은 낯선 사람들이 짧은 지인 사슬로 연결되는 작은 세계 현상을 초래한다. 소셜 네트워크 , Wikipedia와 같은 위키, 유전자 네트워크 , 심지어 인터넷 의 기본 아키텍처를 포함한 많은 경험적 그래프는 작은 세계 효과를 보여준다. 그것은 현대 컴퓨터 하드웨어의 많은 네트워크 온 칩 아키텍처에 대한 영감이다.

 

작은 세계 네트워크의 특정 범주는 1998년 Duncan Watts 와 Steven Strogatz에 의해 무작위 그래프 클래스로 식별되었다. 노드간 거리 (평균 최단 경로 길이 라고도 함)는 Erdős–Rényi (ER) 모델에 따라 구축된 순전히 무작위 그래프, 작은 클러스터링 계수와 함께 작은 평균 최단 경로 길이 (일반적으로 노드 수의 로그로 변함)를 나타낸다. Watts와 Strogatz는 실제로 많은 실제 네트워크가 평균 최단 경로 길이가 짧지만 클러스터링 계수가 무작위로 예상한 것보다 훨씬 높다는 것을 측정했다. 그런 다음 Watts와 Strogatz 는 (i) 평균 최단 경로 길이가 작고 (ii) 클러스터링 계수가 큰 새로운 그래프 모델을 제안했다. 현재 Watts and Strogatz 모델이라고 한다. 격자와 같은 "큰 세계"와 작은 세계 사이의 Watts-Strogatz 모델의 교차는 1999년 Barthelemy와 Amaral에 의해 처음 설명되었다.

 

작은 세상 네트워크 계수 (Small World Network Coefficient)

 

특성 경로 길이 L 및 클러스터링 C가 있는 그래프가 주어지면 작은 세상 계수 ω는 네트워크의 클러스터링을 등가 격자 (equivalent lattice) 네트워크 Clatt와 등가 랜덤 네트워크 Lrand 관계는 클러스터링과 비교 하고 경로 길이를 비교하여 정의된다. 단순히 정의된 두 비율의 차이이다.

 

 

랜덤 네트워크가 아닌 동등한 격자 네트워크의 클러스터링을 사용하는 경우 이 메트릭은 C and에서 나타나는 변동에 덜 민감하다. 또한, ω의 값은 네트워크 크기에 관계없이 간격이 -1에서 1로 제한된다. ω가 0에 가까운 L ≈ L rand 및 C ≈ Clatt의 조건에서 0에 가까운 값은 작은 세상으로 간주된다.  L ≈ L rand 및 C ≪ C latt 조건에서 ω 양수 값은 보다 무작위적인 특성이 있는 그래프를 나타낸다. L ≫ Lrand, C ≈ Clatt의 조건에서 ω 음수 값은 더 규칙적이거나 격자와 같은 특성을 가진 그래프를 나타낸다.

 

정규적 네트워크 (Regular Network)

 

https://link.springer.com/article/10.1007/s11067-018-9417-y

 

정규적 네트워크 (regular network)에서 무작위로 몇 개의 연결만 추가한 것이다. 무작위성 (randomness)의 측면에서 볼 때 완전히 규칙적이지도, 완전히 무작위적이지도 않은 중간에 있다고 할 수 있다. 그리고 이 소수의 무작위 연결의 추가만으로 네트워크는 급격하게 좁아진다. 모든 노드들 간의 연결단계가 급속하게 줄어든다는 것이다.

 

https://www.nature.com/articles/30918

 

작은 세상 네트워크가 생성되는 과정은 Watts-Strogatz Procedure라고 부른다. 이 알고리즘은 k-regular network를 small world network로 만든다. small world network은 주어진 k-regular network에서 임의의 개수 edge를 random하게 rewire를 시킴으로써 얻을 수 있다. 즉, 임의로 regualr network에서 p의 확률로 하나의 edge를 random한 edge로 바꿔주는 과정을 계속 반복하기만 하면 된다. 이 과정을 통해 regular network에 강제적으로 randomness를 주입할 수 있게 되며 p가 약 1 ~ 4%가 되면 small-world effect가 나타난다. 여기서 p 값이 0.01 ~ 0.04일 때 transition threshold 혹은 crossover point라고 한다.

 

작은 세상 네트워크의 속성 (small-worldness)은 네트워크의 거시적 특성을 보여주는 중요한 정량적 지표로 사용된다. 주변 노드들과 클러스터링을 이루면서도 (regular network의 특성) 네트워크 내에서 거리가 좁은 (random network의 특성) 특성을 모두 가지는 네트워크는 global efficiency와 local efficiency가 모두 좋다고 할 수 있다. 하지만 이런 특성을 갖는 현실 세계의 다양한 네트워크들은 다른 모양을 하고 있음이 밝혀졌다.

 

https://en.wikipedia.org/wiki/Small-world_network

Small-world network - Wikipedia