Digital Library[ Search Result ]
Fast Personalized PageRank Computation on Very Large Graphs
Sungchan Park, Youna Kim, Sang-goo Lee
http://doi.org/10.5626/JOK.2022.49.10.859
Computation of Personalized PageRank (PPR) in graphs is an important function that is widely utilized in myriad application domains such as search, recommendation, and knowledge discovery. As the computation of PPR is an expensive process, a good number of innovative and efficient algorithms for computing PPR have been developed. However, efficient computation of PPR within very large graphs with over millions of nodes is still an open problem. Moreover, previously proposed algorithms cannot handle updates efficiently, thereby severely limiting their capability of handling dynamic graphs. In this paper, we present a fast converging algorithm that guarantees high and controlled precision. We attempted to improve the convergence rate of the traditional Power Iteration approximation methods and fully exact methods. The results revealed that the proposed algorithm is at least 20 times faster than the Power Iteration and outperforms other state-of-the-art algorithms in terms of computation time.
Proposal of a Graph Based Chat Message Analysis Model for Messenger User Verification
http://doi.org/10.5626/JOK.2022.49.9.696
As crimes and accidents through messengers increase, the necessity of verifying messenger users is emerging. In this study, two graph-based messenger user verification models that apply the traditional author verification problem to chat text were proposed. First, the graph random walk model builds an n-gram transition graph with a previous chat message and verifies the user by learning the characteristic of traversing the transition graph with a message whose author is unknown. The results showed an accuracy of 86% in 10,000 chat conversations. Second, the graph volume model verified the user using the characteristic that the size of the transition graph increased over time and achieved an accuracy of 87% in 1,000 chat conversations. When the density of the chat messages was calculated based on the transmission time, both graph models could guarantee more than 80% accuracy when the chat density was 15 or more.
New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem
Seunghwan Min, Wonseok Shin, Chaewon Kim, Kunsoo Park
http://doi.org/10.5626/JOK.2022.49.1.1
In recent years, graph analysis has been used in various applications. One of the fundamental problems in graph analysis is the subgraph matching problem. Given a data graph and a query graph, the subgraph matching problem is to find all embeddings of the query graph in the data graph. Many backtracking-based algorithms have been studied to solve this problem. In this paper, we analyzed the problems in adaptive matching order proposed by DAF, a state-of-the-art algorithm that solves this problem, and introduced an improved adaptive matching order. Furthermore, we conducted experiments with real data graphs to demonstrate that the proposed matching order was more effective than the previous matching orders if the pruning technique was not used or the elapsed time was not very short even if the pruning technique was used.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr