DEVELOPMENT OF PRO-HEAPS ALGORITHM TO ANALYZE COMMUNITY EVOLUTION IN HETEROGEN GRAPH

• Main Author: Andika Bukit, Tori
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/39869
• Institution: Institut Teknologi Bandung

In this study, a path interaction searching method between dynamic community members was developed on heterogeneous graph data using the PRO-HEAPS algorithm. The development of the PRO-HEAPS algorithm is done by integrating the time component against the path searching query on the PRO-HEAPS. Then an improvement was made on the PRO-HEAPS algorithm to support searching for interaction paths between dynamic community members that were modeled with heterogeneous graph data. The PRO-HEAPS algorithm provides better performance than other path searching methods, but this algorithm has not been able to support searching paths in an evolved graph data. The approach to developing the PRO-HEAPS algorithm in this study is done by modifying the path searching query and adding the pre-processing stage to process evolved graph data. The preprocessing stage is designed by selecting which time snapshots meet the query requirements, then running the PRO-HEAPS algorithm on each time snapshot of the evolving graph. In this study, an experiment was conducted to test the results of PRO-HEAPS development on evolved graph data. Implementation of the development of the PRO-HEAPS algorithm is done by developing desktop-based applications using C ++ language. The data testing used is synthesis data and DBLP data. Synthesis data is based on previous research by Liang et al. in 2018. While in the DBLP data, 6-time snapshots were selected from 1990 - 1995 to perform experiments. From this study, it can be concluded that the PRO-HEAPS algorithm is able to be developed to perform path searching on evolved graph data. Development is done by modifying the path searching query using the temporal query concept. The PRO-HEAPS algorithm was also developed by adding pre-processing stages to process evolved graphs. This pre-processing stage can select and save the snapshot time of graph data. Based on the experimental results, the application of the PRO-HEAPS development was able to maintain the ability of the functionality of the original PRO-HEAPS algorithm and be able to searching paths for evolved graph data.