침투 이론
Percolation theory시리즈의 일부 | ||||
네트워크 과학 | ||||
---|---|---|---|---|
네트워크 타입 | ||||
그래프 | ||||
| ||||
모델 | ||||
| ||||
| ||||
통계물리학과 수학에서 침투 이론은 노드나 링크가 추가되었을 때 네트워크의 동작을 기술합니다.이는 기하학적 위상전이의 유형으로, 접속이 끊긴 소규모 클러스터 네트워크가 매우 큰 규모의 접속 클러스터로 병합되기 때문에 이른바 스패닝 클러스터라고 불립니다.재료 과학 및 다른 많은 분야에 대한 침투 이론의 적용은 여기에서 그리고 기사 네트워크 이론과 침투에서 논의된다.
서론
대표적인 질문(및 이름의 출처)은 다음과 같습니다.다공질 재료 위에 액체를 붓는다고 가정합니다.액체가 구멍에서 구멍으로 흘러나와 바닥에 닿을 수 있을까요?이 물리적 질문은 n × n × n 정점의 3차원 네트워크로 수학적으로 모델링되며, 일반적으로 "사이트"라고 불린다. 여기서 각 인접국 사이의 가장자리 또는 "결합"은 확률 p로 개방되거나 확률 1 – p로 폐쇄될 수 있으며, 이들은 독립적이라고 가정한다.따라서, 주어진 p에 대해, 열린 경로(각 링크가 "열린" 결합인 경로를 의미)가 위에서 아래로 존재할 확률은 얼마나 됩니까?큰n 의 동작이 주된 관심사입니다.지금은 결합 침투라고 불리는 이 문제는 Broadbent & Hammersley(1957)[1]에 의해 수학 문헌에 소개되었고, 그 이후로 수학자들과 물리학자들에 의해 집중적으로 연구되어 왔다.
랜덤 그래프를 얻기 위한 약간 다른 수학 모델에서 사이트는 확률 p 또는 확률 1 – p의 "빈" (이 경우 가장자리가 제거됨)로 "점유"된다. 이에 해당하는 문제를 사이트 침투라고 한다.같은 질문입니다.특정 p에 대해 상단과 하단의 사이에 패스가 존재할 확률은 얼마나 됩니까?마찬가지로, 연결된 그래프가 어떤 부분 1 – p의 기능 상실을 나타내면 그래프가 연결이 끊어질지 물어볼 수 있습니다(큰 구성요소는 없음).
격자 치수에 대해서도 같은 질문을 할 수 있다.매우 일반적인 것처럼 실제로는 대규모 네트워크보다 무한 네트워크를 조사하는 것이 더 쉽습니다.이 경우 이에 대응하는 질문은 무한 산개 클러스터가 존재하는가 하는 것입니다.즉, 네트워크를 통과하는 무한 길이의 접속 포인트의 경로가 있습니까?콜모고로프의 0-1 법칙에 따르면 주어진 p에 대해 무한 군집이 존재할 확률은 0이거나 1입니다.이 확률은 p(결합 인수에 의한 증명)의 증가 함수이므로 확률이 항상 0이고 확률이 항상 1인 임계 p(p로 표시c)가 있어야 합니다.실제로 이 중요도는 매우 쉽게 관찰할 수 있습니다.100보다 작은 n개라도 p 값의 짧은 범위 내에서 정상에서 하단으로의 개방 경로 확률은 0에 매우 가깝고 1에 매우 가까운 확률로 급격히 증가한다.
역사
Flory-Stockmayer 이론은 침투 [2]과정을 조사하는 최초의 이론이었다.
우리가 알고 있는 침투 모델의 역사는 석탄 산업에 뿌리를 두고 있다.산업 혁명 이후, 이 에너지원의 경제적 중요성은 그 구성을 이해하고 그 사용을 최적화하기 위해 많은 과학적 연구를 촉진시켰다.30~40년대 유기화학에 의한 정성분석은 양적 연구의 여지를 점점 더 많이 남겼다.[3]
이러한 맥락에서 1938년 영국 석탄 이용 연구 협회(BCURA)가 창설되었다.탄광 소유주들이 자금을 댄 연구회입니다.1942년 로잘린드 프랭클린은 캠브리지 대학에서 화학을 전공했고, BCURA에 합류했다.그녀는 석탄의 밀도와 다공성에 대한 연구를 시작했다.2차 세계대전 동안 석탄은 중요한 전략적 자원이었다.그것은 에너지원으로 사용되었지만, 방독면의 주요 성분이기도 했다.
석탄은 다공질 매체이다.그것의 '실제' 밀도를 측정하기 위해, 한 가지는 미세한 구멍을 채울 수 있을 정도로 분자가 작은 기체의 액체에 그것을 가라앉히는 것이었다.로잘린드 프랭클린은 여러 가스(헬륨, 메탄올, 헥산, 벤젠)를 이용해 석탄의 밀도를 측정하려다 사용된 가스에 따라 다른 값을 찾으면서 석탄의 기공이 미세한 체 역할을 하는 다양한 길이의 미세구조로 만들어졌다는 것을 보여줬다.그녀는 또한 이 구조물들의 크기가 석탄 생산 중 탄산화 온도에 따라 달라진다는 것을 발견했다.이러한 연구로, 그녀는 박사 학위를 취득했고 1946년에 BCURA를 떠났다.[4]
50년대 중반 Simon Broadbent는 BCURA에서 통계학자로 일했다.다른 관심사들 중에서, 그는 방독면에 석탄을 사용하는 것을 연구했다.한 가지 질문은 어떻게 유체가 석탄 기공에서 확산될 수 있는지 이해하는 것입니다. 개방 또는 폐쇄된 터널의 무작위 미로처럼 모델링됩니다.1954년 몬테카를로 방법에 대한 심포지엄에서 그는 존 해머슬리에게 이 모델을 분석하기 위한 수치적 방법의 사용에 대한 질문을 던졌다.[5]
Broadbent와 Hammersley는 1957년 그들의 기사에서 이 현상을 모델링하기 위한 수학적 모델인 침투(percolation)를 소개했다.
중요 파라미터의 계산
대부분의 무한 격자 그래프의 경우 p를 정확하게 계산할 수 없습니다c. 그러나c 경우에 따라 p는 정확한 값이 있습니다.예를 들어 다음과 같습니다.
- 2차원, pc).mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-outp에 사각형의 격자 ℤ2.결합 여과에다고.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}1/2 사실을 20여년간 미해결의 문제와 결국 해리의 작가.에 의해 초기 1980s,[6]에 해결되었다의 작가.(1982년)참조하십시오.현장 침투의 경우 p의c 값은 분석적 도출에서 알 수 없으며 큰 [7]격자의 시뮬레이션을 통해서만 알 수 있다.
- 고차원 격자에 대한 리미트 케이스는 배위수 z에 대해 역치가 p=1/z~1인c 베테 격자에 의해 주어진다.즉 일반 인 z(\ z의 경우 c는 1/ (z - 1 입니다.
- 정도 상관관계가 없는 임의의 트리형 네트워크에 대해서는 그러한 네트워크가 거대한 컴포넌트를 가질 수 있음을 알 수 있으며 침투 임계값(전송 확률)은 p 1 (1 }= frac 1}'( 서 로 지정된다.과도한 정도 분포에 대응하는 정격 함수.즉, 도「k k의 랜덤 Erd's-Rényi 네트워크의 경우c p = 1/displayk.[8][9][10]
- 저클러스터링에서는 임계점은 다음과 같이 (-) - (1 - C )^{ - 1(1 - -) 됩니다.
이는 일정 정도의 분포에서는 클러스터링이 침투 임계값을 크게 하는 것을 나타냅니다.이는 주로 고정된 수의 링크에서는 클러스터 구조가 글로벌 접속을 희석시키는 가격으로 네트워크의 핵심을 보강하기 때문입니다.클러스터링이 높은 네트워크에서는 강력한 클러스터링을 통해 코어 주변 구조가 유도될 수 있습니다.코어와 페리페럴은 다른 크리티컬포인트로 침투할 수 있기 때문에 위의 대략적인 처리는 [12]적용되지 않습니다.
유니버설리티
보편성 원칙은 p의 수치c 값이 그래프의 국소 구조에 의해 결정되는 반면, 임계 임계값 pc 근처의 동작은 보편적 임계 지수에 의해 특징지어진다고 말한다.예를 들어, 임계 상태의 군집 크기 분포는 모든 2D 격자에 대해 동일한 지수를 갖는 멱함수로 감소합니다.이 보편성은 주어진 차원, 다양한 임계 지수에 대해 p에서 클러스터의c 프랙탈 치수가 격자 유형과 침투 유형(예: 결합 또는 현장)과 독립적이라는 것을 의미한다.그러나 최근 가중 평면 확률 격자(WPSL)에서 침투가 수행되었고 WPSL의 치수가 포함된 공간의 치수와 일치하지만 보편성 클래스는 알려진 모든 평면 [13][14]격자의 치수와 다르다는 것을 발견했다.
단계
미임계 및 초임계
아임계 단계의 주요 사실은 "지수적 붕괴"입니다.즉, p < p일c 때, 특정 점(예를 들어 원점)이 r크기의 오픈 클러스터(그래프의 "오픈" 에지의 최대 연결 세트)에 포함될 확률은 r에서 지수적으로 0으로 감소한다.이것은 멘시코프(1986년)와 아이젠만 & 바르스키(1987년)에 의해 독립적으로 3차원 이상의 침투로 증명되었다.2차원에서, 그것은 p =[15] 1/2라는c 케스텐의 증명의 일부를 형성했다.
정사각형 격자2 δ의 이중 그래프는 정사각형 격자이기도 합니다.따라서 2차원에서 초임계 단계는 아임계 침투 프로세스와 이중적입니다.이는 기본적으로 d = 2인 초임계 모델에 대한 전체 정보를 제공합니다.3차원 이상의 초임계 단계에 대한 주요 결과는 충분히 큰 N에 대해 2차원 슬래브 δ2 × [0, N]d − 2에 무한 개방 클러스터가 있다는[clarification needed] 것이다.이것은 그림메트와 마스트랜드(1990)[16]에 의해 증명되었다.
p < 1/2의 2차원에서는 1의 확률로 고유한 무한 닫힌 클러스터가 존재합니다(닫힌 클러스터는 그래프의 "닫힌" 모서리의 최대 연결 집합입니다).따라서 아임계 단계는 무한 폐쇄 대양의 유한 개방 섬이라고 할 수 있다.p > 1/2 이면 무한대양에 유한하게 닫힌 섬이 있는 경우는 정반대입니다.그림은 p < 1/2 이후 d 3 3일 때 더c 복잡하며 p와 1 - p 사이에c p에c 대해 무한 개방 클러스터와 폐쇄 클러스터가 공존한다.
중요도
침투는 임계점 p = p에서c 특이점을 가지며, p- c c c {\c의 멱함수로 동작한다. 스케일링 이론은 특이점의 등급을 결정하는 임계 지수의 존재를 예측한다.d = 2일 때, 이러한 예측은 등각장 이론과 슈람-뢰너 진화의 논거에 의해 뒷받침되며, 지수에 대한 예측 수치들을 포함한다.이러한 예측의 대부분은 d 차원수가 d = 2 또는 d 6 6을 만족하는 경우를 제외하고 추측에 불과하다.다음과 같은 것이 있습니다.
- 무한 클러스터가 없습니다(열린 클러스터 또는 닫힌 클러스터).
- 특정 고정점(원점 등)에서 r의 거리까지 열린 경로가 있을 확률은 다항식으로 감소한다. 즉, 일부 α에 대해 r의α 차수이다.
- α는 선택된 특정 격자 또는 다른 국소 매개변수에 의존하지 않는다.이는 차원 d에만 의존합니다(이것은 보편성 원리의 인스턴스입니다).
- α는d d = 2에서 d = 6까지 감소하다가 고정 상태를 유지한다.
- α2 = -5/48
- α6 = -1.
- 2차원에서 큰 군집의 모양은 일관되게 변하지 않습니다.
그림멧(1999)[17]을 참조해 주세요.11개 이상의 치수에서 이러한 사실은 레이스 확장이라고 알려진 기술을 사용하여 대부분 입증됩니다.레이스 확장 버전은 7차원 이상에 유효해야 하며, 아마도 6차원의 문턱값 케이스에도 영향을 미칠 수 있습니다.레이스 확장에 대한 침투의 관련성은 Hara & Slade(1990)[18]에서 확인할 수 있다.
2차원에서 첫 번째 사실("임계 단계에서 침투하지 않음")은 이중성을 사용하여 많은 격자에 대해 증명된다.대형 성단의 스케일 한계는 슈람-뢰너 진화의 관점에서 설명될 수 있다는 Oded Schramm의 추측을 통해 2차원 침투에 상당한 진전이 있었다.이 추측은 Smirnov(2001)[19]에 의해 삼각형 격자의 현장 침투의 특별한 경우에 증명되었다.
다른 모델
- 액체에 작용하는 중력의 영향을 모델링하는 유도 침투도 Broadbent & Hammersley(1957년)[1]에 도입되어 접촉 과정과 관련이 있다.
- 연구된 첫 번째 모델은 베르누이 침투였다.이 모형에서는 모든 채권이 독립적이다.이 모델은 물리학자에 의해 결합 침투라고 불립니다.
- 다음으로 일반화는 이징 모델 및 다른 포츠 모델과 많은 관련이 있는 포르투인-카스테린 랜덤 클러스터 모델로 도입되었습니다.
- 완전 그래프의 베르누이(결합) 침투는 랜덤 그래프의 한 예이다.임계 확률은 p = 1/N이며, 여기서 N은 그래프의 꼭지점(정점) 수입니다.
- 부트스트랩 퍼컬레이션은 액티브네이버가 너무 적은 경우 클러스터에서 액티브셀을 삭제하고 나머지 [20]셀의 접속성을 조사합니다.
- 첫 번째 통로의 침투.
- 침입 침투.
적용들
생물학, 생화학, 물리 바이러스학에서
B형 간염 바이러스 캡시드의 파편화 역치를 예측하고 [23]실험적으로 검출하여 생물학적 바이러스 껍질(캡시드)[21][22]의 파편화를 성공적으로 예측하기 위해 퍼콜레이션 이론이 사용되어 왔다.나노스코프 셸에서 임계 수의 서브유닛이 랜덤으로 제거되면 파편화되어 다른 단일 입자 기술 중 전하 검출 질량 분광법(CDMS)을 사용하여 이 파편을 검출할 수 있습니다.이것은 일반적인 보드 게임 젠가와 유사한 분자로 바이러스 분해에 대한 광범위한 연구와 관련이 있습니다.흥미롭게도,[21] 보다 안정적인 바이러스 입자가 자연에서 더 풍부하게 발견됩니다.
생태학에서
침투 이론은 환경 파편이 동물 서식지에[24] 어떻게 영향을 미치는지에 대한 연구와 페스트 박테리아 예르시니아 페스티스가 어떻게 [25]퍼지는지에 대한 모델에 적용되어 왔다.
「 」를 참조해 주세요.
- 연속체 침투 이론
- 임계 지수 – 임계 지점 부근의 물리 상태를 나타내는 파라미터
- 직접 투과 – 중력 등의 힘으로 필터링하는 물리적 모델
- Erdss-Rényi 모델– 랜덤 그래프 생성을 위한 밀접하게 관련된 두 가지 모델
- 프랙탈 – 자체 유사한 수학적 구조
- 자이언트 컴포넌트– 랜덤 그래프의 대규모 접속 컴포넌트
- 그래프 이론 – 이산 수학 영역
- 상호의존 네트워크– 네트워크 과학의 서브필드
- 침입 침투
- 칸-칼라이 추측 - 수학적 명제
- 네트워크 이론 – 개별 객체 간의 관계를 나타내는 그래프 연구
- 네트워크 과학– 학술 분야
- 침투 임계값 – 침투 이론 모델의 임계값
- 침투 임계 지수 – 침투 이론의 수학적 매개 변수
- 스케일이 필요 없는 네트워크– 멱함수의 법칙에 따른 정도 분포
- 최단 경로 문제 – 그래프 이론의 계산 문제
레퍼런스
- ^ a b Broadbent, Simon; Hammersley, John (1957). "Percolation processes I. Crystals and mazes". Mathematical Proceedings of the Cambridge Philosophical Society. 53 (3): 629–641. Bibcode:1957PCPS...53..629B. doi:10.1017/S0305004100032680. ISSN 0305-0041.
- ^ Sahini, M.; Sahimi, M. (2003-07-13). Applications Of Percolation Theory. CRC Press. ISBN 978-0-203-22153-2.
- ^ van Krevelen, Dirk W (1982). "Development of coal research—a review". Fuel. 61 (9): 786–790.
- ^ 로잘린드 프랭클린 종이들 - 석탄에 난 구멍들:1942-1951년, BCURA와 파리에서 연구.https://profiles.nlm.nih.gov/spotlight/kr/feature/coal 를 참조해 주세요.접속처: 2022-01-17
- ^ Hammersley, JM; Welsh, DJA (1980). "Percolation theory and its ramifications". Contemporary Physics. 21 (6): 593–605.
- ^ Bollobás, Béla; Riordan, Oliver (2006). "Sharp thresholds and percolation in the plane". Random Structures and Algorithms. 29 (4): 524–548. arXiv:math/0412510. doi:10.1002/rsa.20134. ISSN 1042-9832. S2CID 7342807.
- ^ MEJ Newman; RM Ziff (2000). "Efficient Monte Carlo algorithm and high-precision results for percolation". Physical Review Letters. 85 (19): 4104–4107. arXiv:cond-mat/0005264. Bibcode:2000PhRvL..85.4104N. doi:10.1103/physrevlett.85.4104. PMID 11056635. S2CID 747665.
- ^ Erdős, P. & Rényi, A. (1959). "On random graphs I.". Publ. Math. (6): 290–297.
- ^ Erdős, P. & Rényi, A. (1960). "The evolution of random graphs". Publ. Math. Inst. Hung. Acad. Sci. (5): 17–61.
- ^ Bolloba's, B. (1985). "Random Graphs". Academic.
- ^ Berchenko, Yakir; Artzy-Randrup, Yael; Teicher, Mina; Stone, Lewi (2009-03-30). "Emergence and Size of the Giant Component in Clustered Random Graphs with a Given Degree Distribution". Physical Review Letters. 102 (13): 138701. doi:10.1103/PhysRevLett.102.138701. ISSN 0031-9007.
- ^ Li, Ming; Liu, Run-Ran; Lü, Linyuan; Hu, Mao-Bin; Xu, Shuqi; Zhang, Yi-Cheng (2021-04-25). "Percolation on complex networks: Theory and application". Physics Reports. Percolation on complex networks: Theory and application. 907: 1–68. doi:10.1016/j.physrep.2020.12.003. ISSN 0370-1573.
- ^ Hassan, M. K.; Rahman, M. M. (2015). "Percolation on a multifractal scale-free planar stochastic lattice and its universality class". Phys. Rev. E. 92 (4): 040101. arXiv:1504.06389. Bibcode:2015PhRvE..92d0101H. doi:10.1103/PhysRevE.92.040101. PMID 26565145. S2CID 119112286.
- ^ Hassan, M. K.; Rahman, M. M. (2016). "Universality class of site and bond percolation on multi-multifractal scale-free planar stochastic lattice". Phys. Rev. E. 94 (4): 042109. arXiv:1604.08699. Bibcode:2016PhRvE..94d2109H. doi:10.1103/PhysRevE.94.042109. PMID 27841467. S2CID 22593028.
- ^ Kesten, Harry (1982). Percolation Theory for Mathematicians. Birkhauser. doi:10.1007/978-1-4899-2730-9. ISBN 978-0-8176-3107-9.
- ^ Grimmett, Geoffrey; Marstrand, John (1990). "The Supercritical Phase of Percolation is Well Behaved". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 430 (1879): 439–457. Bibcode:1990RSPSA.430..439G. doi:10.1098/rspa.1990.0100. ISSN 1364-5021. S2CID 122534964.
- ^ Grimmett, Geoffrey (1999). Percolation. Grundlehren der mathematischen Wissenschaften. Vol. 321. Berlin: Springer. doi:10.1007/978-3-662-03981-6. ISBN 978-3-642-08442-3. ISSN 0072-7830.
- ^ Hara, Takashi; Slade, Gordon (1990). "Mean-field critical behaviour for percolation in high dimensions". Communications in Mathematical Physics. 128 (2): 333–391. Bibcode:1990CMaPh.128..333H. doi:10.1007/BF02108785. ISSN 0010-3616. S2CID 119875060.
- ^ Smirnov, Stanislav (2001). "Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limits". Comptes Rendus de l'Académie des Sciences. I. 333 (3): 239–244. arXiv:0909.4499. Bibcode:2001CRASM.333..239S. CiteSeerX 10.1.1.246.2739. doi:10.1016/S0764-4442(01)01991-7. ISSN 0764-4442.
- ^ 를 클릭합니다Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and Its Applications, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/0378-4371(91)90295-n.
- ^ a b Brunk, Nicholas E.; Twarock, Reidun (2021). "Percolation Theory Reveals Biophysical Properties of Virus-like Particles". ACS Nano. American Chemical Society (ACS). 15 (8): 12988–12995. doi:10.1021/acsnano.1c01882. ISSN 1936-0851. PMC 8397427. PMID 34296852.
- ^ Brunk, N. E.; Lee, L. S.; Glazier, J. A.; Butske, W.; Zlotnick, A. (2018). "Molecular Jenga: the percolation phase transition (collapse) in virus capsids". Physical Biology. 15 (5): 056005. Bibcode:2018PhBio..15e6005B. doi:10.1088/1478-3975/aac194. PMC 6004236. PMID 29714713.
- ^ Lee, L. S.; Brunk, N.; Haywood, D. G.; Keifer, D.; Pierson, E.; Kondylis, P.; Zlotnick, A. (2017). "A molecular breadboard: Removal and replacement of subunits in a hepatitis B virus capsid". Protein Science. 26 (11): 2170–2180. doi:10.1002/pro.3265. PMC 5654856. PMID 28795465.
- ^ Boswell, G. P.; Britton, N. F.; Franks, N. R. (1998-10-22). "Habitat fragmentation, percolation theory and the conservation of a keystone species". Proceedings of the Royal Society of London B: Biological Sciences. 265 (1409): 1921–1925. doi:10.1098/rspb.1998.0521. ISSN 0962-8452. PMC 1689475.
- ^ Davis, S.; Trapman, P.; Leirs, H.; Begon, M.; Heesterbeek, J. a. P. (2008-07-31). "The abundance threshold for plague as a critical percolation phenomenon". Nature. 454 (7204): 634–637. Bibcode:2008Natur.454..634D. doi:10.1038/nature07053. hdl:1874/29683. ISSN 1476-4687. PMID 18668107. S2CID 4425203.
- Aizenman, Michael; Barsky, David (1987), "Sharpness of the phase transition in percolation models", Communications in Mathematical Physics, 108 (3): 489–526, Bibcode:1987CMaPh.108..489A, doi:10.1007/BF01212322, S2CID 35592821
- Menshikov, Mikhail (1986), "Coincidence of critical points in percolation problems", Soviet Mathematics - Doklady, 33: 856–859
추가 정보
- Austin, David (July 2008). "Percolation: Slipping through the Cracks". American Mathematical Society.
- Bollobás, Béla; Riordan, Oliver (2006). Percolation. Cambridge University Press. ISBN 978-0521872324.
- Kesten, Harry (May 2006). "What Is ... Percolation?" (PDF). Notices of the American Mathematical Society. 53 (5): 572–573. ISSN 1088-9477.