رتبه بندي رأس‌هاي گراف

بدون عنوان

يك مسئلۀ مهم در نظريۀ گراف، علوم كامپيوتر و شبكه هاي اجتماعي، مشخص كردن اهميت رأس هاي يك گراف (يا گره هاي يك شبكه) است. بدين منظور، معيارها و روش هاي گوناگوني پيشنهاد شده است. يكي از اين روش ها، رتبه بندي است كه بر پايۀ گا م برداريِ تصادفي بنا شده است. هدف ما در اين مقاله، توضيح الگوريتم رتبه بندي به دو شكل متمركز و توزيع شده است. به اين منظور، نخست مفهوم رتبه بندي و الگوريتم محاسبۀ آن را به صورت متمركز توضيح مي دهيم. سپس يك الگوريتم رتبه بندي توزيع شده مبتني برشبيه سازي مونت كارلو را كه در O(log n) دور با احتمال زياد پايان مي پذيرد. تشريح مي كنيم.

بدون چكيده