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

نوع مقاله: مقاله علمی - مروری

نویسندگان

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

چکیده

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

کلیدواژه‌ها

موضوعات