29

19ص.

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

فرهنگ و انديشه رياضي

تهران انجمن رياضي ايران 1397

1397

37

63

129-147

پاييز و زمستان