Im Kontext der Netzwerktheorie ist ein komplexes Netzwerk ein Graph (Netzwerk) mit nicht-trivialen topologischen Merkmalen – Merkmalen, die in einfachen Netzwerken wie Gittern oder Zufallsgraphen nicht auftreten , aber häufig in Netzwerken realer Systeme zu finden sind. Die Erforschung komplexer Netzwerke ist ein junges und aktives Forschungsgebiet [ 1 ] [ 2 ] (seit 2000), das maßgeblich durch empirische Erkenntnisse aus realen Netzwerken wie Computernetzwerken , biologischen Netzwerken , technologischen Netzwerken, Gehirnnetzwerken [ 3 ] [ 4 ] und sozialen Netzwerken inspiriert wurde .

Definition

Die meisten sozialen , biologischen und technologischen Netzwerke weisen ausgeprägte, nicht-triviale topologische Merkmale auf, deren Verbindungsmuster weder rein regulär noch rein zufällig sind. Zu diesen Merkmalen gehören ein schwerer Ausläufer in der Gradverteilung , ein hoher Clustering-Koeffizient , Assortativität oder Disassortativität zwischen Knoten, Community-Struktur und hierarchische Struktur . Bei gerichteten Netzwerken zählen dazu auch Reziprozität , das Triaden-Signifikanzprofil und weitere Merkmale. Im Gegensatz dazu weisen viele der in der Vergangenheit untersuchten mathematischen Netzwerkmodelle, wie beispielsweise Verbände und Zufallsgraphen , diese Merkmale nicht auf. Die komplexesten Strukturen lassen sich durch Netzwerke mit einer mittleren Anzahl von Interaktionen realisieren. [ 5 ] Dies entspricht der Tatsache, dass der maximale Informationsgehalt ( Entropie ) bei mittleren Wahrscheinlichkeiten erreicht wird.

Zwei bekannte und viel untersuchte Klassen komplexer Netzwerke sind skalenfreie Netzwerke [ 6 ] und Small-World-Netzwerke [ 7 , 8 ], deren Entdeckung und Definition als Paradebeispiele in diesem Forschungsgebiet gelten. Beide zeichnen sich durch spezifische Strukturmerkmale aus: Potenzgesetz -Gradverteilungen bei skalenfreien Netzwerken und kurze Pfadlängen sowie eine hohe Clusterbildung bei Small-World - Netzwerken. Da die Erforschung komplexer Netzwerke jedoch zunehmend an Bedeutung und Popularität gewinnt, rücken auch viele andere Aspekte von Netzwerkstrukturen in den Fokus der Forschung.

Das Forschungsgebiet entwickelt sich rasant und hat Forscher aus vielen Bereichen zusammengebracht, darunter Mathematik , Physik , elektrische Energiesysteme [ 9 ] , Biologie , Klimaforschung , Informatik , Soziologie , Epidemiologie und weitere [ 10 ] . Ideen und Werkzeuge der Netzwerkforschung und -technik wurden angewendet auf die Analyse metabolischer und genetischer Regulationsnetzwerke, die Untersuchung der Stabilität und Robustheit von Ökosystemen [ 11 ] , die klinische Forschung [ 12 ], die Modellierung und den Entwurf skalierbarer Kommunikationsnetzwerke, wie beispielsweise die Generierung und Visualisierung komplexer drahtloser Netzwerke [ 13 ] , sowie auf eine Vielzahl weiterer praktischer Fragestellungen. Die Netzwerkforschung ist Gegenstand zahlreicher Konferenzen in verschiedenen Fachgebieten und hat bereits viele Bücher für Laien und Experten inspiriert.

Skalenfreie Netzwerke

Ein Beispiel für ein komplexes skalenfreies Netzwerk

Ein Netzwerk wird als skalenfrei [ 6 ] [ 14 ] bezeichnet , wenn seine Gradverteilung, d. h. die Wahrscheinlichkeit, dass ein zufällig ausgewählter Knoten eine bestimmte Anzahl von Verbindungen (Grad) besitzt, einer mathematischen Funktion, dem sogenannten Potenzgesetz , folgt . Das Potenzgesetz impliziert, dass die Gradverteilung dieser Netzwerke keine charakteristische Skala aufweist. Im Gegensatz dazu ähneln Netzwerke mit einer einzigen, wohldefinierten Skala einem Gitter, da jeder Knoten (annähernd) denselben Grad besitzt. Beispiele für Netzwerke mit einer einzigen Skala sind der Erdős-Rényi-Zufallsgraph (ER-Graph) , zufällige reguläre Graphen , reguläre Gitter und Hyperwürfel . Zu den Modellen wachsender Netzwerke, die skaleninvariante Gradverteilungen erzeugen, gehören das Barabási-Albert-Modell und das Fitnessmodell . In einem Netzwerk mit einer skalenfreien Gradverteilung weisen einige Knoten einen Grad auf, der um Größenordnungen über dem Durchschnitt liegt – diese Knoten werden oft als „Hubs“ bezeichnet, obwohl diese Bezeichnung irreführend ist, da es definitionsgemäß keine inhärente Schwelle gibt, ab der ein Knoten als Hub gelten kann. Wenn es eine solche Schwelle gäbe, wäre das Netzwerk nicht skalenfrei.

Das Interesse an skalenfreien Netzwerken begann Ende der 1990er Jahre mit der Entdeckung von Potenzgesetz-Gradverteilungen in realen Netzwerken wie dem World Wide Web , dem Netzwerk autonomer Systeme (AS), einigen Netzwerken von Internetroutern, Proteininteraktionsnetzwerken, E-Mail-Netzwerken usw. Die meisten dieser berichteten „Potenzgesetze“ erweisen sich bei strengen statistischen Tests als unhaltbar. Die allgemeinere Idee von Gradverteilungen mit schweren Rändern – die viele dieser Netzwerke tatsächlich aufweisen (bevor Effekte endlicher Größe auftreten) – unterscheidet sich jedoch deutlich von dem, was man erwarten würde, wenn die Kanten unabhängig und zufällig verteilt wären (d. h. einer Poisson-Verteilung folgten ). Es gibt viele verschiedene Möglichkeiten, ein Netzwerk mit einer Potenzgesetz-Gradverteilung zu konstruieren. Der Yule-Prozess ist ein kanonischer generativer Prozess für Potenzgesetze und ist seit 1925 bekannt. Aufgrund seiner häufigen Weiterentwicklung ist er jedoch unter vielen anderen Namen bekannt, z. B. als Gibrat-Prinzip von Herbert A. Simon , Matthäus-Effekt , kumulativer Vorteil und bevorzugte Anbindung von Barabási und Albert für Potenzgesetz-Gradverteilungen. Kürzlich wurden hyperbolische geometrische Graphen als weitere Methode zur Konstruktion skalenfreier Netzwerke vorgeschlagen.

Netzwerke mit einer Potenzgesetz-Gradverteilung (und bestimmten anderen Strukturtypen) können gegenüber dem zufälligen Löschen von Knoten sehr resistent sein – d. h., die überwiegende Mehrheit der Knoten bleibt in einer großen Komponente miteinander verbunden. Solche Netzwerke können auch sehr empfindlich auf gezielte Angriffe reagieren, die darauf abzielen, das Netzwerk schnell zu zersplittern. Wenn der Graph bis auf die Gradverteilung gleichverteilt zufällig ist, sind diese kritischen Knoten diejenigen mit dem höchsten Grad und spielen daher eine Rolle bei der Ausbreitung von Krankheiten (natürlichen und künstlichen) in sozialen und Kommunikationsnetzwerken sowie bei der Verbreitung von Moden (beides wird durch einen Perkolations- oder Verzweigungsprozess modelliert ). Während Zufallsgraphen (ER) einen durchschnittlichen Abstand in der Größenordnung von log N [ 7 ] zwischen den Knoten aufweisen, wobei N die Anzahl der Knoten ist, kann ein skalenfreier Graph einen Abstand von log log N aufweisen.

Small-World-Netzwerke

Ein Netzwerk wird in Analogie zum Small-World-Phänomen (bekannt als „ Sechs-Grade-der-Trennung “) als Small-World-Netzwerk bezeichnet [ 7 ] . Die Small-World-Hypothese, die 1929 von dem ungarischen Schriftsteller Frigyes Karinthy erstmals beschrieben und 1967 von Stanley Milgram experimentell überprüft wurde , besagt, dass zwei beliebige Personen nur durch sechs Grade der Trennung miteinander verbunden sind, d. h. der Durchmesser des entsprechenden sozialen Netzwerks ist nicht wesentlich größer als sechs. 1998 veröffentlichten Duncan J. Watts und Steven Strogatz das erste Small-World-Netzwerkmodell, das mittels eines einzigen Parameters stetig zwischen einem Zufallsgraphen und einem Gitter interpoliert. [ 7 ] Ihr Modell zeigte, dass sich ein regulärer Graph, dessen Durchmesser proportional zur Netzwerkgröße ist, durch das Hinzufügen einer geringen Anzahl von Verbindungen über große Entfernungen in einen „Small-World“-Graphen transformieren lässt. In diesem ist die durchschnittliche Anzahl der Kanten zwischen je zwei Knoten sehr gering (mathematisch gesehen sollte sie mit dem Logarithmus der Netzwerkgröße wachsen), während der Clustering-Koeffizient hoch bleibt. Es ist bekannt, dass viele abstrakte Graphen, z. B. Zufallsgraphen und skalenfreie Netzwerke, diese Small-World-Eigenschaft aufweisen. Auch reale Netzwerke wie das World Wide Web und das metabolische Netzwerk besitzen diese Eigenschaft.

In der wissenschaftlichen Literatur zu Netzwerken herrscht eine gewisse Unklarheit bezüglich des Begriffs „Small World“. Er kann nicht nur den Durchmesser des Netzwerks bezeichnen, sondern auch das gleichzeitige Auftreten eines kleinen Durchmessers und eines hohen Clustering-Koeffizienten . Der Clustering-Koeffizient ist ein Maß für die Dreiecksdichte im Netzwerk. Beispielsweise weisen dünn besetzte Zufallsgraphen einen verschwindend kleinen Clustering-Koeffizienten auf, während reale Netzwerke oft einen deutlich höheren Koeffizienten aufweisen. Wissenschaftler interpretieren diesen Unterschied als Hinweis darauf, dass Kanten in realen Netzwerken korreliert sind. Es wurden Ansätze entwickelt, um Netzwerkmodelle zu generieren, die hohe Korrelationen aufweisen und gleichzeitig die gewünschte Gradverteilung und Small-World-Eigenschaften beibehalten. Diese Ansätze können verwendet werden, um analytisch lösbare Modellmodelle für die Forschung an diesen Systemen zu erstellen. [ 15 ]

räumliche Netzwerke

Viele reale Netzwerke sind räumlich eingebettet. Beispiele hierfür sind Verkehrs- und andere Infrastrukturnetze sowie Hirnnetzwerke. [ 3 ] [ 4 ] Es wurden verschiedene Modelle für räumliche Netzwerke entwickelt. [ 16 ]

Siehe auch

Bücher

  • BS Manoj, Abhishek Chakraborty und Rahul Singh, Komplexe Netzwerke: Eine netzwerk- und signalverarbeitungstheoretische Perspektive , Pearson, New York, USA, Februar 2018. ISBN 978-0-13-478699-5
  • SN Dorogovtsev und JFF Mendes, Evolution of Networks: From biological networks to the Internet and WWW , Oxford University Press, 2003, ISBN 0-19-851590-1
  • Duncan J. Watts, Six Degrees: The Science of a Connected Age , WW Norton & Company, 2003, ISBN 0-393-04142-5
  • Duncan J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness , Princeton University Press, 2003, ISBN 0-691-11704-7
  • Albert-László Barabási, Linked: Wie alles mit allem anderen verbunden ist , 2004, ISBN 0-452-28439-2
  • Alain Barrat, Marc Barthelemy, Alessandro Vespignani, Dynamische Prozesse in komplexen Netzwerken , Cambridge University Press, 2008, ISBN 978-0-521-87950-7
  • Stefan Bornholdt (Hrsg.) und Heinz Georg Schuster (Hrsg.), Handbuch der Graphen und Netzwerke: Vom Genom zum Internet , 2003, ISBN 3-527-40336-1
  • Guido Caldarelli, Scale-Free Networks , Oxford University Press, 2007, ISBN 978-0-19-921151-7
  • Guido Caldarelli, Michele Catanzaro, Networks: A Very Short Introduction Oxford University Press, 2012, ISBN 978-0-19-958807-7
  • E. Estrada, „Die Struktur komplexer Netzwerke: Theorie und Anwendungen“, Oxford University Press, 2011, ISBN 978-0-199-59175-6
  • Mark Newman, Netzwerke: Eine Einführung , Oxford University Press, 2010, ISBN 978-0-19-920665-0
  • Mark Newman, Albert-László Barabási und Duncan J. Watts, The Structure and Dynamics of Networks , Princeton University Press, Princeton, 2006, ISBN 978-0-691-11357-9
  • R. Pastor-Satorras und A. Vespignani, Evolution und Struktur des Internets: Ein statistisch-physikalischer Ansatz , Cambridge University Press, 2004, ISBN 0-521-82698-5
  • T. Lewis, Netzwerkforschung, Wiley 2009,
  • Niloy Ganguly (Hrsg.), Andreas Deutsch (Hrsg.) und Animesh Mukherjee (Hrsg.), Dynamik komplexer Netzwerke: Anwendungen in Biologie, Informatik und Sozialwissenschaften , 2009, ISBN 978-0-8176-4750-6
  • Vito Latora, Vincenzo Nicosia, Giovanni Russo, Komplexe Netzwerke: Prinzipien, Methoden und Anwendungen , Cambridge University Press, 2017, ISBN 978-1-107-10318-4

Referenzen

  1. ^ R. Albert und A.-L. Barabási (2002). „Statistische Mechanik komplexer Netzwerke“. Reviews of Modern Physics . 74 (1): 47–49 . arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . S2CID 60545 . 
  2. ^ Mark Newman (2010). Netzwerke: Eine Einführung . Oxford University Press. ISBN 978-0-19-920665-0Die
  3. ^ a b Bassett, Danielle S; Sporns, Olaf (2017-02-23). ​​„Netzwerk-Neurowissenschaft“ . Nature Neuroscience . 20 (3): 353–364 . doi : 10.1038/nn.4502 . ISSN 1097-6256 . PMC 5485642. PMID 28230844 .   
  4. ^ a b Alex Fornito. „Einführung in die Netzwerk-Neurowissenschaft: Wie man Konnektome erstellt, modelliert und analysiert – 08:00–10:00 | OHBM“ . pathlms.com . Abgerufen am 11.03.2020 .
  5. ^ T. Wilhelm, J. Kim (2008). „Was ist ein komplexer Graph?“. Physica A. 387 ( 11): 2637–2652 . Bibcode : 2008PhyA..387.2637K . doi : 10.1016/j.physa.2008.01.015 .
  6. ^ a b A. Barabási, E. Bonabeau (2003). „Scale-Free Networks“. Scientific American . 288 (5): 50–59 . Bibcode : 2003SciAm.288e..60B . doi : 10.1038/scientificamerican0503-60 . PMID 12701331 . 
  7. ^ a b c d S. H. Strogatz, DJ Watts (1998). „Kollektive Dynamik von ‚Small-World‘-Netzwerken“. Nature . 393 ( 6684): 440–442 . Bibcode : 1998Natur.393..440W . doi : 10.1038/30918 . PMID 9623998. S2CID 4429113 .  
  8. ^ H. E. Stanley, L. A. Amaral, A. Scala, M. Barthélemy (2000). „Klassen von Small-World-Netzwerken“ . PNAS . 97 (21): 11149–52 . arXiv : cond-mat/0001458 . Bibcode : 2000PNAS...9711149A . doi : 10.1073/ pnas.200327197 . PMC 17168. PMID 11005838 .  
  9. ^ Saleh, Mahmoud; Esa, Yusef; Mohamed, Ahmed (2018-05-29). „Anwendungen der komplexen Netzwerkanalyse in elektrischen Energiesystemen“ . Energies . 11 (6): 1381. doi : 10.3390/en11061381 .
  10. ^ A. E. Motter, R. Albert ( 2012). „Netzwerke in Bewegung“ . Physics Today . 65 (4): 43–48 . arXiv : 1206.2369 . Bibcode : 2012PhT....65d..43M . doi : 10.1063/pt.3.1518 . S2CID 12823922 . {{cite journal}}: CS1 maint: deprecated archival service (link)
  11. Johnson S, Domínguez-García V, Donetti L, Muñoz MA (2014). „Trophische Kohärenz bestimmt die Stabilität von Nahrungsnetzen“ . Proc Natl Acad Sci USA . 111 (50): 17923–17928 . arXiv : 1404.7728 . Bibcode : 2014PNAS..11117923J . doi : 10.1073 / pnas.1409077111 . PMC 4273378. PMID 25468963 .  
  12. ^ SGHofmann, JECurtiss (2018). „Ein komplexer Netzwerkansatz für die klinische Wissenschaft“ . European Journal of Clinical Investigation . 48 (8) e12986. doi : 10.1111/eci.12986 . PMID 29931701 . 
  13. ^ Mouhamed Abdulla (22.09.2012). Grundlagen der stochastischen räumlichen Modellierung und Analyse drahtloser Netzwerke und deren Auswirkungen auf Kanalverluste . Dissertation, Fakultät für Elektrotechnik und Informatik, Concordia University, Montréal, Québec, Kanada, September 2012. (Dissertation). Concordia University. S. (Kapitel 4 entwickelt Algorithmen zur Generierung und Visualisierung komplexer Netzwerke). Archiviert vom Original am 09.10.2016 . Abgerufen am 11.10.2013 .
  14. ^ R. Albert und A.-L. Barabási (2002). „Statistische Mechanik komplexer Netzwerke“. Reviews of Modern Physics . 74 (1): 47–97 . arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . ISBN 978-3-540-40372-2. S2CID  60545 .
  15. ^ A. Ramezanpour, V. Karimipour, A. Mashaghi, Generierung korrelierter Netzwerke aus unkorrelierten Netzwerken. Physical Review E 67(4 Pt 2):046107 (2003) doi: 10.1103/PhysRevE.67.046107
  16. ^ Waxman BM (1988). „Routing von Mehrpunktverbindungen“. IEEE J. Sel. Areas Commun . 6 (9): 1617–1622 . doi : 10.1109/49.12889 .