COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM
<p align="justify">Agents of a complex system tend to naturally form groups or communities based on their similarities. In a network, these communities manifest themselves as bundles or densely connected nodes. Community detection is a prominent method for understanding the structure...
Saved in:
Main Author: | |
---|---|
Format: | Final Project |
Language: | Indonesia |
Online Access: | https://digilib.itb.ac.id/gdl/view/21984 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Institut Teknologi Bandung |
Language: | Indonesia |
id |
id-itb.:21984 |
---|---|
spelling |
id-itb.:219842018-10-23T08:53:11ZCOMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM NURRIYADI SUPARNO (NIM : 10211053), ERVANO Indonesia Final Project INSTITUT TEKNOLOGI BANDUNG https://digilib.itb.ac.id/gdl/view/21984 <p align="justify">Agents of a complex system tend to naturally form groups or communities based on their similarities. In a network, these communities manifest themselves as bundles or densely connected nodes. Community detection is a prominent method for understanding the structure, organization, and functioning of various real-world networks and has applications in diverse problems such as consensus formation in social communities and the identification of functional modules in biochemical networks. Current algorithms for identifying community structures in large-scale real-world networks generally require a priori information such as the number and sizes of communities and are computationally expensive. In this Final Project, we implement a simple label propagation algorithm that uses network structure alone as its guide and has an almost linear running time. In this algorithm, every node is initialized with a unique label, and at every step, each node adopts the label that most of its neighbors currently have. In this iterative process, densely connected groups of nodes form a consensus on a unique label to form communities. We then implement an agglomerative method to escape from local maxima and enhance the modularity. This combination of algorithm is known as advance label propagation algorithm. Finally, we validate the algorithm by applying it to networks whose community structures are known.<p align="justify"> text |
institution |
Institut Teknologi Bandung |
building |
Institut Teknologi Bandung Library |
continent |
Asia |
country |
Indonesia Indonesia |
content_provider |
Institut Teknologi Bandung |
collection |
Digital ITB |
language |
Indonesia |
description |
<p align="justify">Agents of a complex system tend to naturally form groups or communities based on their similarities. In a network, these communities manifest themselves as bundles or densely connected nodes. Community detection is a prominent method for understanding the structure, organization, and functioning of various real-world networks and has applications in diverse problems such as consensus formation in social communities and the identification of functional modules in biochemical networks. Current algorithms for identifying community structures in large-scale real-world networks generally require a priori information such as the number and sizes of communities and are computationally expensive. In this Final Project, we implement a simple label propagation algorithm that uses network structure alone as its guide and has an almost linear running time. In this algorithm, every node is initialized with a unique label, and at every step, each node adopts the label that most of its neighbors currently have. In this iterative process, densely connected groups of nodes form a consensus on a unique label to form communities. We then implement an agglomerative method to escape from local maxima and enhance the modularity. This combination of algorithm is known as advance label propagation algorithm. Finally, we validate the algorithm by applying it to networks whose community structures are known.<p align="justify"> |
format |
Final Project |
author |
NURRIYADI SUPARNO (NIM : 10211053), ERVANO |
spellingShingle |
NURRIYADI SUPARNO (NIM : 10211053), ERVANO COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
author_facet |
NURRIYADI SUPARNO (NIM : 10211053), ERVANO |
author_sort |
NURRIYADI SUPARNO (NIM : 10211053), ERVANO |
title |
COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
title_short |
COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
title_full |
COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
title_fullStr |
COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
title_full_unstemmed |
COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM |
title_sort |
community structure detection of networks using advanced label propagation algorithm |
url |
https://digilib.itb.ac.id/gdl/view/21984 |
_version_ |
1821120629892448256 |