Sieci bezskalowe – bezpieczeństwo i zastosowania

Abstract

Naturalnym kierunkiem badań informatyki teoretycznej jest badanie sieci przy pomocy ich teoretycznych modeli grafowych. Przykładem takich sieci są sieci bezskalowe. Ich koncepcja wywołała w ostatnich latach spore zainteresowanie, ponieważ wiele rzeczywistych sieci ma istotnie cechy bezskalowości np. internet. Celem rozprawy jest analiza w/w sieci. Istotną częścią pracy są wyniki teoretyczne (twierdzenia, lematy, itp.) dotyczące podstawowych problemów bezpieczeństwa w sieciach bezskalowych. W pracy rozważany jest problem spójności grafów bezskalowych, a dokładnie problem izolacji wierzchołka. Drugi istotny aspekt bezpieczeństwa sieci bezskalowych, który poruszany jest w pracy to szybkość rozprzestrzeniania się plotki. Plotka to podstawowy mechanizm rozpowszechniania się informacji w sieci. W rozprawie analizowana jest zależność między stopniami wierzchołków a ich wysokościami, co bez wątpienia ma wpływ na szybkość rozprzestrzeniania się plotki. Testowanie bezskalowości sieci rzeczywistych sprawia wielu badaczom problemy. W rozprawie zaprezentowane są dotychczas używane metody od najmniej do najbardziej wiarygodnych. Każda z nich poddana jest analizie i omawiane są ich słabe punkty. Następnie prezentowana jest nowa metoda bazująca na poprzednich, ale eliminująca ich wady. Istotnym zagadnieniem w dziedzinie sieci bezskalowych jest zastosowanie ich w rzeczywistym świecie do konkretnych celów. Jednym z nich jest prognozowanie zachowań cen akcji na rynkach finansowych. W pracy wprowadzane są m.in. modele rynku akcji posiadające właściwości grafów bezskalowych. One of the field of theoretical computer science is the study of the network using graph theoretical models. An example of such networks are scale-free networks. Their concept raised in recent years a lot of interest, because many real networks have scale-free features e.g. internet. The aim of the dissertation is an analysis of these networks. The important part of the dissertation are theoretical results (theorems, lemmas, etc.) which concern basic security problems in scale-free networks. In the second chapter is considered the connectivity of scale-free graphs, namely the vertex isolation problem. Another important problem of scale free-network security is the rate of spreading rumors. In the second chapter is analyzed the relationship between degrees of vertices and their heights which undoubtedly has an impact on the speed of the spread of rumors. Testing whether a real network is scale-free makes a lot of trouble. In the dissertation are presented methods used so far. At the end is presented the new method based on previous methods but eliminating their defects. Scale-free networks are used in the real world, e.g. to forecasting stock prices in financial markets. The fourth chapter deals with this problem. Stock market models, which have properties of scale-free graphs, are described.