COMMUNITY STRUCTURE DETECTION OF NETWORKS USING ADVANCED LABEL PROPAGATION ALGORITHM

• Main Author: NURRIYADI SUPARNO (NIM : 10211053), ERVANO
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/21984
• Institution: Institut Teknologi Bandung

<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">