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. W badaniach nad sieciami złożonymi uczestniczą naukowcy z wielu dziedzin, m.in.: matematyki, fizyki, biologii, informatyki, socjologii, epidemiologii.
Historia W roku 1959 węgierscy matematycy Paul Erdős i Alfréd Rényi zaproponowali model grafów losowych.. 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 WWW 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. W badaniu przeprowadzonym w 2000 roku na 50 milionach stron wielkość ta wynosiła 16.
Przypisy
Bibliografia
Kategoria:Klasy grafów