바라바시-알베르트 모델

분류:네트워크 이론
네트워크 과학
이론
그래프 복잡계 네트워크 복잡한 전염 작은 세상 네트워크 척도 없는 네트워크 군집구조 퍼컬레이션 이론 진화 망 그래프 그리기 사회 자본 링크 분석 조합 최적화 삼각 폐쇄 동종애 추이적 관계 네트워크 효과 사회 영향
네트워크 유형
정보 (컴퓨팅) 통신 사회 생물 시맨틱 흐름 온칩
그래프
특징 클릭 순환 자료 구조 경로 꼭짓점 인접 리스트 / 행렬 유형 이분 완전 유향 초 다중 가중
측정항목 알고리즘
중심성 거리
모델
토폴로지 바라바시-알베르트 동역학 행위자 기반
목록 분류
분류:네트워크 이론 분류:그래프 이론
v t e

바라바시-알베르트 모델(Barabási–Albert, BA) 모델은 선호적 연결(preferential attachment) 메커니즘을 이용해 무작위 척도 없는 네트워크를 생성하는 알고리즘이다.

인터넷, 월드 와이드 웹, 인용 네트워크, 일부 사회 관계망 등 여러 자연적·인공적 시스템은 대체로 척도 없는 구조를 가지며, 네트워크 내 다른 노드들에 비해 비정상적으로 높은 연결 수(차수)를 지닌 소수의 노드(허브)를 포함하고 있는 것이 특징이다.

BA 모델은 실제 네트워크에서 이러한 허브가 등장하는 현상을 설명하기 위해 고안되었다.

이 알고리즘의 이름은 이를 제안한 알베르트라슬로 바라버시(Albert-László Barabási)와 레카 알베르트(Réka Albert)의 이름에서 유래되었다.

많은 실제 네트워크는 척도 없는 네트워크(scale-free network)의 특성을 (적어도 근사적으로) 보인다. 척도 없는 네트워크란 노드의 연결 수(차수)가 멱함수(power-law) 분포를 따르는 네트워크를 말한다. 반면, Erdős–Rényi(ER) 모델이나 Watts–Strogatz(WS) 모델 같은 무작위 그래프 모델은 이러한 멱함수 분포를 보이지 않는다.

Barabási–Albert(BA) 모델은 이러한 척도 없는 네트워크를 생성하기 위한 여러 모델 중 하나로, 다음의 두 가지 핵심 개념을 바탕으로 한다: 성장(growth)과 선호적 연결(preferential attachment). 이 두 개념은 실제 네트워크에서 매우 보편적으로 관찰된다.

성장(Growth):

네트워크의 노드 수가 시간에 따라 증가한다는 의미이다. 새로운 노드들이 지속적으로 추가되는 동적인 시스템을 가정한다.

선호적 연결(Preferential Attachment):

기존에 더 많은 연결을 보유한 노드는 새로운 노드가 연결될 확률이 더 높다. 다시 말해, 차수가 높을수록 더 많은 연결을 획득할 가능성이 크다.

이 개념은 사회적 네트워크로 비유하면 직관적으로 이해할 수 있다. 예를 들어, 어떤 사람이 새롭게 공동체에 들어왔을 때, 대부분의 경우 이름도 낯설고 잘 알려지지 않은 사람보다 이미 많은 사람과 관계를 맺고 있는 유명인사와 더 쉽게 연결된다.

월드 와이드 웹(World Wide Web)에서도 이와 유사한 현상이 관찰된다. 새로운 웹페이지가 생길 때, 잘 알려지지 않은 페이지보다는 구글 같은 유명한 허브 사이트에 링크를 거는 경향이 있다는 것이다.

만약 누군가 기존 링크 중 하나를 무작위로 선택해서 새로운 페이지를 연결한다고 가정하면, 이 링크가 가리키는 페이지는 차수가 높을수록 선택될 확률이 높아진다.

BA 모델은 바로 이 점을 바탕으로 선호적 연결의 확률 규칙을 설명한다.

이후에는 Bianconi–Barabási 모델이 이를 확장하여 각 노드에 "적합도(fitness)" 파라미터를 도입함으로써 보다 다양한 상황을 설명하려 한다.

선호적 연결은 일종의 양의 피드백 사이클(positive feedback cycle)이다. 초기에는 아주 작은 차이(예: 더 빨리 등장한 노드, 초기에 더 많은 연결을 가진 노드)였지만, 이 차이가 시간이 지날수록 자동적으로 증폭된다.

이러한 현상은 "부익부 현상(the rich get richer)", 혹은 매튜 효과(Matthew effect)라고도 불리며, 생화학에서의 자동촉매(autocatalysis)와 유사한 원리로 설명되기도 한다.

BA 모델의 유일한 매개변수는 다음과 같다. ${\displaystyle m}$, 양의 정수. 네트워크는 네트워크로 초기화된다. ${\displaystyle m_{0}\geq m}$ 노드. (The only parameter in the BA model is ${\displaystyle m}$, a positive integer. The network initializes with a network of ${\displaystyle m_{0}\geq m}$ nodes.)

각 단계에서는 새로운 노드를 하나 추가하고, 기존 네트워크 내의 노드들 중에서 𝑚개의 이웃 노드를 선택하여 연결한다.

이때, 기존 노드가 선택될 확률은 그 노드가 가진 연결 수(차수)에 비례하여 결정된다.

(참고: 원 논문에서는 동일한 노드가 여러 번 선택될 경우를 어떻게 처리할지에 대해서는 명시하지 않았다.)

형식적으로, 새 노드가 기존의 노드 𝑖에 연결될 확률 𝑝ᵢ는 다음과 같이 정의된다:

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

여기서

• 𝑘ᵢ는 노드 𝑖의 차수(연결 수)이며,
• Σ𝑗𝑘𝑗는 네트워크 내 모든 기존 노드 𝑗의 차수를 더한 값이다. 이는 현재 네트워크 내의 전체 간선 수의 두 배와 같다는 점에서, 각 노드는 그 상대적인 중요도에 따라 연결 기회를 얻게 된다.

이 과정을 실제로 구현할 때는 임의의 간선 하나를 균등하게 선택한 후, 그 간선에 연결된 두 노드 중 하나를 다시 임의로 선택하는 방식으로 수행할 수 있다. 이 방식은 확률이 각 노드의 차수에 비례하도록 보장한다.

이러한 메커니즘의 결과로, 허브(hub)로 불리는 고차수 노드는 새로운 링크를 빠르게 더 많이 확보하게 된다. 반면, 연결 수가 적은 노드는 새로운 링크 대상이 될 가능성이 낮아진다.

즉, 새로운 노드들은 이미 연결이 많이 되어 있는 허브 노드에 더 ‘선호적으로’ 연결되는 경향을 보이며, 이는 네트워크 내 양극화를 심화시키는 양의 피드백 구조를 만들어낸다.

BA 모델로부터 생성된 차수 분포는 척도 없는(scale-free) 특성을 가지며, 특히 다음과 같은 형태의 멱함수(power law)를 따른다:

${\displaystyle P(k)\sim k^{-3}\,}$

h-지수 또는 Hirsch 지수 분포 또한 척도 없는 성질을 보이는 것으로 밝혀졌으며, 이는 중심성 척도(centrality measure)로 활용하기 위해 로비 지수(lobby index)라는 이름으로 제안되었다^[1].

${\displaystyle H(k)\sim k^{-6}\,}$

또한, 초기 연결 차수가 ${\displaystyle m_{0}=1}$인 경우에는 h-지수(h-index)가 1인 노드들의 밀도(density)에 대한 해석적인 결과(analytic result)를 도출할 수 있다.

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

BA 모델에서는 네트워크가 진화하는 방식 때문에 연결된 노드의 차수 간 상관관계가 자연스럽게 발생한다. 확률은, ${\displaystyle n_{k\ell }}$, 차수의 노드를 연결하는 링크를 찾는 것 ${\displaystyle k}$ 차수의 조상 노드로 ${\displaystyle \ell }$ 특수한 경우의 BA 모델에서 ${\displaystyle m=1}$ (BA 트리)는 다음과 같이 주어진다.

${\displaystyle n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.}$

이는 분포가 상관관계가 없다면 다음과 같은 결과를 얻을 수 있으므로 차수 상관관계의 존재를 확인한다. ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$ .^[2]

일반용 ${\displaystyle m}$, 차수 노드를 연결하는 링크의 분수 ${\displaystyle k}$ 차수의 노드로 ${\displaystyle \ell }$^[3] 이다

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

또한, 최근접 이웃 차수 분포 ${\displaystyle p(\ell \mid k)}$ 즉, 차수가 있는 노드의 이웃들의 차수 분포이다. ${\displaystyle k}$,^[3] 로 주어진다.

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

즉, 차수가 있는 노드를 선택하면 ${\displaystyle k}$ 그리고 이웃 중 하나를 무작위로 선택하면 이 무작위로 선택된 이웃이 차수를 가질 확률은 ${\displaystyle \ell }$ 다음 표현식으로 주어진다 ${\displaystyle p(\ell |k)}$ 위에.

에 대한 사례 ${\displaystyle m=1}$ 간단한 문제이다. 네트워크는 트리이고 클러스터링 계수는 0이다. BA 모델의 클러스터링 계수 에 대한 분석 결과는 Klemm과 Eguíluz^[4]에 의해 얻어졌고 Bollobás^[5]에 의해 증명되었다. Fronczak, Fronczak 및 Holyst는 클러스터링 계수를 연구하기 위해 평균장 접근 방식을 적용했다.^[6]

Barabási–Albert 모델의 평균 클러스터링 계수는 네트워크 N의 크기에 따라 달라진다.

${\displaystyle \langle C\rangle \sim lnN^{2}/N.}$

이러한 동작은 클러스터링이 시스템 크기에 관계없이 이루어지는 소규모 네트워크의 동작과는 다르다.

노드 차수에 따른 클러스터링 ${\displaystyle C(k)}$ 실질적으로 독립적이다 ${\displaystyle k}$ .^[6]

BA 모델의 스펙트럼 밀도는 무작위 그래프의 반원형 스펙트럼 밀도와 다른 모양을 갖는다. 반원보다 훨씬 위에 꼭대기가 있는 삼각형 모양이며 가장자리는 거듭제곱 법칙에 따라 감소한다.^[7][8] (5.1절)에서는 스펙트럼 밀도의 모멘트를 거듭제곱 지수의 함수로 분석하여 이 스펙트럼 밀도의 모양이 정확한 삼각 함수가 아님을 증명했다.

정의에 따르면 BA 모델은 시간에 따라 발전하는 현상을 설명하므로 척도 없는 속성 외에도 동적 척도 속성을 찾아볼 수도 있다. BA 네트워크 노드는 일반화된 정도로도 특징지어질 수 있다. ${\displaystyle q}$, 각 노드의 출생 시간의 제곱근과 해당 차수의 곱 ${\displaystyle k}$, 학위 대신에 ${\displaystyle k}$ BA 네트워크에서는 출생 이후부터 혼자 있는 것이 중요하다. 우리는 일반화된 차수 분포를 발견한다. ${\displaystyle F(q,t)}$ 몇 가지 중요한 기능이 있으며 동적 확장을 보여준다.

${\displaystyle F(q,t)\sim t^{-1/2}\phi (q/t^{1/2}).}$

이는 다음과 같은 뚜렷한 플롯을 의미한다. ${\displaystyle F(q,t)}$ 대 ${\displaystyle q}$ 우리가 그래프를 그리면 보편적인 곡선으로 붕괴될 것이다. ${\displaystyle F(q,t)t^{1/2}}$ 대 ${\displaystyle q/t^{1/2}}$ .

모델 A는 성장을 유지하지만 우선적 부착은 포함하지 않는다. 새로운 노드가 기존 노드에 연결될 확률은 같다. 이 한계에서 결과적인 차수 분포는 기하학적이며^[9] 성장만으로는 척도 없는 구조를 생성하는 데 충분하지 않음을 나타낸다.

모델 B는 우선적 애착을 유지하지만 성장은 없다. 이 모델은 고정된 수의 연결이 끊긴 노드로 시작하여 링크를 추가하며, 우선적으로 높은 차수의 노드를 링크 대상으로 선택한다. 시뮬레이션 초기에는 차수 분포가 척도가 없는 것처럼 보이지만 분포 자체는 안정적이지 않으며 네트워크가 포화 상태에 가까워질수록 결국 가우시안에 가까워진다. 따라서 선호적 애착만으로는 척도가 없는 구조를 만들어내기에 충분하지 않는다.

모델 A와 B가 척도 없는 분포를 유도하지 못한 것은 실제 네트워크에서 관찰되는 정상 전력 법칙 분포를 재생산하기 위해서는 성장과 우선적 연결이 동시에 필요하다는 것을 나타낸다.^[2]

BA 모델은 보다 일반적인 비선형 선호 애착(NLPA) 모델의 특정 사례로 생각할 수 있다.^[10] NLPA 알고리즘은 첨부 확률이 보다 일반적인 형태로 대체된 BA 모델과 동일하다.

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}},}$

어디 ${\displaystyle \alpha }$ 는 상수 양의 지수이다. 만약에 ${\displaystyle \alpha =1}$ NLPA는 BA 모델로 축소되며 "선형"이라고 한다. 만약에 ${\displaystyle 0<\alpha <1}$ NLPA는 "준선형"으로 불리며, 네트워크의 차수 분포는 늘어난 지수 분포를 따르는 경향이 있다. 만약에 ${\displaystyle \alpha >1}$ NLPA는 "초선형"이라고 하며, 소수의 노드가 네트워크의 거의 모든 다른 노드에 연결된다. 두 가지 모두에 대해 ${\displaystyle \alpha <1}$ 그리고 ${\displaystyle \alpha >1}$ 네트워크의 척도 없는 속성은 무한한 시스템 크기의 한계에서 깨진다. 그러나 만약 ${\displaystyle \alpha }$ 단지 약간 더 크다 ${\displaystyle 1}$ NLPA는 일시적으로 척도가 없는 것처럼 보이는 차수 분포를 초래할 수 있다.^[11]

선호적 애착은 1923년 헝가리 수학자 György Pólya의 유명한 항아리 모델에서 처음 등장했다.^[12] 더욱 투명한 도출을 제공하는 마스터 방정식 방법은 1955년 Herbert A. Simon에 의해 도시 규모 및 기타 현상에 대한 연구 과정에서 적용되었다^[13] . 이것은 1976년 Derek de Solla Price 에 의해 인용 빈도를 설명하기 위해 처음 적용되었다.^[14] 프라이스는 과학 논문의 인용이 누적되는 데 관심이 있었고, 프라이스 모델은 '누적 이점'(특정 애착에 대한 그의 이름)을 사용하여 뚱뚱한 꼬리 분포를 생성했다. 현대 인용 네트워크의 언어로 말하면, Price의 모델은 지향성 네트워크, 즉 Barabási-Albert 모델의 버전을 생성한다. "선호적 애착"이라는 이름과 현재 척도 없는 네트워크 모델의 인기는 Albert-László Barabási 와 Réka Albert 의 작업 덕분이다. 이들은 실제 네트워크에서도 유사한 프로세스가 존재한다는 사실을 발견했고 1999년에 웹에서 수치적으로 관찰된 차수 분포를 설명하기 위해 선호적 애착을 적용했다.^[15]

• 비안코니-바라바시 모델
• 중국 음식점 프로세스
• 복잡한 네트워크
• 에르되시-레니(ER) 모델
• Price의 모델
• 침투 이론
• 척도 없는 네트워크
• 소규모 세계 네트워크
• 왓츠와 스트로가츠 모델

• "이 남자는 세상을 지배할 수 있다"
• "Barabási–Albert를 위한 Java 구현"
• "코드에서 Barabási–Albert 모델 그래프 생성"