Sieć złożona
Sieć złożona to graf o nietrywialnych właściwościach topologicznych. Przykłady takich sieci to: WWW, Internet, sieć współpracy pomiędzy aktorami, sieć współpracy pomiędzy naukowcami, sieć kontaktów seksualnych[1]. W badaniach nad sieciami złożonymi uczestniczą naukowcy z wielu dziedzin, m.in.: matematyki, fizyki, biologii, informatyki, socjologii, epidemiologii.
Historia[edytuj | edytuj kod]
W roku 1959 węgierscy matematycy Paul Erdős i Alfréd Rényi zaproponowali model grafów losowych.[2]. Zakładał on, że połączenia w sieci powstają w sposób losowy, dlatego też do ich analizy można używać rachunku prawdopodobieństwa. Był to dominujący model analizy sieci do czasu, aż moc obliczeniowa komputerów pozwoliła na badanie rzeczywistych sieci złożonych. Okazało się, że cechuje je rozkład potęgowy stopni wierzchołka, a nie rozkład dwumianowy, jak to wynikało z modelu grafów losowych. Odkrycie to przypisuje się Albertowi-László Barabási.
Przykłady[edytuj | edytuj kod]
WWW[edytuj | edytuj kod]
Sieć WWW to graf skierowany gdzie wierzchołkami są strony internetowe, a krawędziami hiperłącza łączące dokumenty. Pomimo swoich ogromnych rozmiarów WWW posiada właściwość małego świata. Badanie przeprowadzone w 1999 roku na 325 729 stronach pokazało, że średnia długość ścieżki, czyli ilość hiperłączy łączących dwa dokumenty, wynosiła 11,2[1]. W badaniu przeprowadzonym w 2000 roku na 50 milionach stron wielkość ta wynosiła 16[3].
Przypisy[edytuj | edytuj kod]
- ↑ a b Réka Albert, Albert-László Barabási. Statistical mechanics of complex networks. „Revies of Modern Physics”. 74, s. 47-97, 30 stycznia 2002. (ang.).
- ↑ Paul Erdős, Alfréd Rényi. On Random Graphs I. „Publ. Math. Debrecen”. 6. s. 290-297. (ang.).
- ↑ Andrei Broder i inni, Graph structure in the Web, „Computer Networks”, 33, s. 309-320 (ang.).
Bibliografia[edytuj | edytuj kod]
- Agata Fronczak, Piotr Fronczak: Świat sieci złożonych. Warszawa: Wydaw. Naukowe PWN, 2009. ISBN 978-83-01-15987-0. (pol.).