Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 720664

Community structure in networks: Girvan-Newman algorithm improvement


Despalatović, Ljiljana; Vojković, Tanja; Vukičević, Damir
Community structure in networks: Girvan-Newman algorithm improvement // Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014
Opatija, Hrvatska: IEEE, 2014. str. 997-1002 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), ostalo)


CROSBI ID: 720664 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

Naslov
Community structure in networks: Girvan-Newman algorithm improvement

Autori
Despalatović, Ljiljana ; Vojković, Tanja ; Vukičević, Damir

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), ostalo

Izvornik
Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014 / - : IEEE, 2014, 997-1002

ISBN
978-953-233-081-6

Skup
Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014 37th International Convention on

Mjesto i datum
Opatija, Hrvatska, 26-30.05. 2014

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
complex networks computational complexity graph theory iterative methods

Sažetak
Real world networks often have community structure. It is characteristic that the groups of nodes are connected denser within themselves and rarely with each other. The Girvan-Newman method for the detection and analysis of community structure is based on the iterative elimination of edges with the highest number of the shortest paths that go through them. By eliminating edges the network breaks down into smaller networks, i.e. communities. This paper introduces improved Girvan-Newman method where multi-edge removal is allowed, and presents the results of the application of both methods to the existing real social network (Zachary karate club), the computergenerated network and the tumor genes and their mutations network. The improved algorithm in practice reduces the number of operations, but retains the same computational complexity, so it cannot be applied to networks with a very large number of nodes. The most important feature of our improvement is that the result is graph- theoretical invariant, while original algorithm depends on the vertex labeling.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo, Informacijske i komunikacijske znanosti



POVEZANOST RADA


Ustanove:
Prirodoslovno-matematički fakultet, Split


Citiraj ovu publikaciju

Despalatović, Ljiljana; Vojković, Tanja; Vukičević, Damir
Community structure in networks: Girvan-Newman algorithm improvement // Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014
Opatija, Hrvatska: IEEE, 2014. str. 997-1002 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), ostalo)
Despalatović, L., Vojković, T. & Vukičević, D. (2014) Community structure in networks: Girvan-Newman algorithm improvement. U: Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014.
@article{article, year = {2014}, pages = {997-1002}, keywords = {complex networks computational complexity graph theory iterative methods}, isbn = {978-953-233-081-6}, title = {Community structure in networks: Girvan-Newman algorithm improvement}, keyword = {complex networks computational complexity graph theory iterative methods}, publisher = {IEEE}, publisherplace = {Opatija, Hrvatska} }
@article{article, year = {2014}, pages = {997-1002}, keywords = {complex networks computational complexity graph theory iterative methods}, isbn = {978-953-233-081-6}, title = {Community structure in networks: Girvan-Newman algorithm improvement}, keyword = {complex networks computational complexity graph theory iterative methods}, publisher = {IEEE}, publisherplace = {Opatija, Hrvatska} }




Contrast
Increase Font
Decrease Font
Dyslexic Font