An Overview of Algorithms for Community Detection in Networks.

licenciate
dc.abstract.enSystems of entities connected by some form of a relationship are omnipresent in our surrounding world. Human circulatory system, the World Wide Web or the food chain are but a few examples of such systems, known as networks. Due to their widespreadness and importance, networks have been a focus of scientific studies for centuries, studies, which have only increased in frequency in recent years. By means of this research several properties of networks have been determined, one of them being the community structure. As it turns out many networks, particularly social ones, tend to consist of communities - groups of entities densely connected with one another, but having relatively few external connections.In this work we present a simple classification of networks, outline their common properties and, focusing on one of them - the community structure, depict several algorithms for community detection and compare their efficiency as well as accuracy. Specifically, we focus on heuristic algorithms maximizing a certain parameter of a network partition known as modularity, high values of which are indicative of a "good" partition, that is one which closely resembles the desired split of a network into communities.The algorithms analyzed are those by Blondel et al., Girvan-Newman, Clauset-Newman-Moore, and hierarchical clustering. They are tested using our own implementations and real-world as well as randomly generated datasets. The tests one-sidedly conclude the superiority of the algorithm by Blondel et al., both in the fields of accuracy and time efficiency.pl
dc.abstract.plSystemy bytów połączonych pewną formą relacji są wszechobecne w otaczającym nas świecie. Układ krążenia, ogólnoświatowa sieć Internetowa, czy łańcuch pokarmowy to tylko kilka przykładów takich systemów, znanych pod nazwą sieci. W związku z ich powszechnością i istotnością, sieci są obiektem badań naukowych od stuleci — badań, które w ostatnich latach tylko przybrały na intensywności. W ich efekcie wyodrębniono liczne własności sieci, a wśród nich strukturę społecznościową. Jak się okazuje, wiele sieci składa się ze społeczności, czyli grup bytów gęsto ze sobą połączonych, ale mających niewiele połączeń zewnętrznych.W mojej pracy prezentuję prostą klasyfikację sieci, przedstawiam ich charakterystyczne własności i koncentrując się na jednej z nich — strukturze społecznościowej — opisuję kilka algorytmów detekcji społeczności w sieciach, a także porównuję ich wydajność i dokładność. Konkretniej, skupiam się na heurystycznych algorytmach maksymalizujących pewien parametr podziału sieci, znany jako modularność, której wysokie wartości są typowe dla "dobrych" podziałów, czyli takich, które cechuje duże podobieństwo z pożądanym podziałem sieci na społeczności.Porównywane algorytmy to: algorytm Blondela et al., algorytm Girvan-Newmana, algorytm Clauseta-Newmana-Moore'a oraz hierarchiczne klastrowanie. Testuję je, używając własnych implementacji oraz danych ze świata rzeczywistego, jak również generowanych losowo. Przeprowadzone testy jednoznacznie orzekają o wyższości algorytmu Blondela et al., zarówno w obszarze dokładności, jak i wydajności.pl
dc.affiliationWydział Matematyki i Informatykipl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorCieślik, Iwona - 141986 pl
dc.contributor.authorSłoczyński, Adampl
dc.contributor.departmentbycodeUJK/WMI2pl
dc.contributor.reviewerCieślik, Iwona - 141986 pl
dc.contributor.reviewerŚlusarek, Maciej - 132329 pl
dc.date.accessioned2020-07-27T22:51:15Z
dc.date.available2020-07-27T22:51:15Z
dc.date.submitted2019-07-09pl
dc.fieldofstudyinformatyka analitycznapl
dc.identifier.apddiploma-131246-209257pl
dc.identifier.projectAPD / Opl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/234061
dc.languageengpl
dc.subject.ennetwork, graph, community, modularity, algorithm, implementationpl
dc.subject.plsieć, graf, społeczność, modularność, algorytm, implementacjapl
dc.titleAn Overview of Algorithms for Community Detection in Networks.pl
dc.title.alternativeAn Overview of Algorithms for Community Detection in Networkspl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
Systems of entities connected by some form of a relationship are omnipresent in our surrounding world. Human circulatory system, the World Wide Web or the food chain are but a few examples of such systems, known as networks. Due to their widespreadness and importance, networks have been a focus of scientific studies for centuries, studies, which have only increased in frequency in recent years. By means of this research several properties of networks have been determined, one of them being the community structure. As it turns out many networks, particularly social ones, tend to consist of communities - groups of entities densely connected with one another, but having relatively few external connections.In this work we present a simple classification of networks, outline their common properties and, focusing on one of them - the community structure, depict several algorithms for community detection and compare their efficiency as well as accuracy. Specifically, we focus on heuristic algorithms maximizing a certain parameter of a network partition known as modularity, high values of which are indicative of a "good" partition, that is one which closely resembles the desired split of a network into communities.The algorithms analyzed are those by Blondel et al., Girvan-Newman, Clauset-Newman-Moore, and hierarchical clustering. They are tested using our own implementations and real-world as well as randomly generated datasets. The tests one-sidedly conclude the superiority of the algorithm by Blondel et al., both in the fields of accuracy and time efficiency.
dc.abstract.plpl
Systemy bytów połączonych pewną formą relacji są wszechobecne w otaczającym nas świecie. Układ krążenia, ogólnoświatowa sieć Internetowa, czy łańcuch pokarmowy to tylko kilka przykładów takich systemów, znanych pod nazwą sieci. W związku z ich powszechnością i istotnością, sieci są obiektem badań naukowych od stuleci — badań, które w ostatnich latach tylko przybrały na intensywności. W ich efekcie wyodrębniono liczne własności sieci, a wśród nich strukturę społecznościową. Jak się okazuje, wiele sieci składa się ze społeczności, czyli grup bytów gęsto ze sobą połączonych, ale mających niewiele połączeń zewnętrznych.W mojej pracy prezentuję prostą klasyfikację sieci, przedstawiam ich charakterystyczne własności i koncentrując się na jednej z nich — strukturze społecznościowej — opisuję kilka algorytmów detekcji społeczności w sieciach, a także porównuję ich wydajność i dokładność. Konkretniej, skupiam się na heurystycznych algorytmach maksymalizujących pewien parametr podziału sieci, znany jako modularność, której wysokie wartości są typowe dla "dobrych" podziałów, czyli takich, które cechuje duże podobieństwo z pożądanym podziałem sieci na społeczności.Porównywane algorytmy to: algorytm Blondela et al., algorytm Girvan-Newmana, algorytm Clauseta-Newmana-Moore'a oraz hierarchiczne klastrowanie. Testuję je, używając własnych implementacji oraz danych ze świata rzeczywistego, jak również generowanych losowo. Przeprowadzone testy jednoznacznie orzekają o wyższości algorytmu Blondela et al., zarówno w obszarze dokładności, jak i wydajności.
dc.affiliationpl
Wydział Matematyki i Informatyki
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Cieślik, Iwona - 141986
dc.contributor.authorpl
Słoczyński, Adam
dc.contributor.departmentbycodepl
UJK/WMI2
dc.contributor.reviewerpl
Cieślik, Iwona - 141986
dc.contributor.reviewerpl
Ślusarek, Maciej - 132329
dc.date.accessioned
2020-07-27T22:51:15Z
dc.date.available
2020-07-27T22:51:15Z
dc.date.submittedpl
2019-07-09
dc.fieldofstudypl
informatyka analityczna
dc.identifier.apdpl
diploma-131246-209257
dc.identifier.projectpl
APD / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/234061
dc.languagepl
eng
dc.subject.enpl
network, graph, community, modularity, algorithm, implementation
dc.subject.plpl
sieć, graf, społeczność, modularność, algorytm, implementacja
dc.titlepl
An Overview of Algorithms for Community Detection in Networks.
dc.title.alternativepl
An Overview of Algorithms for Community Detection in Networks
dc.typepl
licenciate
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
27
Views per month
Views per city
Warsaw
6
Gdansk
4
Krakow
3
Wroclaw
3
Nuremberg
2
Dublin
1
Elblag
1
Medan
1
Otwock
1
Poznan
1

No access

No Thumbnail Available