DYNAMIC HETER-LP: HETER-LP ALGORITHM DEVELOPMENT AS A LINK PREDICTION SOLUTION FOR DYNAMIC HETEROGENEOUS GRAPH USING DTLPLP INTEGRATION

• Main Author: Puteri Haryono, Hollyana
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/77862
• Institution: Institut Teknologi Bandung

Various real-world phenomena such as recommendation systems, social networks, and protein structures can be well represented by graphs, particularly dynamic heterogeneous graphs. Link prediction is an important task in graphs as it can predict new or missing interactions within a graph. However, research on link prediction for dynamic heterogeneous graphs is still very limited. Heter-LP and DTLPLP are two link prediction algorithms that respectively focus on heterogeneous and dynamic graphs. Both algorithms use label propagation, which has been proven to be a simple and computationally efficient method. Additionally, they include a pre-processing phase to handle the dynamic or heterogeneous nature of the graph before label propagation is performed. In this thesis, the Dynamic Heter-LP algorithm is proposed as a solution for link prediction in dynamic heterogeneous graphs based on label propagation. The contribution of this thesis lies in the development of the Heter-LP algorithm by incorporating dynamic components from the DTLPLP algorithm, resulting in the creation of Dynamic Heter-LP as a new link prediction method specifically designed for dynamic heterogeneous graphs. The evaluation in this thesis uses data from users, businesses, and reviews from the Yelp Dataset over a duration of seven days, based on the time the reviews were conducted. The evaluation metrics used are AUROC score and processing time. Dynamic-Heter-LP achieved a AUROC score of 0.5 in predicting new reviews. In conclusion, Dynamic Heter-LP fulfills its functionality as a link prediction algorithm for dynamic heterogeneous graphs. However, it still has a drawback in terms of relatively long processing time. For future research, extending the duration and interval time in experiments and focusing on optimizing processing time can be considered.