COMMUNITY DETECTION ANALYSIS ON BIG GRAPH DATA
<p align="justify"> <br /> <br /> In this work, an analysis of RelaxMap algorithm and Modified Louvain algorithm is done to determine the optimal algorithm in computation. This analysis is done by comparing the RelaxMap algorithm and the Modified Louvain algorithm in dete...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/28253 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | <p align="justify"> <br />
<br />
In this work, an analysis of RelaxMap algorithm and Modified Louvain algorithm is done to determine the optimal algorithm in computation. This analysis is done by comparing the RelaxMap algorithm and the Modified Louvain algorithm in detecting communities and handling big graphs. Thus, we can determine the optimal algorithm in computation. <br />
<br />
Based on the comparison made, the Modified Louvain algorithm has a lighter computation and has a simpler way of handling big graphs. However, the RelaxMap algorithm detects communities based on flow information through graphs. Thus, the Modified Louvain algorithm is more optimal in terms of computation as long as the user wants a community detection that does not require flow information. In addition, the Modified Louvain algorithm has two ways of community detection, Mod. A with constraint R as input and Mod. B with constraint k as input. These two ways can be combined into one integrated algorithm if the constraint R is greater than the constraint k. <br />
<br />
The Modified Louvain algorithm is chosen to be implemented. The implementation is done by using and modifying the louvain-igraph library created by V. A. Traag. Implementation result program is used for experiments. From this experiment, it was found that processing time increases linearly if the constraint R or k is increased, the number of vertices and the number of edges influences the increase of processing time when the constraint R or k is increased, Mod. B is heavier than Mod. A in terms of computation, community search for a vertex uses considerable memory, and the constraint k further influences processing time on the integrated Modified Louvain algorithm. <br />
<br />
From this work, it can be concluded that the Modified Louvain algorithm is more optimal in computation than RelaxMap algorithm if user do not need to pay attention to flow information. For further development, there is potential to develop modified Louvain algorithm in parallel and shorten processing time or minimize memory usage in the community search process for a vertex. <br />
<p align="justify"> |
|---|