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

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

کلیدواژه ها:

روش مونت کارلو ، گام برداری تصادفی ، معیارهای مرکزیت ، سیستم های توزیع شده