Comparison of models of complex networks used to test algorithms for detecting community structure

Mateusz Witold Kowalczyk

Abstract

In recent years, in the field of complex networks often emerging research topic is a community structure. Indeed, this feature may be responsible for many important properties of real networks, hence the appearance of scientific papers and publications on this subject is not surprising. Community structure of the network is that, of all the vertices (nodes) of the network can be divided into those having more connections between each other than with other nodes. More specifically, the vertices can be grouped, in which the density of the connections between the nodes is greater than the density of connections of nodes to other nodes. The aim of this thesis was to compare the efficiency of numerical algorithms to generating networks according to two models of complex networks with a community structure that can be used to test algorithms for detecting community structure. The first model of the network, which is addressed in this thesis, was based on the classical method of iterative annealing described in A. Lancichinetti, S. Fortunato, F. Radicchi. Benchmark graphs for testing community detection algorithms. (Phys. Rev. E 78: 046110, 2008). The Authors of the paper published a source code of their program which they used for simulating such a network and this was used in this thesis. The second model was based on the idea of exponential random graphs described in the publication of P. Fronczak, A. Fronczak, M. Bujok. Exponential random graph models for networks with community structure. (Phys. Rev. E 88: 032810, 2013). Using their results and simplifying formulas for the probability of an edge existance we wrote a program generating community networks based on accidental graphs. The source code is available on the Internet. Each of the two analysed algorithms generating community networks has its own benefits and drawbacks. This is why one cannot determine which one of them is generally better than the other. Their relationship and characteristics was further studied in this thesis and it was proven that when choosing a proper algorithm one should consider a trade-off between accuracy and speed of computation. Moreover, one has to be cautious that in some applications the drawbacks of the two presented algorithms cannot be accepted. The main benefits of the algorithm based on exponential random graphs is its speed and simplicity, as compared to the second algorithm. Moreover, one can find an analytic description of the model. On the other hand, the second model based on iterative annealing is far more accurate. Complex networks generated using this algorithm have no zero degree nodes and variance between the resulted and sampled, expected degrees of nodes is strongly reduced. Results obtained in this thesis were published as: M. Kowalczyk, P. Fronczak, A. Fronczak. A new algorithm for reproducing complex networks with community structure. (arXiv: 1608.08609).
Diploma typeMaster of Science
Author Mateusz Witold Kowalczyk (FP)
Mateusz Witold Kowalczyk,,
- Faculty of Physics
Title in PolishPorównanie modeli sieci złożonych wykorzystywanych do testowania algorytmów służących do wykrywania struktur społecznościowych
Supervisor Agata Fronczak (FP / PCSD)
Agata Fronczak,,
- Physics of Complex Systems Divison

Certifying unitFaculty of Physics (FP)
Affiliation unitPhysics of Complex Systems Divison (FP / PCSD)
Study subject / specializationFizyka Techniczna
Languagepl polski
StatusFinished
Defense Date09-03-2017
Issue date (year)2017
Reviewers Tomasz Gradowski (FP / PCSD)
Tomasz Gradowski,,
- Physics of Complex Systems Divison
, Agata Fronczak (FP / PCSD)
Agata Fronczak,,
- Physics of Complex Systems Divison
Keywords in Polishsieci złożone, struktura modułowa (blokowa), klasyczna metoda iteracyjnego wyżarzania, model blokowy Lancichinetti'ego, wykładnicze grafy przypadkowe, model blokowy z korektą na stopnie węzłów
Keywords in Englishcomplex networks, community structure, exponential random graphs, algorithms
Abstract in PolishW ostatnich latach często pojawiającym się tematem badań w dziedzinie sieci złożonych jest struktura społecznościowa (modułowa, blokowa). Istotnie, cecha ta może odpowiadać za wiele ważnych własności sieci rzeczywistych, dlatego nie dziwi pojawianie się prac naukowych i publikacji o tej tematyce. Struktura modułowa sieci oznacza, że spośród wszystkich wierzchołków (węzłów) sieci można wyróżnić takie, które mają więcej połączeń między sobą niż z innymi węzłami. Mówiąc ściślej, wierzchołki można podzielić na grupy, w których gęstość połączeń między węzłami jest większa niż gęstość połączeń tych węzłów z pozostałymi węzłami. Celem niniejszej pracy magisterskiej było porównanie efektywności algorytmów numerycznych generujących sieci według dwóch modeli sieci złożonych o strukturze modułowej, które można wykorzystywać do testowania algorytmów służących do wykrywania struktury społecznościowej. Pierwszym modelem sieci, który przeanalizowano w niniejszej pracy, był model oparty na klasycznej metodzie iteracyjnego wyżarzania opisany w publikacji A. Lancichinetti, S. Fortunato, F. Radicchi. Benchmark graphs for testing community detection algorithms. (Phys. Rev. E 78:046110, 2008). Autorzy wspomnianej publikacji umieścili w internecie kod źródłowy programu do symulacji takich sieci, który wykorzystano do analizy w niniejszej pracy magisterskiej. Drugim modelem, który przeanalizowano w niniejszej pracy był model oparty na idei wykładniczych grafów przypadkowych opisany w publikacji P. Fronczak, A. Fronczak, M. Bujok. Exponential random graph models for networks with community structure. (Phys. Rev. E 88:032810, 2013). Korzystając z uproszczonych, względem wspomnianej publikacji, wzorów na prawdopodobieństwo istnienia krawędzi napisano program generujący sieci blokowe w ujęciu wykładniczych grafów przypadkowych, którego kod źródłowy umieszczono w internecie. Każdy z dwóch poddanych analizie algorytmów generujących sieci blokowe ma swoje wady i zalety. Z tego powodu nie można jednoznacznie stwierdzić, że jeden z nich jest lepszy od drugiego. Zbadane zależności i wykreślone charakterystyki dowodzą, że przy wyborze algorytmu trzeba rozważyć kompromis pomiędzy dokładnością a szybkością, a także być świadomym, że w pewnych zastosowaniach wady algorytmów mogą być nie do zaakceptowania. Głównymi zaletami algorytmu opartego na idei wykładniczych grafów przypadkowych jest to, że algorytm ten jest znacznie szybszy i prostszy w implementacji oraz można go łatwo opisać analitycznie. Z drugiej strony algorytm oparty na metodzie iteracyjnego wyżarzania jest znacznie bardziej dokładny. W sieciach wygenerowanych tym algorytmem nie ma węzłów o zerowym stopniu, a wariancja między otrzymanymi a wylosowanymi, oczekiwanymi stopniami węzłów jest silnie zredukowana. Wyniki uzyskane w tej pracy zostały spisane w postaci publikacji: M. Kowalczyk, P. Fronczak, A. Fronczak. A new algorithm for reproducing complex networks with community structure. (arXiv: 1608.08609).
File
Praca_magisterska_Mateusz_Kowalczyk.pdf 2.57 MB
Local fieldsIdentyfikator pracy APD: 15494

Get link to the record

Back