Strukturální omezení - Structural cut-off - Wikipedia

The strukturální cut-off je koncept v síťová věda který ukládá mezní stupeň v rozdělení stupňů sítě konečné velikosti kvůli strukturálním omezením (jako např jednoduchý graf vlastnictví). Sítě s vrcholy se stupněm vyšším, než je strukturální omezení, budou zobrazeny strukturálně disassortativity.

Definice

Strukturální cut-off je maximální stupeň cut-off, který vyplývá ze struktury sítě konečné velikosti.

Nechat ${ displaystyle E_ {kk '}}$ být počet hran mezi všemi vrcholovými stupni ${ displaystyle k}$ a ${ displaystyle k '}$ -li ${ displaystyle k neq k '}$ a dvojnásobné číslo, pokud ${ displaystyle k = k '}$ Vzhledem k tomu, že více hran mezi dvěma vrcholy není povoleno, ${ displaystyle E_ {kk '}}$ je ohraničen maximálním počtem hran mezi dvěma třídami ${ displaystyle m_ {kk '}}$ .

Potom lze poměr zapsat

{ displaystyle r_ {kk '} equiv { frac {E_ {kk'}} {m_ {kk '}}} = { frac { langle k rangle P (k, k')} { min {kP (k), k'P (k '), NP (k) P (k') }}}}

,

kde ${ displaystyle langle k rangle}$ je průměrný stupeň sítě, ${ displaystyle N}$ je celkový počet vrcholů, ${ displaystyle P (k)}$ je pravděpodobnost, že náhodně zvolený vrchol bude mít stupeň ${ displaystyle k}$ , a ${ displaystyle P (k, k ') = E_ {kk'} / langle k rangle N}$ je pravděpodobnost, že náhodně vybraná hrana spojí na jedné straně vrchol se stupněm ${ displaystyle k}$ s vrcholem stupně ${ displaystyle k '}$ .

Být ve fyzické oblasti, ${ displaystyle r_ {kk '} leq 1}$ musí být spokojen.

Strukturální omezení ${ displaystyle k_ {s}}$ je pak definováno ${ displaystyle r_ {k_ {s} k_ {s}} = 1}$ .^[1]

Strukturální omezení pro neutrální sítě

Strukturální cut-off hraje důležitou roli v neutrálních (nebo nekorelovaných) sítích, které nevykazují žádnou souhrnnost. Vyříznutí má formu

{ displaystyle k_ {s} sim ( langle k rangle N) ^ {1/2}}

což je konečné v jakékoli skutečné síti.

Tedy pokud jsou vrcholové stupně ${ displaystyle k geq k_ {s}}$ existuje fyzicky nemožné připojit mezi nimi dostatek hran, aby byla zachována neutralita sítě.

Strukturální disassortativita v sítích bez měřítka

V bezškálová síť rozdělení stupňů je popsáno mocninovým zákonem s charakteristickým exponentem ${ displaystyle gamma}$ , ${ displaystyle P (k) sim k ^ {- gamma}}$ V bezplatné síti s konečným měřítkem se maximální stupeň jakéhokoli vrcholu (nazývaného také přirozený cut-off) mění jako

{ displaystyle k _ { text {max}} sim N ^ { frac {1} { gamma -1}}}

.

Pak sítě s ${ displaystyle gamma <3}$ , což je režim většiny skutečných sítí, bude mít ${ displaystyle k _ { text {max}}}$ se rozcházejí rychleji než ${ displaystyle k_ {s} sim N ^ {1/2}}$ v neutrální síti. To má důležitý důsledek, že jinak neutrální síť může vykazovat disortativní korelaci stupňů, pokud ${ displaystyle k _ { text {max}}> k_ {s}}$ Tato disassortativita není výsledkem žádné mikroskopické vlastnosti sítě, ale je to čistě kvůli strukturálním omezením sítě. V analýze sítí, aby byla korelace stupňů smysluplná, je třeba zkontrolovat, zda korelace nemají strukturální původ.

Dopad strukturálního omezení

Generované sítě

Síť generovaná náhodně algoritmem generování sítě obecně není prostá strukturální disassortativity. Je-li nutná neutrální síť, je třeba se vyhnout strukturální disassortativitě. Existuje několik způsobů, jak toho dosáhnout: ^[2]

Povolte více hran mezi stejnými dvěma vrcholy. I když to znamená, že síť již není jednoduchou sítí, umožňuje dostatečné okraje k zachování neutrality.
Jednoduše odstraňte všechny vrcholy se stupněm ${ displaystyle k> k_ {s}}$ . To zaručuje, že žádný vrchol nepodléhá strukturálním omezením na svých okrajích a že síť neobsahuje strukturální disassortativitu.

Skutečné sítě

V některých reálných sítích lze použít stejné metody jako pro generované sítě. V mnoha případech však nemusí mít smysl uvažovat o více hranách mezi dvěma vrcholy, nebo takové informace nejsou k dispozici. Vrcholy vysokého stupně (rozbočovače) mohou být také důležitou součástí sítě, kterou nelze odstranit bez změny dalších základních vlastností.

Chcete-li zjistit, zda má sortiment nebo disassortativita sítě strukturální původ, lze síť porovnat s randomizovanou verzí, která zachovává určitý stupeň (bez více hran). Poté bude jakákoli míra assortativity randomizované verze výsledkem strukturální odříznout. Pokud skutečná síť zobrazuje další doplňkovou nebo disassortativitu nad rámec strukturální disassortativity, pak je to smysluplná vlastnost skutečné sítě.

Další veličiny, které závisí na korelacích stupňů, jako jsou některé definice koeficient bohatého klubu, bude rovněž ovlivněno strukturálním omezením. ^[3]

Viz také

Reference

^ Boguna, M .; Pastor-Satorras, R .; Vespignani, A. (1. března 2004). "Mezní hodnoty a efekty konečné velikosti v sítích bez měřítka". Evropský fyzický deník B. 38 (2): 205–209. arXiv:cond-mat / 0311650. Bibcode:2004EPJB ... 38..205B. doi:10.1140 / epjb / e2004-00038-8.
^ Catanzaro, Michele; Boguñá, Marián; Pastor-Satorras, Romualdo (únor 2005). "Generování nekorelovaných náhodných sítí bez měřítka". Fyzický přehled E. 71 (2). arXiv:cond-mat / 0408110. Bibcode:2005PhRvE..71b7103C. doi:10.1103 / PhysRevE.71.027103.
^ Zhou, S; Mondragón, R J (28. června 2007). "Strukturální omezení ve složitých sítích". New Journal of Physics. 9 (6): 173–173. arXiv:fyzika / 0702096. Bibcode:2007NJPh .... 9..173Z. doi:10.1088/1367-2630/9/6/173.

[1] Boguna, M .; Pastor-Satorras, R .; Vespignani, A. (1. března 2004). "Mezní hodnoty a efekty konečné velikosti v sítích bez měřítka". Evropský fyzický deník B. 38 (2): 205–209. arXiv:cond-mat / 0311650. Bibcode:2004EPJB ... 38..205B. doi:10.1140 / epjb / e2004-00038-8.

[2] Catanzaro, Michele; Boguñá, Marián; Pastor-Satorras, Romualdo (únor 2005). "Generování nekorelovaných náhodných sítí bez měřítka". Fyzický přehled E. 71 (2). arXiv:cond-mat / 0408110. Bibcode:2005PhRvE..71b7103C. doi:10.1103 / PhysRevE.71.027103.

[3] Zhou, S; Mondragón, R J (28. června 2007). "Strukturální omezení ve složitých sítích". New Journal of Physics. 9 (6): 173–173. arXiv:fyzika / 0702096. Bibcode:2007NJPh .... 9..173Z. doi:10.1088/1367-2630/9/6/173.

[1]

[2]

[3]