평균 경로 길이

평균 경로 길이는 네트워크 토폴로지에서 가능한 모든 네트워크 노드 쌍에 대해 최단 경로를 따라 가는 평균 단계 수로 정의되는 개념이다. 네트워크상에서 정보나 대량 수송의 효율을 측정하는 척도다.

개념

평균 경로 길이는 클러스터링 계수 및 정도 분포와 함께 네트워크 위상의 세 가지 가장 강력한 척도 중 하나이다. 예를 들어, 한 웹 사이트에서 다른 웹 사이트로 이동하는 평균 클릭 수 또는 평균적으로 완전히 낯선 사람에게 연락하기 위해 통신해야 하는 사람들의 수입니다. 가장 긴 지오데틱, 즉 네트워크의 어떤 두 노드 사이에 있는 가장 짧은 경로로 정의되는 네트워크의 직경과 혼동해서는 안 된다(그래프 이론 참조).

평균 경로 길이는 쉽게 협상할 수 있는 네트워크를 하나와 구별하는데, 이는 복잡하고 비효율적이며, 평균 경로 길이가 짧은 것이 더 바람직하다. 그러나 평균 경로 길이는 경로 길이와 같을 것이다. 네트워크 자체에는 매우 원격으로 연결된 노드와 서로 이웃인 많은 노드가 있을 수 있다.

정의

Consider an unweighted directed graph ${\displaystyle G}$ with the set of vertices ${\displaystyle V}$. Let ${\displaystyle d(v_{1},v_{2})}$, where ${\displaystyle v_{1},v_{2}\in V}$ denote the shortest distance between ${\displaystyle v_{1}}$ and ${\displaystyle v_2}$${\displaystyle v_{1$2}}: $1$에서 v 2 {\$displaystyle v_{$1}{1}에 도달할 수 없는$$ 경우$$ $d{\displaystyle ({v\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{v\mathrm{}}_{}}$2 )${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle d(v_{1$}, $v_{2}}}=0}$이라고 가정하십시오$.$ 평균 경로 길이 $l{\displaystyle {}_{}}$ ${\displaystyle G_{}}$ ${\$는 다음과 같다$$.

${\displaystyle l_{G}={\frac {1}{n\cdot(n-1)}\cdot \sum \sum _{i_}d(v_{i},v_{j}),}$

여기서 $n{\displaystyle }$ ${\displaystyle n}$은(는) $G{\displaystyle }$ ${\displaystyle G}$의 정점 수입니다$.$

적용들

인터넷과 같은 실제 네트워크에서, 짧은 평균 경로 길이는 정보의 빠른 전송을 촉진하고 비용을 절감한다. 대사 네트워크에서 대량 전달의 효율성은 평균 경로 길이를 연구함으로써 판단할 수 있다. 전력망 네트워크는 그것의 평균 경로 길이를 최소화한다면 손실이 적을 것이다.

대부분의 실제 네트워크는 매우 짧은 평균 경로 길이를 가지고 있어 모든 사람이 매우 짧은 경로를 통해 다른 모든 사람과 연결되는 작은 세계의 개념으로 이어진다.

결과적으로, 대부분의 실제 네트워크 모델은 이러한 조건을 염두에 두고 만들어진다. 실제 네트워크를 설명하려는 첫 번째 모델 중 하나는 랜덤 네트워크 모델이었다. 이후 와츠와 스트로가츠 모델이 뒤따랐고, 이후에도 BA 모델부터 시작하는 스케일 프리 네트워크가 있었다. 이 모든 모델들의 공통점은 매우 짧은 평균 경로 길이를 예측했다는 것이다. 일부 네트워크의 평균 경로 길이는 표에 나열되어 있다.^[1]

평균 경로 길이는 시스템 크기에 따라 다르지만 시스템 크기에 따라 크게 변경되지는 않는다. 소세계 네트워크 이론은 평균 경로 길이가 로그 n에 비례하여 변화한다고 예측한다. 여기서 n은 네트워크의 노드 수입니다.

참조