Knowledge base: Warsaw University of Technology

Settings and your account

Back

Applet for simulating complex networks with community structure

Jakub Sobolewski

Abstract

The goal of this thesis was to create an applet for visualization of exponential random graphs with power-law node degree distributions and community structure. The application was written in Java with use of library for making graphical user interfaces JavaFX. Basic concepts regarding graph theory and exponential random graph formalism are described. In this formalism one can create a network with arbitrary structural properties, which are represented by a so called structural hamiltonian. Monte Carlo method in use of creating a network with an arbitrary hamiltonian is described. In this work simulated networks have a power-law node degree distribution, so that they represent properties of real world networks well. A development of the model is described. It incorporates community structure in order to better match properties of networks such as social networks. In this model a network is divided into K blocks with N vertices each with connections between blocks. Elements of implementation are presented: ways of representing graphs in computer memory and representation of graphs in space. Force directed algorithm is described in detail. It works well for drawing networks with are simulated in this work, because they have small amount of vertices. Method of generating numbers from power-law distribution is described. In the end, the outcome applet is presented: description of user interface as well as an example of simulation.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Jakub Sobolewski (FP) Jakub Sobolewski,, Faculty of Physics (FP)
Title in Polish
Stworzenie apletu do wizualizacji sieci o strukturze modułowej
Supervisor
Piotr Fronczak (FP/PCSD) Piotr Fronczak,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Certifying unit
Faculty of Physics (FP)
Affiliation unit
Physics of Complex Systems Divison (FP/PCSD)
Study subject / specialization
Fizyka Techniczna
Language
(pl) Polish
Status
Finished
Defense Date
31-01-2019
Issue date (year)
2019
Reviewers
Piotr Fronczak (FP/PCSD) Piotr Fronczak,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP) Maciej Mrowiński (FP/PCSD) Maciej Mrowiński,, Physics of Complex Systems Divison (FP/PCSD)Faculty of Physics (FP)
Keywords in Polish
graf, wizualizacja grafów, sieci złożone, wykładnicze grafy przypadkowe, Monte Carlo, algorytm Metropolisa.
Keywords in English
graph, graph visualization, complex networks, exponential random graphs, Monte Carlo, Metropolis algorithm
Abstract in Polish
Celem pracy było stworzenie aplikacji do wizualizacji wykładniczych grafów przypadkowych o potęgowym rozkładzie stopni wierzchołków i strukturze blokowej. Została ona wykonana w języku Java z wykorzystaniem biblioteki do tworzenia graficznych interfejsów użytkownika JavaFX. Opisano podstawowe pojęcia z teorii grafów oraz formalizmu wykładniczych grafów przypadkowych. W tym formalizmie możliwe jest stworzenie sieci o dowolnych własnościach strukturalnych reprezentowanych przez tak zwany hamiltonian sieci. Zaprezentowano metodę Monte Carlo do symulowania sieci o dowolnym hamiltonianie. W ramach tej pracy wytwarzane sieci określone są przez potęgowy rozkład stopni wierzchołków, który dobrze oddaje własności sieci rzeczywistych. Opisano rozwinięcie modelu wykładniczych grafów przypadkowych, który wprowadza do sieci strukturę blokową, w celu przybliżenia własności modelu do sieci takich jak sieć kontaktów społecznych. W modelu tym sieć jest podzielona na K bloków, po N wierzchołków każdy, a pomiędzy blokami mogą występować krawędzie. Przedstawiono elementy implementacji programu: sposoby reprezentacji grafów w pamięci komputera i ich reprezentacji w przestrzeni. W szczególności opisano algorytm skierowany siłowo, który w przypadku tej pracy znajduje zastosowanie, ponieważ sieci mają niewielką liczbę wierzchołków. Omówiono metodę generacji liczb losowych z rozkładu potęgowego. Na końcu pracy przedstawiono aplikację, opis interfejsu oraz przykładowy wynik symulacji.
File
  • File: 1
    Praca_inżynierska_Jakub_Sobolewski.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 27199

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT6e118b67b20e4c8b89b3341b6ba71496/
URN
urn:pw-repo:WUT6e118b67b20e4c8b89b3341b6ba71496

Confirmation
Are you sure?
Report incorrect data on this page