부울 네트워크

노드당 N=4노드 및 K=1링크가 있는 부울 네트워크의 상태 공간.노드는 켜짐(빨간색) 또는 꺼짐(파란색) 중 하나입니다.얇은(검은색) 화살표는 각 노드의 단순한 "복사" 함수인 부울 함수의 입력을 나타냅니다.두꺼운(회색) 화살표는 동기 업데이트의 기능을 보여줍니다.총 6개의 (주황색) 유인기가 있으며 그 중 4개는 고정점입니다.

부울 네트워크는 각각에 할당된 부울 함수(변수마다 다를 수 있음)를 가진 이산적인 부울 변수 세트로 구성됩니다.부울 함수는 이들 변수의 서브셋에서 입력을 받아 할당되는 변수의 상태를 결정하는 출력입니다.이 함수 세트는 실제로 변수 세트의 토폴로지(접속성)를 결정하며, 변수 세트는 네트워크 내의 노드가 됩니다.통상, 시스템의 역학은, 시각 t+1 의 네트워크 상태에서의 각 변수의 기능을 평가해, 시각 t+1 의 네트워크 전체의 상태를 결정하는 이산 시계열로서 받아들여진다.이것은 동기 또는 ^[1]비동기식으로 실행할 수 있습니다.

부울 네트워크는 생물학에서 규제 네트워크를 모델링하기 위해 사용되어 왔습니다.부울 네트워크는 유전자가 단순한 이진 스위치가 아닌 유전적 현실을 조잡하게 단순화한 것이지만, 발현 및 ^[2]^[3]억제된 유전자의 올바른 패턴을 올바르게 전달하는 몇 가지 사례가 있다.수학적으로 쉬워 보이는 (동기식) 모델은 2000년대 ^[4]중반에야 완전히 이해되었습니다.

고전적 모형

부울 네트워크는 특정 종류의 순차 동적 시스템으로, 시간과 상태는 이산적입니다. 즉, 시계열 내의 변수 집합과 상태 집합은 각각 정수 계열에 대한 바이젝션을 가집니다.

랜덤 부울 네트워크(RBN)는 특정 크기의 모든 가능한 부울 네트워크 집합에서 랜덤으로 선택되는 네트워크입니다.그러면 이러한 네트워크의 예상 속성이 모든 가능한 네트워크의 앙상블의 다양한 통계 속성에 어떻게 의존하는지 통계적으로 조사할 수 있습니다.예를 들어 평균 접속이 변경됨에 따라 RBN 동작이 어떻게 변화하는지 조사할 수 있습니다.

최초의 부울 네트워크는 1969년 Stuart A. Kauffman에 의해 유전자 조절 네트워크의^[5] 무작위 모델로 제안되었지만 수학적 이해는 2000년대에 ^[6]^[7]시작되었다.

어트랙터

이후 부울 네트워크만 2N 가능한 상태를 가지고 있는 궤도 조만간, 따라서 이후 역학 관계를 결정론적은 동적 시스템에 대한 광범위한 분야에서( 하지만 비록 사이클은 단순한 끌어당기는 것 만약 그것에서 적시 르, 궤도 안정된 상태를 유지하거나 자전거에 대한 끌어당기는 것이라고 불리는 쓰러지고 이전에 방문한 상태에 도달할 것이다.a(다시 되돌아가다)어트랙터의 상태가 1개뿐인 경우는 포인트 어트랙터, 어트랙터가 2개 이상의 상태로 구성되어 있는 경우는 사이클 어트랙터라고 불립니다.유인기로 이어지는 일련의 상태를 유인기의 분지라고 합니다.궤적의 시작 부분에서만 발생하는 상태를 (궤적이 없는 상태를) 에덴의^[8] 정원 상태라고 하며, 이러한 상태에서 어트랙터로 향하는 네트워크 흐름의 역동성이라고 합니다.어트랙터에 도달하는 데 걸리는 시간을 과도 ^[4]시간이라고 합니다.

컴퓨터 파워가 증가하고 단순해 보이는 모델에 대한 이해가 높아짐에 따라, 저자들마다 유인기의 평균 수와 길이에 대해 서로 다른 추정치를 제시했는데, 여기 주요 ^[9]출판물의 간략한 요약이 있다.

작가.	연도	평균 어트랙터 길이	평균 유인자 번호	댓글
카우프만	1969	$\displaystyle \langle A\sim \sqrt {N}}$	$\displaystyle \langle \sim \sqrt {N}}$
바스토라 / 파리지^[10]	1998	멱승법칙보다 빠릅니다. $\langle A\rangle >N^{x}\forall x$ A $\langle A\rangle >N^{x}\forall x$ $\langle A\rangle >N^{x}\forall x$ x $\langle A\rangle >N^{x}\forall x$ x \ $displaystyle$ \ $langle$ A \ $rangle$ > $N^$ { $x$ } \ $forall$ x $\langle A\rangle >N^{x}\forall x$ }	멱승법칙보다 빠름, $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ x $\langle \nu \rangle >N^{x}\forall x$ \ $displaystyle \langle$ \ $nu \rangle$ > $N^{x}\forall$ x}	제1의 수치 증거
빌케 / 스주네손^[11]	2002		시스템 크기를 가진 선형 - $\langle \nu \rangle \sim N$ N $)$
소콜라/카우프만^[12]	2003		선형보다 빠릅니다 $\langle \nu \rangle >N^{x}$ $x>1$ $\langle \nu \rangle >N^{x}$ $x>1$ { $displaystyle$ $x$ > 1 { \ $displaystyle x$ $\langle \nu \rangle >N^{x}$ $>$ 1 } ）。
사무엘손/트로인^[13]	2003		초다항 성장, $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ > $\langle \nu \rangle >N^{x}\forall x$ x $\langle \nu \rangle >N^{x}\forall x$ x { $displaystyle$ \ $langle$ \ $nu$ \ $rangle$ > $N^$ { $x$ } \ $forall$ x }	수학적 증명
미할예프/드로셀^[14]	2005	멱승법칙보다 빠릅니다. $\langle A\rangle >N^{x}\forall x$ A $\langle A\rangle >N^{x}\forall x$ $\langle A\rangle >N^{x}\forall x$ x $\langle A\rangle >N^{x}\forall x$ x \ $displaystyle$ \ $langle$ A \ $rangle$ > $N^$ { $x$ } \ $forall$ x $\langle A\rangle >N^{x}\forall x$ }	멱승법칙보다 빠름, $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ $\langle \nu \rangle >N^{x}\forall x$ x $\langle \nu \rangle >N^{x}\forall x$ \ $displaystyle \langle$ \ $nu \rangle$ > $N^{x}\forall$ x}

안정성.

동적 시스템 이론에서 네트워크의 어트랙터의 구조와 길이는 네트워크의 동적 위상에 대응합니다.부울 네트워크의 안정성은 노드의 연결에 따라 달라집니다.Boolean 네트워크는 안정, 크리티컬 또는 카오스 동작을 나타낼 수 있습니다.이 현상은 노드의 평균 연결 수 임계값( $K_{c}$ c $\$ 에 의해 제어되며 거리 측정으로 해밍 거리를 특징으로 할 수 있습니다.불안정한 체제에서는 초기에 가까운 두 상태 사이의 거리가 평균적으로 시간에 따라 기하급수적으로 증가하는 반면, 안정된 체제에서는 기하급수적으로 감소한다.여기서 "초기 근접 상태"는 네트워크 내의 노드 수( $\displaystyle$ N $N$ 에 비해 Hamming 거리가 작음을 의미합니다.

N-K^[15] 모델의 경우 K $K<K_{c}$ < $K$ < K $_$ { $c$ } 、 K $K=K_{c}$ $K=K_{c}$ \ $display$ K $=$ K _ { $c$ } 、 K $K>K_{c}$ > $K$ c \ display $style K$ _ { c } $K>K_{c}$ K _ { c }의 경우 네트워크는 안정적입니다.

특정 $n_{i}$ $(\$ })의 $n_{i}$ 상태는 해당 진실 테이블에 따라 갱신되며 출력은 랜덤하게 입력됩니다. $p_{i}$ i $p_{i}$ {\ $displaystyle p_{$ i}}는 $p_{i}$ 특정 일련의 입력 신호에 오프 출력을 할당할 가능성을 나타냅니다.

$p_{i}=p=const.$ i $p_{i}=p=const.$ $p_{i}=p=const.$ $p_{i}=p=const.$ $p_{i}=p=const.$ $p_{i}=p=const.$ n s $p_{i}=p=const.$ . { $displaystyle p_{i$ }= $p=const.$ } 각 $p_{i}=p=const.$ 노드에 대해 안정된 범위와 카오스 범위 간의 전환은 p ${\displaystyle$ p $p$ 에 따라 $달라집니다$ $.$ Bernard Derrida 및 Yves Poemau에^[16] 따르면 평균 $K_{c}=1/[2p(1-p)]$ 수 임계값은 $K_{c}=1/[2p(1-p)]$ c $K_{c}=1/[2p(1-p)]$ / [ $K_{c}=1/[2p(1-p)]$ ] { $c$ $K_{c}=1/[2p(1-p)]$ 1 / [ 2 p $K_{c}=1/[2p(1-p)]$ ] { display $K$ _ { $c$ } = $K_{c}=1/[2p(1-p)]$ 1 / [ 2 p ( 1 - p ) $]$ 입니다 $K_{c}=1/[2p(1-p)]$

만약 K{K\displaystyle}, 그리고 in-degrees과 out-degrees 사이에 아무런 상관 관계가 있다고 일정하지 않기 때문입니다, 안정성의 조건⟨ Ki의 스녀 ⟩{\displaystyle\langle K^{에}\rangle에 의해}만약⟨ Ki의 스녀⟩<>Kc{\displaystyle\langle K^{에}\rangle<>K_{c}}, critica[17][18][19]이 네트워크 안정된 것이 결정된다.나는 만약⟨ K나는 $\langle K^{in}\rangle >K_{c}$ $\langle K^{in}\rangle =K_{c}$ $\langle K^{in}\rangle =K_{c}$ c { $displaystyle$ \ $displayle K$ ^ { $in$ } \ rangle = $K$ _ { $c$ $\langle K^{in}\rangle >K_{c}$ 、 $\langle K^{in}\rangle >K_{c}$ \ $displaystyle$ \ $displaystyle K^$ { $in$ } \ $rangle$ > $K$ _ { $c$ } $\langle K^{in}\rangle >K_{c}$ 。

안정성 조건은 스케일프리 토폴로지를 사용하는 네트워크의 경우 P $P(K)\propto K^{-\gamma }$ $P(K)\propto K^{-\gamma }$ $P(K)\propto K^{-\gamma }$ - $（$ \ $display style$ P ( $K$ ) \ $propto$ K^ { - \ $gamma$ } $P(K)\propto K^{-\gamma }$ $\langle K^{in}\rangle =\langle K^{out}\rangle$ i n $\langle K^{in}\rangle =\langle K^{out}\rangle$ $\langle K^{in}\rangle =\langle K^{out}\rangle$ $display tyle$ \ display tyle \ display tyle ） $\langle K^{in}\rangle =\langle K^{out}\rangle$ $P(K)\propto K^{-\gamma }$ $\langle K^{in}\rangle =\langle K^{out}\rangle$ 노드로부터의 out-link는 다른 ^[20]노드로의 인링크입니다.

감도는 입력이 변경되면 특정 노드의 부울 함수의 출력이 변경될 가능성을 나타냅니다. $q_{i}=2p_{i}(1-p_{i})$ 부울 네트워크의 경우, $q_{i}=2p_{i}(1-p_{i})$ $q_{i}=2p_{i}(1-p_{i})$ $= 2$ i ( $1$ - $q_{i}=2p_{i}(1-p_{i})$ ) { $displaystyle q$ _ { i $q_{i}=2p_{i}(1-p_{i})$ 。일반적으로 네트워크의 안정성은 $매트릭스$ Q의 최대 고유값 $(\$ _ ${$ $i})$ 에 의해 $\lambda _{Q}$ $Q_{ij}=q_{i}A_{ij}$ 됩니다. $Q_{ij}=q_{i}A_{ij}$ 서 $Q_style$ $Q_{ij}=q_{i}A_{ij}$ ${$ Q $Q$ $Q_{ij}=q_{i}A_{ij}$ $A_{ij$ 및 A $(\displaystyle$ A $)$ 는 $A$ 네트워크의 ^[21]인접 매트릭스입니다. $\lambda _{Q}>1$ 는 Q $\lambda _{Q}<1$ < 1 $\lambda _{Q}<1$ \ $displaystyle$ \ $displayda$ _ { $Q$ } < $1$ $\lambda _{Q}<1$ Critical $=$ \ $displaystyle$ \ $displayda$ _ { Q $\lambda _{Q}>1$ } $\lambda _{Q}=1$ > $1$ \ $displaystyle$ \ $displayda$ _ { $Q$ } $\lambda _{Q}>1$ = $1$ 이면 안정적입니다.

모델의 변형

기타 토폴로지

한 가지 주제는 서로 다른 기본 그래프 토폴로지를 연구하는 것입니다.

동종의 경우는 단순히 유명한 이싱 모델을 축소한 격자를 말합니다.
부울 ^[22]네트워크에서는 스케일프리 토폴로지를 선택할 수 있습니다.멱함수에서 정도 분포만 ^[23]분포하는 경우와 정도 분포만 분포하는 경우를 구분할 수 있습니다.

기타 업데이트 방식

클래식 부울 네트워크(CRBN이라고도 함)는 동기식으로 갱신됩니다.유전자가 보통 ^[24]동시에 상태를 바꾸지 않는다는 사실에 자극받아, 다른 대안들이 도입되었다.일반적인 분류는^[25] 다음과 같습니다.

결정론적 비동기 업데이트 부울 네트워크(DRBN)는 동기적으로 업데이트되지 않지만 결정론적 솔루션은 여전히 존재합니다.노드 i는 t q_i Q(mod_i P)일 때 갱신됩니다.여기서 t는 시간 스텝입니다.^[26]
가장 일반적인 경우는 완전 확률 업데이트(GARBN, 일반 비동기 랜덤 부울 네트워크)입니다.여기서 갱신되는 각 계산 스텝에서 하나 이상의 노드가 선택된다.
Partially-Observated Boolean Dynamic System(POBDS;^[27]^[28]^[29]^[30] 부분 관측 부울 다이내믹 시스템) 신호 모델은 부울 상태 벡터의 직접 관측 가능성의 가정을 제거하고 실제로 마주치는 시나리오에 대처함으로써 이전의 모든 결정론적 및 확률적 부울 네트워크 모델과 다릅니다.
Autonomous Boolean Network(ABN; 자율부울 네트워크)는 연속적인 시간(t는 정수가 아닌 실수)에 갱신되므로 레이스 조건과 결정론적 ^[31]^[32]혼돈 등의 복잡한 동적 동작이 발생합니다.