رتبه بندی راس‌های گراف

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