کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
392185 664685 2015 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Probabilistic SimRank computation over uncertain graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Probabilistic SimRank computation over uncertain graphs
چکیده انگلیسی

Existing studies on graph-based analysis focus on standard graphs that are precise and complete. However, in many prevalent application domains, such as social, biological, and mobile networks, the existence of an edge in a graph is best captured by a likelihood measure or a probability. This paper investigates the problem of node similarity computation on large uncertain graphs. We first extend the well-known SimRank to define meaningful similarity measure on probabilistic graphs, and then propose a probabilistic framework to compute it. Based on the observation that the probabilistic transition probabilities computed on the whole graph equal to those computed on multiple sub-graphs, we design a SubG algorithm to compute the probabilistic transition matrix. Furthermore, we propose an efficient dynamic programming algorithm to degrade the time complexity from exponential to polynomial. We give the corresponding theoretical justification and extend the proposed algorithm to incremental dynamic programming algorithm, which further improves the efficiency and can be applied to dynamic graphs. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 295, 20 February 2015, Pages 521–535
نویسندگان
, , , , ,