Štúdium komplexných sietí v poslednom desaťročí zažíva neobyčajný záujem vedcov a inžinierov z odlišných odvetví života. Zdá sa, že táto nová veda naberie ešte viac na dôležitosti v nastávajúcich rokoch najmä vďaka novým poznatkom a využitiu informačných technológií. Mnohé popredné svetové univerzity a výskumné inštitúty vynakladajú čoraz viac prostriedkov pre dosiahnutie významných úspechov v tejto problematike. V nasledujúcej práci priblížime problematiku komplexných sietí a popíšeme hlavné pojmy.

1. Úvod

Sieť smerovačov tvoriacich obrovskú štruktúru s názvom Internet, telefónna sieť, interakcia medzi počítačmi, ktoré sú napadnuté vírusom alebo ktoré iba spoločne kooperujú za účelom napomáhania k vedeckým objavom, chemické väzby medzi bunkami v prírode, sociálne väzby medzi ľuďmi, interakcie medzi webovými stránkami alebo službami, všetky spomenuté prípady majú spoločnú vlastnosť. V každom z nich sa pri širšom pohľade pozeráme na sieť určitých prvkov, ktoré sú vzájomne pospájané a ktoré určitým spôsobom navzájom komunikujú.

2. Od Eulera po mocninnú funkciu

Teória grafov sa zrodila už pred 275 rokmi. Obyvatelia vtedajšieho Königsbergu (dnešný Kaliningrad) si kládli otázku, ktorú nikto nevedel vyriešiť. Je možné nájsť takú cestu cez všetkých sedem mostov Königsbergu, ktorá by neobsahovala prechod cez niektorý z mostov dva krát? Odpoveď na túto otázku našiel a matematicky dokázal až známy matematik Leonard Euler v roku 1736. Predložil dôkaz, ktorý potvrdil dohady, že v prípade siedmych mostov takú cestu nie je možné nájsť. Jeho dôkaz však znamenal viac ako len vyriešenie Konigsberského hlavolamu. Vo svojom článku totiž načrtol základy nového matematického oboru – teórie grafov.

O 223 rokov neskôr, v roku 1959 publikovali Paul Erdõs a Alfréd Rényi prácu s názvom „On Random Graphs“, ktorá je pokladaná za jednu z najvýznamnejších prác týkajúcich sa štúdiom náhodných grafov. Teória náhodných grafov, ako bola pomenovaná sa neskôr stala základným kameňom štúdia komplexných sietí.

Model, ktorý Erdõs s Rényim navrhli pozostáva z n uzlov ktoré sú navzájom pospájané hranami tak, že tieto hrany sú náhodne priradené spojeniu medzi niektorými uzlami. Erdõs s Rényim navrhli niekoľko verzii náhodných grafov. V najvýznamnejšom z nich, ktorý je označovaný ako G_n,p sa predpokladá, že každá možná hrana, ktorá bude v grafe spájať dva uzly, sa v grafe objaví s pravdepodobnosťou p, a naopak hrana, ktorá v grafe nevystupuje má priradenú pravdepodobnosť 1-p.

Charakteristickým zobrazením vlastností takto zostrojeného grafu je priemerný stupeň uzla označovaný písmenom z. Stupňom uzla nazývame číslo, ktoré vyjadruje počet hrán pripojených do daného uzla. V modeli náhodného grafu sa dá vyjadriť priemerný stupeň uzla ako z≈np. Zo štúdia náhodných grafov vyplýva, že táto aproximácia je tým presnejšia, čím je n väčšie.

Distribúcia stupňov jednotlivých uzlov v sieti náhodných grafov je len jedným z mnohých parametrov, ktoré je možné vypočítať. Zaujímavé je, že tak ako pri tejto charakteristike aj pre ostatné platí, že výsledné výpočty sú presnejšie pre väčšie n. Ďalším významným parametrom je tzv. gigantický komponent.

Gigantický komponent vzniká vytvorením tak pospájanej štruktúry uzlov, že obsahuje majoritnú časť celého pôvodného grafu. V súvislosti s vytváraním gigantického komponentu je zaujímavé sledovať hraničnú hodnotu, pri ktorej sa v náhodnom grafe takýto prvok objaví. Teória, ktorá popisuje tento jav sa nazýva perkolačná teória (Percolation Theory).

Skúmaním sietí v reálnom prostredí sa prišlo na to, že model, ktorým Erdõs a Rényi popisovali náhodné grafy nie je úplne použiteľný pre skúmanie reálnych sietí akými sú napríklad chemické reakcie buniek, štruktúra telefónnej siete, sociálne väzby ľudí či potravinové reťazce v prírode. Samotní autori v práci „On the evolution of random graphs“ prikladajú poznámku:

„Samozrejme, ak by niekto popisoval modelom reálnu situáciu musel by nahradiť hypotézu o ekvivalentnej pravdepodobnosti pripojovania všetkých uzlov realistickejšou hypotézou.“

Významnú úlohu zohrala v počiatkoch vytvárania vedy o sieťach sociológia. Práve v sociológii sa pomocou sledovania medziľudských väzieb v sedemdesiatich rokoch minulého storočia podarilo znovuobjaviť fenomén, ktorý predpovedal už o tridsať rokov skôr maďarský spisovateľ Frigyes Karinthy. Stanley Milgram, profesor na Harvarde pokusom overil, že náhodne vybraný človek na planéte je s iným náhodne vybraným človekom vzdialený v priemere na šesť krokov od seba (jeden krok znamená jednu sociálnu väzbu – známosť).

Toto číslo je vzhľadom k tomu, že na svete žije skoro 7 miliárd ľudí veľmi malé. Postupnou dostupnosťou informačných technológií koncom minulého storočia bola táto vlastnosť sledovaná aj pri štruktúrach sietí v iných odvetviach. Tento fenomén dostal pomenovanie efekt malého sveta (Small world effect).

Tab. 1. Porovnanie parametrov rôznych typov sietí. Počet uzlov n, priemerný stupeň uzla z. Čísla sú prebrané z ^a Pastor-Sattoras a kol. (2001), ^b Adamic (1999), ^c Watts and Strogatz (1998), ^d Newman (2001b), ^e Newman (2001d), ^f Newman a kol. (2001), ^g i Cancho a Solé (2001), ^h Montoya a Solé (2001), ⁱ Fell and Wagner (2000).

Sieť a	n	z
Internet (autonómny systém) a	6374	3.8
World-Wide Web (webové stránky) b	153127	35.2
Energetická sieť c	4941	2.7
Referencie prác v biológii d	1520251	15.5
Referencie prác v matematike e	253339	3.9
Spolupráca filmových hercov f	449913	113.4
Riaditelia spoločností f	7673	14.4
Opakovanie slov v texte g	460902	70.1
Neurónová sieť c	282	14
Metabolická sieť h	315	28.3
Potravinová sieť i	134	8.7

Zdroj: Random graphs as models of networks, M. E. J. Newman [3]

Sieť a	Zhlukovací koeficient C
	Namer.	počitaný pomocou modelu náhodného grafu
Internet (autonómny systém) a	0.24	0.0006
World-Wide Web (webové stránky) b	0.11	0.00023
Energetická sieť c	0.08	0.00054
Referencie prác v biológii d	0.081	0.00001
Referencie prác v matematike e	0.15	0.000015
Spolupráca filmových hercov f	0.2	0.00025
Riaditelia spoločností f	0.59	0.0019
Opakovanie slov v texte g	0.44	0.00015
Neurónová sieť c	0.28	0.049
Metabolická sieť h	0.59	0.09
Potravinová sieť i	0.22	0.065

Jednými z prvých, ktorí sa pokúsili priblížiť modelovanie sietí reálnym parametrom komplexných sietí boli Duncan J. Watts a Steven Strogatz. Prišli na to, že model náhodných grafov, navrhovaný Erdõsom a Rényim nezohľadňuje dve významné charakteristiky reálnych komplexných systémov.

Prvým rozdielom bola hodnota koeficientu zhlukovania (Clustering Coeficient) a s tým súvisiace zhlukovanie uzlov. Koeficient zhlukovania určuje pomer medzi počtom trojuholníkov v sieti prenásobený konštantou a počtom pripojených trojíc. Vyjadruje priemernú pravdepodobnosť, že dva uzly, ktoré sú susedmi s tým istým uzlom budú aj navzájom susedmi.

(1)

Watts so Strogatzom určili alternatívnu cestu výpočtu koeficientu zhlukovania tak, aby bolo možné sledovať zhlukovanie v sieti lokálne.

(2)

Potom pre výpočet priemerného koeficientu zhlukovania platí

(3)

V modeli náhodných grafov sa zhlukovanie uzlov neprejavovalo v takej miere ako pri reálnych sieťach. Príčinou tohto faktu bola práve vlastnosť náhodných grafov, podľa ktorej hrany medzi uzlami vznikajú s konštantne stanovenou pravdepodobnosťou. Druhým výrazným rozdielom bola distribúcia stupňov uzlov grafu. Kým v prípade náhodných grafov mala distribúcia Poissonove rozdelenie, v prípade reálnych sietí sa sledovaním zistila mocninná charakteristika.

3. Využitie teórie v praxi

Pri pohľade na sieť smerovačov, ktoré sú základným prvkom v sieti Internet alebo na štruktúru siete zostavenú z odkazov internetových stránok zisťujeme, že tieto siete nevznikajú spôsobom aký je predpokladaný v modeli náhodných grafov. Na to, aby mohli byť smerovače v sieti navzájom spájané úplne náhodne by sme museli zanedbať geografickú polohu a teda vzdialenosti akýchkoľvek dvoch smerovačov v sieti navzájom čo je v praxi nedosiahnuteľné.

Namiesto toho sú smerovače pripojované preferenčne k vybraným uzlom. Podobný scenár možno sledovať aj pri pohľade na sieť odkazov jednotlivých stránok World Wide Webu. Kým na jednej strane existuje veľmi veľa stránok, ktoré sa odkazujú na zopár ďalších, na druhej strane možno nájsť centrá akými sú napríklad vyhľadávacie služby Google či Yahoo, ktorých počet je malý, ale spájajú nespočetne veľa iných stránok.

Významný posun vo vnímaní komplexných systémov nastal vďaka práci Alberta Lászla Barabásiho a jeho kolegov Ginestre Bianconiovej a Hawoonga Jeonga. Pomocou webového robota zozbierali informácie o malej frakcii siete WWW a sledovali prepojenie jednotlivých webových stránok. Zhrnutie ich výskumu publikoval A-L Barabási v knižnej podobe pod jednoduchým názvom Linked (V českom preklade – V pavučině síťí).

Spomenutí autori zistili, že aj odkazy umiestnené na webových stránkach a ich prepojenie vykazuje vlastnosti mocninnej funkcie čo sa týka distribúcie počtu pripojení. Autor v knihe toto zistenie popisuje nasledovne:

„Mocninné zákony sa zriedkavo objavujú v systémoch, ktoré sú ovládané výhradne náhodne tzv. hodom kockou. Fyzici zistili, že najčastejšie sú signálom prechodu z neusporiadanosti k usporiadanému radu.“

Neskôr zistenia zhodnotil nasledovne:

„Prvý krát sme tak mohli prehlásiť, že snáď existujú zákony skrývajúce sa za komplexnými systémami.“

V oblasti komplexných systémov od vtedy vznikli ďalšie modely, ktoré sa snažia priblížiť fungovanie týchto zložitých sietí. Bolo publikovaných mnoho prác, ktoré napomohli k objavom v rôznych oblastiach. Z pohľadu Telekomunikácii stojí za zmienku spomenúť prácu troch bratov Faloutsov, ktorí skúmali vlastnosti mocninnej funkcie distribúcie internetových smerovačov na úrovni autonómnych systémov. Zaujímavou prácou je taktiež „Meranie odolnosti komplexných sietí simulovaním DDoS útokov“ od Igora Mishkovského a kol. z univerzity Sv. Cyrila a Metóda v Skopje.

Napriek týmto a mnohým ďalším úspešným prácam ostáva táto problematika stále neprebádaná. Viacerí autori, ktorí popisujú teóriu sietí sa zhodujú v tom, že tieto teoretické vedomosti sú značne rozpracované v súčasnosti až po úroveň sledovania topológie sietí. Predpokladá sa, že ďalší výskum bude popisovať práve dynamiku jednotlivých systémov. Našou ambíciou je využiť nadobudnuté vedomosti v nasledujúcom období a aplikovať ich na špecifický problém v komunikačných technológiách.

4. Literatúra

1. Barabási, A-L, “V pavučině sítí”, Paseka, 2005
2. Van der Hofstad, R, “Random Graphs and Complex Networks”, 2009, Dostupné z
   http://www.win.tue.nl/~rhofstad/NotesRGCN2009.pdf
3. Newman, M. E. J., “Random graphs as models of networks”, Dostupné z
   http://www.santafe.edu/media/workingpapers/02-02-005.pdf
4. Barabási, A-L, “The physics of the Web”, Physics World, 2001, pp. 33-38
5. Newman, M. E. J., “The structure and function of complex networks”, Dostupné z
   http://www-personal.umich.edu/~mejn/courses/2004/cscs535/review.pdf
6. Mishkovski, I, et. al., “Measuring Vulnerability of Complex Networks by Simulating DDoS Attacks”, 18th Telecommunications forum TELFOR 2010, pp. 127-130

---

Spoluautorom článku je prof. Ing. Ivan Baroňák, PhD., Katedra telekomunikácii, Fakulta elektrotechniky a informatiky, Slovenská technická univerzita, Ilkovičova 3, 812 19 Bratislava

---

Práca bola prezentovaná na Študentskej vedeckej a odbornej činnosti (ŠVOČ 2011) v sekcii Telekomunikácie V a získala cenu ČS sekcie IEEE, ISBN 978-80-227-3508-7