Powrót
Teoria, symulacje numeryczne i wybrane zastosowania sieci złożonych o strukturze blokowej
Abstract
The dissertation is devoted to complex networks with community structure. We discuss models of such networks, which have been developed based on the idea of exponential random graphs. We also study percolation phenomenon in the simplest of these models, i.e. in the classical block model. An attempt to analyze real networks with community structure is also discussed. More precisely, the statistical analysis of two semantic networks: Polish and English wordnets, is shown. In relation to these networks, the problem of interlanguage synonymy is considered, which allows to treat them as modules of a larger network, which contains many autonomous semantic networks corresponding to individual European languages. In the first chapter we discuss the research purpose of the dissertation and specify the author’s contribution in obtaining the results. In the second chapter, entitled Exponential random graph models for networks with community structure, we discuss the approach to modeling complex networks which exploits the idea of statistical ensembles, which is borrowed from equilibrium statistical physics. In these models, the structural properties of the network are defined by the so-called structural network hamiltonian. So far, this method was used only for simple networks, e.g. classical random graphs or random graphs with a given node degree distribution (i.e. configuration models). In this thesis, the method is applied to networks with community structure. We have found structural hamiltonians and studied properties of the classical block model and its degree-corrected counterpart and study many of their properties analytically. We show that in the degree-corrected blockmodel, node degrees display an interesting scaling property, which is reminiscent of what is observed in real-world fractal networks. A short description of Monte Carlo simulations of the models is also given in the hope of being useful to others working in the field. In the third chapter of the thesis, entitled Percolation in the classical blockmodel, percolation transition in the simplest among models of networks with community structure is examined. We derive the self-consistent equation for the size the global percolation cluster in the classical blockmodel. We also find the condition for percolation threshold which characterizes the emergence of the giant component. We show that the discussed percolation phenomenon may cause unexpected problems in a simple optimization process of the multilevel network construction. Numerical simulations confirm the correctness of our theoretical derivations. In the fourth chapter, entitled Comparison of properties of Polish and English wordnets, semantic language networks are discussed. Wordnets are semantic networks containing nouns, verbs, adjectives, and adverbs organized according to linguistic principles, by means of semantic relations. In this work, we adopt a complex network perspective to perform a comparative analysis of the English and Polish wordnets. We determine their similarities and show that the networks exhibit some of the typical characteristics observed in other real-world networks. We analyse interlingual relations between both wordnets and deliberate over the problem of mapping the Polish lexicon onto the English one. Finally, in the fifth chapter, all the results are summarized and perspectives for further research is outlined.- Identyfikator pozycji
- WUT8798521a3f8b428b9a7586aa39858097
- Rodzaj dyplomu
- Praca doktorska
- Autor
- Tytuł w języku polskim
- Teoria, symulacje numeryczne i wybrane zastosowania sieci złożonych o strukturze blokowej
- Język
- (pl) polski
- Jednostka dyplomująca
- Wydział Fizyki (WF)
- Dyscyplina nauki
- fizyka / dziedzina nauk fizycznych / obszar nauk ścisłych
- Status pracy
- Obroniona
- Data nadania stopnia
- 22-12-2016
- Promotor
- Recenzenci zewnętrzni
- Paginacja
- 81
- Słowa kluczowe w języku polskim
- x
- Streszczenie w języku polskim
- Przedmiotem rozprawy są sieci złożone o strukturze modułowej. W rozprawie omówiono modele takich sieci, które zostały opracowane w oparciu o ideę wykładniczych grafów przypadkowych. Zbadano zjawisko perkolacji w najprostszym z tych modeli, tzw. klasycznym modelu blokowym. W końcu, podjęto próbę analizy rzeczywistych sieci o strukturze modułowej. Analizie poddano sieci językowe (semantyczne): polską Słowosieć oraz angielski Wordnet, przy czym, w odniesieniu do tych sieci, rozważano również problem synonimii międzyjęzykowej, która pozwala traktować te sieci, jak moduły większej sieci, tzw. EuroWordnetu, zawierającego wiele autonomicznych sieci semantycznych odpowiadających poszczególnym językom europejskim. W rozdziale pierwszym omówiono celu naukowy rozprawy i wkład doktoranta w uzyskanie przedłożonych wyników badań. W rozdziale drugim, zatytułowanym Wykładnicze grafy przypadkowe dla sieci ze strukturami blokowymi, omówiono podejście do modelowania sieci złożonych wykorzystujące, znaną z równowagowej fizyki statystycznej, ideę zespołów. W modelach tych, własności strukturalne sieci są określone przez podanie tzw. strukturalnych hamiltonianów sieciowych, przy czym sama metoda była dotychczas stosowana jedynie do modelowania prostych układów sieciowych, np. klasycznych grafów przypadkowych, czy grafów o zadanym rozkładzie stopni węzłów (tj. modeli konfiguracyjnych). W niniejszej rozprawie metodę tę zastosowano do sieci ze strukturami blokowymi. Określono hamiltoniany sieciowe i zbadano własności zespołów takich, jak klasyczny model blokowy oraz model blokowy realizujący z góry zadane rozkłady wielkości klasterów i stopni węzłów. Zbadano własności sieci w zaproponowanych zespołach. Ważną i dość nieoczekiwaną obserwacją uzyskaną przy wykorzystaniu tego podejścia, jest analityczny wynik pokazujący, że w modelach blokowych z korekta˛ na stopnie węzłów, usieciowienie węzłów wewnątrz i na zewnątrz modułów, spełnia podobną relację skalowania do tej, jaką obserwuje się we fraktalnych sieciach złożonych, i która była dotychczas uważana za bezpośrednią konsekwencję fraktalności. W rozdziale trzecim rozprawy, zatytułowanym Perkolacja w klasycznym modelu blokowym, przeanalizowano zjawisko perkolacji w najprostszym modelu sieci o strukturze blokowej. Perkolacja ma charakter ciągłej przemiany fazowej, która polega na tym, że w sieciach mających odpowiednio dużą gęstość połączeń, wyższą od pewnej krytycznej gęstości, zwanej progiem perkolacji, pojawia się tzw. klaster perkolacyjny skupiający makroskopową ilość węzłów sieci. W rozdziale trzecim rozprawy wyznaczono warunek określający próg perkolacji w klasycznym modelu blokowym oraz opracowano uwikłane równanie, którego rozwiązaniem jest rozmiar klastera perkolacyjnego, będącego również parametrem porządku badanej przemiany fazowej. Ponadto, uzyskane wyniki wykorzystano do stworzenia prostego modelu optymalizacji stosunku kosztów i zysków wynikających z budowy i utrzymania modułowych sieci dystrybucyjnych. W rozdziale czwartym rozprawy, zatytułowanym Porównanie własności polskiej słowosieci i angielskiego wordnetu, analizowane były semantyczne sieci językowe. Węzłami tych sieci są synsety, tzn. zbiory słów o jednakowym znaczeniu, które są ze sobą połączone za pomocą różnych relacji językowych, np. hiperonimii, meronimii, fuzynimii, synonimii międzyjęzykowej itd. Pierwszą na świecie tego typu siecią był leksykon języka angielskiego utworzony na Uniwersytecie w Princeton, tzw. Princeton WordNet (PWN). Polska słowosieć (PolWN) zaczęła powstawać w 2005 roku na Politechnice Wrocławskiej i wciąż jest w fazie tworzenia. Proces ten trwa tak długo ponieważ nie jest zautomatyzowany. Podstawowym celem analiz przedstawionych w czwartym rozdziale rozprawy było porównanie własności angielskiej i polskiej sieci semantycznej i wykrycie nietrywialnych zależności miedzy tymi sieciami, które ułatwiłyby rozbudowę połączeń´ pomiędzy polskim i angielskim wordnetem, poprzez tłumaczenia automatyczne lub półautomatyczne. Działania tego typu są nie tylko istotne ze względu na rozwój polskiej słowosieci. Są one ważne w szerszym kontekście, ponieważ kształtują świadomość różnic międzyjęzykowych, które w istotny sposób wpływają na różnorakie procesy związane z przetwarzaniem języków naturalnych. Wspomniany cel został zrealizowany jedynie częściowo. Porównano podstawowe charakterystyki strukturalne wordnetów polskiego i angielskiego oraz zbadano przydatność miary, zwanej supremacją węzłową, w celu wykorzystania jej do automatyzacji tworzenia połączeń synonimii międzyjęzykowej. W rozdziale piątym rozprawy podsumowano uzyskane wyniki i nakreślono perspektywę dalszych badań.
- Plik pracy
-
- Plik: 1
- Bujok.pdf
-
- Jednolity identyfikator zasobu
- https://repo.pw.edu.pl/info/phd/WUT8798521a3f8b428b9a7586aa39858097/
- URN
urn:pw-repo:WUT8798521a3f8b428b9a7586aa39858097