효율성(네트워크 과학)

네트워크 과학에서 네트워크의 효율은 얼마나 효율적으로 정보를 교환하는지를 나타내는 척도이며 통신 효율이라고도 합니다.기본적인 생각(및 주요 가정)은 네트워크 내에 있는2개의 노드가 멀어질수록 통신 효율이 떨어진다는 것입니다.효율의 개념은 네트워크의 로컬 및 글로벌 규모 모두에 적용할 수 있습니다.글로벌 규모로 효율성은 동시에 정보를 교환하는 네트워크 전체의 정보 교환을 수량화합니다.로컬 효율은 네트워크의 장애 저항성을 소규모로 수량화합니다. $노드$ 의 $로컬$ 효율은 노드 i가삭제되었을 때 네이버에 의해 정보가 얼마나 잘 교환되는지를 나타냅니다 $i$ .

정의.

통신 효율의 정의는 효율이 거리에 반비례한다고 가정합니다.따라서 수학적인 관점에서 보면

({displaystyle\ipsilon_{ij}=black{1}{d_{ij}}})

여기서 $\epsilon _{ij}$ $\epsilon _{ij}$ j \ $displaystyle _$ { $ij$ }는 $\epsilon _{ij}$ $G=(V,E)$ G $G=(V,E)$ ( $G=(V,E)$ , $G=(V,E)$ ) \ $displaystyle$ G = ( $V$ , $E$ ) \ $d_{ij}$ d $_$ { $ij$ }의 $i,j\in V$ $G=(V,E)$ $d_{ij}$ 노드 $i,j\in V$ i , $v$ V \ $displaystyle$ $i,j\in V$ i , j }의 쌍별 효율입니다.

$G$ 으로 네트워크 G $(\displaystyle$ G $)$ 의 $G$ 평균 통신 효율은 쌍별 ^[1]효율에 대한 평균으로 정의됩니다.

({displaystyle E(G)=paramfrac {1}{N(N-1)}}}\sum _{i\neq j\in V}{\frac {1}{d_{ij}}})

$N=|V|$ 서 N $N=|V|$ $displaystyle$ N= $V)$ 는 $N=|V|$ 네트워크 내의 노드 수를 나타냅니다.

거리는 네트워크의 유형에 따라 다양한 방법으로 측정할 수 있습니다.가중치 $없는$ 네트워크에서 가장 자연스러운 거리는 $i$ 와 $i$ $j$ $사이$ 의 최단 경로 길이입니다 $j$ 즉 $,$ i $사이$ 의 $i,j$ 최단 $경로$ 는 엣지 수가 최소인 경로이며 $엣지 수$ 는 엣지 길이입니다.i $i=j$ { $displaystyle$ i $=$ $j}$ 인 $i=j$ $i$ $d_{ij}=0$ $d_{ij}=0$ $=$ 0( $displaystyle d_{ij$ }= $0$ 입니다. 따라서 위의 합계가 i $i\neq j$ ({ $displaystyle$ i $\$ $neq$ j $j$ $j$ 에 있는 반면 $,$ i $=$ $displaystyle$ $di$ 를 $i$ 하는 경로가 없는 $d_{ij}=\infty$ di = $displaystyle$ displaystyle $diyle di$ 에 유의하십시오.효율은 제로입니다. $d_{ij}$ $({$ $displaystyle d_$ ${$ $ij})$ 는 $d_{ij}$ $i\neq j$ i $i\neq j$ $({displaystyle d_{ij}\geq$ $1$ )에 $d_{ij}\geq 1$ $i\neq j$ $d_{ij}$ 이므로 $(G)$ 는 $E(G)$ 0과 1 사이의 범위로 정규화된 기술자입니다.

가중치 네트워크

최단 패스 거리는 가중치 네트워크에도 일반화할 수 있습니다.단, 이 $d_{ij}^{W}\in [0,+\infty ]$ $d_{ij}^{W}\in [0,+\infty ]$ W $d_{ij}^{W}\in [0,+\infty ]$ [ $d_{ij}^{W}\in [0,+\infty ]$ , + $]{$ $displaystyle d_{ ij$ }^{ $W}\in [0,+\infty$ ]} 및 $d_{ij}^{W}\in [0,+\infty ]$ 다른 네트워크 간에 비교하기 위해서는 ^[2]^[3]평균 통신 효율을 적절히 정규화할 필요가 있습니다.

저자들은 E $)$ 를 $E(G)$ 할 것을 제안했다.\ $displaystyle$ E $(G)$ 는 $E(G)$ $네트워크$ G $(\displaystyle$ G $G$ 의 이상화된 버전의 효율로 나눈다.\displaystyle E(G)는 다음과 같다.

E_{\text{glob}}(G)=blac{E(G)}{E(G^{\text{ideal}}}}}}}.

$G^{\text{ideal}}$ ideal {\ $displaystyle$ G $^{\text$ ${$ $ideal}}$ 은 $G^{\text{ideal}}$ 가능한 모든 가장자리가 존재하는N개 $노드$ 에서의 $N$ "이상" 그래프입니다.무가중치인 경우, $G^{\text{ideal}}$ ideal {\ $E_{\text{glob}}(G)\in [0,1]$ G $^{\$ $text{ideal$ $}}}$ 은 $G^{\text{ideal}}$ clique, full network, $(G$ $E_{\text{glob}}(G)\in [0,1]$ ideal}) $= 1$ edge의 가중치가 부여되었을 때 (Globalization을 $E_{\text{glob}}(G)\in [0,1]$ 하기 위한) $E_{\text{glob}}(G)\in [0,1]$ 조건이다. $le$ $l_{ij}$ ${\text{glob}}(G)\in [0,1$ 은, 이 $l_{ij}$ $l_{ij}$ ({ $displaystyle l_{ij$ 라고 불리는 이상적인 네트워크내의 거리에 대해서, 다음과 같습니다.

(\displaystyle l_{ij}\leq d_{ij})

$i,j=1,...,N$ $i,j=1,...,N$ $i,j=1,...,N$ , $i,j=1,...,N$ . $i,j=1,...,N$ . , $i,j=1,...,N$ {\ $displaystyle$ i $,j=1$ , $...N$ . $l_{ij}$ $l_{ij}$ { $displaystyle l_{ij}}$ 의 $l_{ij}$ 경우 모든 노드 쌍에 대해 알고 있어야 합니다(및 0과 다름).일반적으로 공간 네트워크의^[2] 지리적 또는 물리적 거리로 간주하거나 모든 링크의 최대 비용으로 $l_{ij}={\frac {1}{w_{\max }}}$ 합니다( $l_{ij}={\frac {1}{w_{\max }}}$ : l $l_{ij}={\frac {1}{w_{\max }}}$ $l_{ij}={\frac {1}{w_{\max }}}$ $=$ 1 $w max$ { ij } $= displaystyle l_{\max }$ ）。여기서 w $w_{\max }$ ${\$ 에서는 $l_{ij}={\frac {1}{w_{\max }}}$ $w_{\max }$ ^[4]네트워크의 최대 상호 작용 $w_{\max }$ 를 나타냅니다.그러나 저자들은 이질적인 구조와 흐름에 의해 특징지어지는 실제 네트워크를 다룰 때 이러한 선택의 문제를 강조한다.예를 들어 l $l_{ij}={\frac {1}{w_{\max }}}$ j $=$ $l_{ij}={\frac {1}{w_{\max }}}$ $l_{ij}={\frac {1}{w_{\max }}}$ max ${\$ }= $flac {1}{w_{\max }}}}$ 를 $l_{ij}={\frac {1}{w_{\max }}}$ $l_{ij}={\frac {1}{w_{\max }}}$ 하면 글로벌 측정값이 가중치 분포에서 이상치에 매우 민감해지고 네트워크의 실제 효율성에 영향을 미치지 않는 경향이 있습니다.저자들은 또한 통계적으로 견고하고 물리적으로 근거가 있는 가장자리 가중치에 포함된 모든 정보(지리적 거리 등 기타 메타 데이터 없음)만을 $G^{\text{ideal}}$ 사용하여 G $G^{\text{ideal}}$ 을 $구축$ 하는 방법(\ $displaystyledisplaystyle$ G $^{\text{ideal}}.$

효율성 및 소규모 환경에서의 동작

네트워크의 글로벌 효율은 평균 경로 $길이$ L(\ $displaystyle$ L $)$ 이 $L$ 아니라 1 $(\displaystyle$ 1/ $L$ 에 상당합니다.중요한 차이점은 $1/L$ 1/ $(\$ $displaystyle$ $1/L$ 1/ $L)$ 은 $1/L$ 네트워크상에서 1개의 정보 패킷만 이동하는 시스템에서 효율을 측정하는 $1/L$ , $E_{\text{glob}}(G)$ $glob(G)$ 은 $E_{\text{glob}}(G)$ 모든 노드가 정보의 패킷을 교환하는 병렬 통신의 효율성을 측정하는 것입니다 $.$ 동시에 하고 있어요.

네트워크의 클러스터링 계수의 대안으로 쌍방향 통신 효율의 로컬 평균을 사용할 수 있다. $네트워크$ G $(\displaystyle$ G $)$ 의 $G$ 로컬 효율은 다음과 같이 정의됩니다.

({displaystyle E_{loc}(G,i)=sum frac {1}{N}}\sum _{i\in G}E(G_{i})

$G_{i}$ 서 $(\$ })는 $G_{i}$ $노드$ i(\ $displaystyle$ i $i$ 의 인접 노드만으로 구성된 로컬 서브그래프이며 $노드$ i(\ $displaystyle$ i $)$ 자체는 아닙니다 $i$ .

적용들

대략적으로 말하면, 네트워크의 효율은, 네트워크내의 작은 세계의 동작을 정량화하기 위해서 사용할 수 있습니다.효율은 가중 ^[2]및 비가중 네트워크에서 비용 효율적인 구조를 결정하기 위해서도 사용할 수 있습니다.네트워크 효율의 2가지 척도를 같은 규모의 랜덤네트워크와 비교하여 네트워크가 얼마나 경제적으로 구축되어 있는지를 확인합니다.또한 글로벌 효율은 상대적인 경로 ^[5]길이보다 수치적으로 사용하기 쉽습니다.

이러한 이유로 효율의 개념은 네트워크 ^[2]과학의 다양한 응용 분야에서 사용되어 왔습니다.^[6] 효율은 교통망이나 통신망과 같은 인공 네트워크의 분석에 유용하다.특정 네트워크 구성의 비용 효율과 폴트 톨러런스 정도를 판단하는 데 사용됩니다.이러한 네트워크에 대한 연구 결과, 이러한 네트워크는 글로벌 효율이 높은 경향이 있으며, 이는 자원을 적절하게 사용하지만 로컬 효율은 낮음을 의미합니다.이는 예를 들어, 지하철 네트워크가 폐쇄되지 않고, 네트워크 내의 특정 ^[1]회선이 다운된 경우에도 버스에 의해 승객을 재루팅할 수 있기 때문입니다.

인간이 구축한 네트워크를 넘어 물리적 생물학적 네트워크에 대해 이야기할 때 효율은 유용한 지표입니다.생물학의 어떤 측면에서도 자원의 부족이 중요한 역할을 하며, 생물학적 네트워크도 예외는 아닙니다.효율성은 신경과학에서 물리적 공간과 자원의 제약이 주요 ^[5]요소인 신경 네트워크 간의 정보 전송을 논하기 위해 사용됩니다.효율은 개미 군락 터널 시스템 연구에도 사용되어 왔는데, 개미 군락 터널 시스템은 대개 넓은 방뿐만 아니라 많은 널찍한 ^[7]터널로 구성되어 있습니다.군집의 큰 구조는 다양한 자원, 즉 ^[6]식량에 대한 운송 네트워크 역할을 해야 하기 때문에 개미 군집에 대한 이러한 적용은 그리 놀라운 일이 아니다.

레퍼런스

^ ^a ^b ^c ^d ^e Latora, Vito; Marchiori, Massimo (17 October 2001). "Efficient Behavior of Small-World Networks". Phys. Rev. Lett. 87 (19): 198701. arXiv:cond-mat/0101396. Bibcode:2001PhRvL..87s8701L. doi:10.1103/PhysRevLett.87.198701. PMID 11690461. S2CID 15457305.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ ^a ^b ^c ^d ^e ^f Latora, Vito; Marchiori, Massimo (March 2003). "Economic small-world behavior in weighted networks". The European Physical Journal B. 32 (2): 249–263. arXiv:cond-mat/0204089. Bibcode:2003EPJB...32..249L. doi:10.1140/epjb/e2003-00095-5. S2CID 15430987.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ ^a ^b Bertagnolli, Giulia; Gallotti, Riccardo; De Domenico, Manlio (June 2021). "Quantifying efficient information exchange in real network flows". Communications Physics. 4 (125): 125. arXiv:2003.11374. Bibcode:2021CmPhy...4..125B. doi:10.1038/s42005-021-00612-5. S2CID 214641335.
^ Rubinov, Mikail; Sporns, Olaf (2010). "Complex network measures of brain connectivity: uses and interpretations". NeuroImage. 52 (3): 1059–1069. doi:10.1016/j.neuroimage.2009.10.003. PMID 19819337. S2CID 1245121.
^ ^a ^b Bullmore, Ed; Sporns, Olaf (March 2009). "Complex brain networks graph theoretical analysis of structural and functional systems". Nature Reviews Neuroscience. 10 (3): 186–198. doi:10.1038/nrn2575. PMID 19190637. S2CID 205504722.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ ^a ^b Bocaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U. (February 2006). "Complex networks: Structure and dynamics". Physics Reports. 424 (4–5): 175–308. Bibcode:2006PhR...424..175B. CiteSeerX 10.1.1.408.2061. doi:10.1016/j.physrep.2005.10.009.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
^ Buhl, J.; Gautrais, J.; Solé, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (November 2002). "Efficiency and robustness in ant networks of galleries". The European Physical Journal B. 42 (1): 123–129. Bibcode:2004EPJB...42..123B. doi:10.1140/epjb/e2004-00364-9. S2CID 14975826.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[LatoraMarchiori2001-1] Latora, Vito; Marchiori, Massimo (17 October 2001). "Efficient Behavior of Small-World Networks". Phys. Rev. Lett. 87 (19): 198701. arXiv:cond-mat/0101396. Bibcode:2001PhRvL..87s8701L. doi:10.1103/PhysRevLett.87.198701. PMID 11690461. S2CID 15457305.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[LatoraMarchiori2002-2] ^ ^a ^b ^c ^d ^e ^f Latora, Vito; Marchiori, Massimo (March 2003). "Economic small-world behavior in weighted networks". The European Physical Journal B. 32 (2): 249–263. arXiv:cond-mat/0204089. Bibcode:2003EPJB...32..249L. doi:10.1140/epjb/e2003-00095-5. S2CID 15430987.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[Bertagnolli2021-3] Bertagnolli, Giulia; Gallotti, Riccardo; De Domenico, Manlio (June 2021). "Quantifying efficient information exchange in real network flows". Communications Physics. 4 (125): 125. arXiv:2003.11374. Bibcode:2021CmPhy...4..125B. doi:10.1038/s42005-021-00612-5. S2CID 214641335.

[RubinovSporns2010-4] Rubinov, Mikail; Sporns, Olaf (2010). "Complex network measures of brain connectivity: uses and interpretations". NeuroImage. 52 (3): 1059–1069. doi:10.1016/j.neuroimage.2009.10.003. PMID 19819337. S2CID 1245121.

[BullmoreSporns2009-5] Bullmore, Ed; Sporns, Olaf (March 2009). "Complex brain networks graph theoretical analysis of structural and functional systems". Nature Reviews Neuroscience. 10 (3): 186–198. doi:10.1038/nrn2575. PMID 19190637. S2CID 205504722.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[Bocaletti_et_al_2006-6] Bocaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U. (February 2006). "Complex networks: Structure and dynamics". Physics Reports. 424 (4–5): 175–308. Bibcode:2006PhR...424..175B. CiteSeerX 10.1.1.408.2061. doi:10.1016/j.physrep.2005.10.009.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[Buhl_et_al_2004-7] Buhl, J.; Gautrais, J.; Solé, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (November 2002). "Efficiency and robustness in ant networks of galleries". The European Physical Journal B. 42 (1): 123–129. Bibcode:2004EPJB...42..123B. doi:10.1140/epjb/e2004-00364-9. S2CID 14975826.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search

효율성(네트워크 과학)

네임스페이스

더

목차

정의.

가중치 네트워크

효율성 및 소규모 환경에서의 동작

적용들

레퍼런스