کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418344 681642 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Comparison of mean hitting times for a degree-biased random walk
ترجمه فارسی عنوان
مقایسه مقادیر میانگین ضربه برای یک تصادف خیالی درجه یک؟
کلمات کلیدی
زنجیره مارکوف، تصادفی پیاده روی بر روی نمودارها، پیاده روی تصادفی بی طرفانه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Consider the random walk on graphs such that, at each step, the next visited vertex is a neighbor of the current vertex, chosen with probability proportional to the inverse of the square root of its degree. On one hand, for every graph with nn vertices, the maximal mean hitting time for this degree-biased random walk is asymptotically dominated by n2n2. On the other hand, the maximal mean hitting time for the simple random walk is asymptotically dominated by n3n3. Yet, in this article, we exhibit for each positive integer nn:
• A graph of size nn with maximal mean hitting time strictly smaller for the simple random walk than for the degree-biased one.
• A graph of size nn with mean hitting time of a so called root vertex strictly smaller for the simple random walk than for the degree-biased one.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 170, 19 June 2014, Pages 104–109
نویسندگان
, , , ,