Fraktale Dimension in Netzwerken – Wikipedia

Posted on by
before-content-x4

Die Fraktalanalyse ist nützlich bei der Untersuchung komplexer Netzwerke, die sowohl in natürlichen als auch in künstlichen Systemen wie Computersystemen, Gehirn und sozialen Netzwerken vorhanden sind, und ermöglicht die Weiterentwicklung des Feldes in der Netzwerkwissenschaft.

Selbstähnlichkeit komplexer Netzwerke[edit]

Viele reale Netzwerke haben zwei grundlegende Eigenschaften: skalierungsfreies Eigentum und Eigentum der kleinen Welt. Wenn die Gradverteilung des Netzwerks einem Potenzgesetz folgt, ist das Netzwerk skalierungsfrei. Wenn zwei beliebige Knoten in einem Netzwerk in einer sehr kleinen Anzahl von Schritten verbunden werden können, spricht man von einer kleinen Welt.

Die Eigenschaften der kleinen Welt können mathematisch durch die langsame Zunahme des durchschnittlichen Durchmessers des Netzwerks mit der Gesamtzahl der Knoten ausgedrückt werden

N.{ displaystyle N}

,

wo

l{ displaystyle l}

ist der kürzeste Abstand zwischen zwei Knoten.

Gleichermaßen erhalten wir:

wo

l0{ displaystyle l_ {0}}

ist eine charakteristische Länge.

Für eine selbstähnliche Struktur wird eher eine Potenz-Gesetz-Beziehung als die obige Exponentialbeziehung erwartet. Aus dieser Tatsache scheint es, dass die Netzwerke der kleinen Welt unter einer Transformation im Längenmaßstab nicht selbstähnlich sind.

Die Analyse einer Vielzahl realer komplexer Netzwerke zeigt jedoch, dass sie auf allen Längenskalen selbstähnlich sind. Diese Schlussfolgerung ergibt sich aus der Messung einer Potenzgesetzbeziehung zwischen der Anzahl der zur Abdeckung des Netzwerks erforderlichen Boxen und der Größe der Box, der sogenannten Box fraktale Skalierung.[1]

Selbstähnlichkeit wurde in den lösungsmittelzugänglichen Oberflächen von Proteinen entdeckt.[2][3] Da Proteine ​​kugelförmig gefaltete Ketten bilden, hat diese Entdeckung wichtige Auswirkungen auf die Proteinentwicklung und die Proteindynamik, da damit charakteristische dynamische Längenskalen für die Proteinfunktionalität erstellt werden können.[4]

Die Methoden zur Berechnung der Dimension[edit]

Im Allgemeinen berechnen wir die fraktale Dimension entweder mit Box-Zählmethode oder der Cluster-Wachstumsmethode.

Fig. (2) Cluster-Wachstumsmethode.

Die Boxzählmethode[edit]

Lassen

N.B.{ displaystyle N_ {B}}

sei die Anzahl der Kästchen mit linearer Größe

lB.{ displaystyle l_ {B}}

, benötigt, um das gegebene Netzwerk abzudecken. Die fraktale Dimension

dB.{ displaystyle d_ {B}}

ist dann gegeben durch

Dies bedeutet, dass die durchschnittliche Anzahl der Eckpunkte

⟨M.B.(lB.)⟩{ displaystyle left langle M_ {B} left (l_ {B} right) right rangle}

innerhalb einer Box von Größe

lB.{ displaystyle l_ {B}}

Durch Messung der Verteilung von

N.{ displaystyle N}

für verschiedene Kartongrößen oder durch Messung der Verteilung von

⟨M.B.(lB.)⟩{ displaystyle left langle M_ {B} left (l_ {B} right) right rangle}

für verschiedene Kastengrößen die fraktale Dimension

dB.{ displaystyle d_ {B}}

kann durch ein Potenzgesetz der Verteilung erhalten werden.

Die Cluster-Wachstumsmethode[edit]

Ein Startknoten wird zufällig ausgewählt. Ist der Mindestabstand

l{ displaystyle l}

gegeben ist, eine Gruppe von Knoten durch höchstens getrennt

l{ displaystyle l}

aus dem Startknoten kann gebildet werden. Der Vorgang wird wiederholt, indem viele Seeds ausgewählt werden, bis die Cluster das gesamte Netzwerk abdecken. Dann die Dimension

df{ displaystyle d_ {f}}

kann berechnet werden durch

wo

⟨M.C.⟩{ displaystyle left langle M_ {C} right rangle}

ist die durchschnittliche Masse der Cluster, definiert als die durchschnittliche Anzahl der Knoten in einem Cluster.

Diese Methoden lassen sich nur schwer auf Netzwerke anwenden, da Netzwerke im Allgemeinen nicht in einen anderen Raum eingebettet sind. Um die fraktale Dimension von Netzwerken zu messen, fügen wir das Konzept der Renormierung hinzu.

Fraktale Skalierung in skalierungsfreien Netzwerken[edit]

Box-Counting und Renormierung[edit]

Abb. 3) ein, Demonstration der Box-Counting- und Renormierungsmethode für verschiedene

Um die Selbstähnlichkeit in Netzwerken zu untersuchen, verwenden wir die Box-Counting-Methode und die Renormierung. Fig. (3a) zeigt diese Prozedur unter Verwendung eines Netzwerks, das aus 8 Knoten besteht.

Für jede Größe lB., Boxen werden zufällig ausgewählt (wie bei der Cluster-Wachstumsmethode), bis das Netzwerk abgedeckt ist. Eine Box besteht aus Knoten, die alle durch einen Abstand von voneinander getrennt sind l < lB.Das heißt, jedes Knotenpaar in der Box muss durch einen minimalen Pfad von höchstens getrennt sein lB. Links. Dann wird jede Box durch einen Knoten ersetzt (Renormierung). Die renormierten Knoten sind verbunden, wenn mindestens eine Verbindung zwischen den nicht normalisierten Boxen besteht. Dieser Vorgang wird wiederholt, bis das Netzwerk auf einen Knoten zusammenfällt. Jedes dieser Felder hat eine effektive Masse (die Anzahl der darin enthaltenen Knoten), die wie oben gezeigt verwendet werden kann, um die fraktale Dimension des Netzwerks zu messen. In Fig. (3b) wird die Renormierung in drei Schritten für ein WWW-Netzwerk angewendet lB. = 3.

Fig. (5) zeigt die Invarianz der Gradverteilung P.(k) unter der Renormierung in Abhängigkeit von der Boxgröße im World Wide Web. Die Netzwerke sind auch bei mehreren Renormierungen, die für eine feste Boxgröße angewendet werden, unveränderlich lB.. Diese Invarianz legt nahe, dass die Netzwerke auf mehreren Längenskalen selbstähnlich sind.

Fig. (4) Skelett eines Netzwerks.[5]

Skelett- und Fraktalskalierung[edit]

Die fraktalen Eigenschaften des Netzwerks können in seiner zugrunde liegenden Baumstruktur gesehen werden. In dieser Ansicht besteht das Netzwerk aus dem Skelett und den Verknüpfungen. Das Skelett ist eine spezielle Art von Spannbaum, der aus den Kanten mit den höchsten Zentralitäten zwischen den Gleichungen besteht, und die verbleibenden Kanten im Netzwerk sind Verknüpfungen. Wenn das ursprüngliche Netzwerk skalierungsfrei ist, folgt sein Skelett auch einer Potenzgesetz-Gradverteilung, wobei der Grad vom Grad des ursprünglichen Netzwerks abweichen kann. Für die fraktalen Netzwerke nach der fraktalen Skalierung zeigt jedes Skelett eine fraktale Skalierung ähnlich der des ursprünglichen Netzwerks. Die Anzahl der Boxen, die das Skelett abdecken, entspricht fast der Anzahl, die zur Abdeckung des Netzwerks benötigt wird.[5]

Fraktale Netzwerke der realen Welt[edit]

Fig. (5) Invarianz der Gradverteilung des WWW unter der Renormierung für verschiedene Kastengrößen.[1]

Fig. (6) Fraktale Skalierungsanalyse des WWW-Netzwerks. Rot – das ursprüngliche Netzwerk, Blau – das Skelett und Orange – ein zufälliger Spannbaum.[6]

Da fraktale Netzwerke und ihre Skelette der Beziehung folgen

Wir können untersuchen, ob ein Netzwerk fraktal ist und welche fraktale Dimension das Netzwerk hat. Zum Beispiel das WWW, das menschliche Gehirn, das metabolische Netzwerk, das Proteininteraktionsnetzwerk (PIN) von H.. Sapiensund PIN von S.. cerevisiaewerden als fraktale Netzwerke betrachtet. Weiterhin sind die gemessenen fraktalen Dimensionen

dB.=4.1, 3.7, 3.4, 2.0, und 1.8{ displaystyle d_ {B} = 4.1, { mbox {}} 3.7, { mbox {}} 3.4, { mbox {}} 2.0, { mbox {und}} 1.8}

für die Netzwerke jeweils. Andererseits zeigen das Internet, das Akteursnetzwerk und künstliche Modelle (zum Beispiel das BA-Modell) die fraktalen Eigenschaften nicht.[6][7]

Andere Definitionen für Netzwerkdimensionen[edit]

Die beste Definition der Dimension für ein komplexes Netzwerk oder Diagramm hängt von der Anwendung ab. Beispielsweise wird die metrische Dimension als Auflösungssatz für ein Diagramm definiert. Definitionen basierend auf der Skalierungseigenschaft der “Masse” wie oben definiert mit Abstand,[8]

oder basierend auf der komplexen Netzwerk-Zeta-Funktion[9] wurden auch untersucht.

Für Netzwerke, die in den realen Raum eingebettet sind, kann eine Dimension definiert werden, die die Anzahl der Knoten kennzeichnet, die mit einer durchschnittlichen euklidischen Entfernung erreicht werden können.[10]

Verweise[edit]

  1. ^ ein b c Lied, Chaoming; Havlin, Shlomo; Makse, Hernán A. (2005). “Selbstähnlichkeit komplexer Netzwerke”. Natur. Springer Science and Business Media LLC. 433 (7024): 392–395. arXiv:cond-mat / 0503078. doi:10.1038 / nature03248. ISSN 0028-0836.CS1-Wartung: ref = harv (Link)
  2. ^ Moret, MA; Zebende, GF (2007-01-19). “Aminosäurehydrophobie und zugängliche Oberfläche”. Körperliche Überprüfung E.. Amerikanische Physikalische Gesellschaft (APS). 75 (1): 011920. doi:10.1103 / physreve.75.011920. ISSN 1539-3755.
  3. ^ Phillips, JC (2014). “Fraktale und selbstorganisierte Kritikalität in Proteinen”. Physica A: Statistische Mechanik und ihre Anwendungen. Elsevier BV. 415: 440–448. doi:10.1016 / j.physa.2014.08.034. ISSN 0378-4371.
  4. ^ 3. Phillips, JC Quantitative molekulare Skalierungstheorie der Proteinaminosäuresequenzen, -struktur und -funktionalität. arXiv 1606.1004116 (2016)
  5. ^ ein b K.-I. Goh, G. Salvi, B. Kahng und D. Kim, Skelett- und Fraktalskalierung in komplexen Netzwerken, Phys. Rev. Lett. 96, 018701 (2006), http://iopscience.iop.org/article/10.1088/1367-2630/9/6/177/pdf
  6. ^ ein b JS Kim et al.,Fraktalität in komplexen Netzwerken: kritische und überkritische Skelette, 2006, arXiv:cond-mat / 0605324
  7. ^ F. Klimm; Danielle S. Bassett; Jean M. Carlson; Peter J. Mucha (2014). “Auflösung struktureller Variabilität in Netzwerkmodellen und im Gehirn”. PLOS Computational Biology. 10 (3): e1003491. arXiv:1306.2893. Bibcode:2014PLSCB..10E3491K. doi:10.1371 / journal.pcbi.1003491. PMC 3967917. PMID 24675546.
  8. ^ Shanker, O. (2007). “Dimension eines komplexen Netzwerks definieren”. Moderne Physikbuchstaben B.. 21 (6): 321–326. Bibcode:2007MPLB … 21..321S. doi:10.1142 / S0217984907012773.
  9. ^ Shanker, O. (2007). “Graph Zeta Funktion und Dimension des komplexen Netzwerks”. Moderne Physikbuchstaben B.. 21 (11): 639–644. Bibcode:2007MPLB … 21..639S. doi:10.1142 / S0217984907013146.
  10. ^ D. Li; K. Kosmidis; A. Bunde; S. Havlin (2011). “Dimension räumlich eingebetteter Netzwerke”. Naturphysik. 7 (6): 481. Bibcode:2011NatPh … 7..481D. doi:10.1038 / nphys1932.


after-content-x4