An Application of Louvain Method on Overlapping Community Detection to Improve The Detection Time

• Main Author: Syamsu - NIM: 23516050, Rosalina
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/30685
• Institution: Institut Teknologi Bandung

The rapid development of social media today has made social media very popular. Social media has a community structure like the real world which consists of one or several people in the community. Along with this rapid development, there is a way to find out the community called community detection. Community detection is divided into two, namely disjoint and overlapping community. The disjoint community is a community where members of the community could only join one community. The overlapping community is a community where members of the community could join more than one community. The Louvain method is the most commonly used method for disjoint community detection because the Louvain method can detect very quickly. The forming process of community detection with the Louvain method consisting of 2 million nodes only takes 2 minutes. The solutions offered by previous studies of overlapping community detection still had limitations, such as there are algorithms that should determine the number of clusters, the members who are unknown to join to any single communities, and the detection time is slow. The development of social media which causes large data sizes require algorithms that could detect with a faster detection time than previous studies. <br /> <br /> <br /> <br /> <br /> From the problems explained above, an experiment is needed to increase detection time on overlapping community detection by applying the Louvain method. Experiments are designed based on the results of the analysis in previous studies. The author proposed two experimental proposals. The first experiment used the calculation of betweenness centrality and belonging coefficient. The calculation of betweenness centrality is used to find members who have an influence on the other members if the betweenness vertex value is greater than the edge betweenness value. The calculation of belonging coefficient is used in members obtained from the betweenness centrality measurement to find the overlapping community. The second experiment used a belonging coefficient on all members of the graph network to find the overlapping community. Both of these experimental proposals are used to find out proposals that have a faster detection time with good community quality values. <br /> <br /> <br /> <br /> <br /> The test results in this study compared with the overlapping community detection algorithm in the previous studies. The first experiment resulted in better community quality values compared to the second experiment and previous studies. However, the first experiment still has limited detection time when tested on large data. This is due to the complexity of the betweenness centrality measurement. The second experiment generated community quality values that were not too far from the first experiment. The second experiment generated to find overlapping community with a faster detection time. In the data with the number of nodes 334,863 and edges 925,872, the second experiment succeeded in finding the overlapping community within 1 hour and 65 minutes, while the first experimental proposal and previous studies could not generate any results. From these results, it could be concluded that the second experiment can result in a faster detection time with good community quality values. <br />