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

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

نویسندگان

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

چکیده

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

کلیدواژه‌ها

موضوعات


Aho, A. V.‎, ‎Hopcroft, J. E.‎, ‎Ullman, J. D.‎,  ‎The Design and Analysis of Computer Algorithms,‎‎ ‎Addison-Wesley‎, New York, 1974.
 
‎Avrachenkov, K.‎, ‎Litvak, N.‎, ‎Nemirovsky, D.‎, ‎Osipova, N.‎,  Monte-Carlo methods in PageRank computation‎: ‎when one iteration is sufficient‎, ‎SIAM Journal on Numerical Analysis‎‎, ‎45 (2007)‎‎, ‎890--904‎
 
‎Barab'{a}si, A. L.‎, Network Science, ‎Cambridge University Press‎, Cambridge, 2016.
 
anatomy of a large-scale hypertextual web search engine‎, ‎Computer Networks and ISDN Systems‎‎, ‎30 (1998)‎‎, ‎107--117‎.
 
‎Dixon, J. D.‎,  Exact solution of linear equations using ‎$p‎$-adic expansions‎, ‎Numerische Mathematik‎‎, 40 (1982)‎‎, ‎137--141‎.
 
‎Erciyes, K.‎,  Distributed Graph Algorithms for Computer Networks‎‎, ‎Springer-Velrag, New York, Berlin, 2013‎.
 
‎Grimmett‎, ‎G.‎, ‎Stirzaker‎, ‎D.‎,  Probability and Random Processes‎‎, ‎Oxford University Press‎, London, 2001.
 
‎Huang, W.‎, ‎Yang, H.‎,  A Hadoop job scheduling algorithm based on PageRank‎,                  Metallurgical and Mining Industry‎‎, {‎8} (2015)‎‎, ‎420--425‎.
 
‎Kim, H.‎, ‎Veciana, G.‎, ‎Yang, X.‎, ‎Venkatachalam, M.‎,  Distributed $alpha$‎-‎optimal user association and cell load balancing in wireless networks‎, ‎IEEE/ACM Transactions on Networking‎‎, ‎20 (2012)‎‎, ‎177--190‎.
 
‎Langville, A. N.‎, ‎Meyer, C. D.‎,  Google's PageRank and Beyond‎: ‎The Science of Search Engine Rankings‎‎, ‎Princeton University Press‎, 2012.
 
‎Lawler, F. G.‎,  Introduction to Stochastic Processes‎‎, ‎Chapman and Hall/CRC‎, 2006.
 
‎Mitzenmacher, M.‎, ‎Upfal, E.‎,  Probability and Computing‎: ‎An Introduction to Randomized Algorithms and Probabilistic Analysis‎‎,  ‎Cambridge University Press‎, London, 2005.
 
‎Newman, M.‎, Networks‎: ‎An Introduction‎‎, ‎Oxford University Press‎, London, 2010.
 
‎Peleg, D.‎,  Distributed Computing‎: ‎A Locality-Sensitive Approach‎‎, ‎SIAM‎, 2000.
 
‎Penmatsa, S.‎, ‎Chronopoulos, A.T.‎,  Game-theoretic static load balancing for distributed systems‎, ‎Journal of Parallel and Distributed Computing‎‎, ‎71 (2011)‎‎, ‎537--555‎.
 
‎P'{e}rez-Ros'{e}s, H.‎, ‎Seb'{e}, F.‎, ‎Rib'{o}, J. M.‎,  Endorsement deduction and ranking in social networks‎, ‎Computer Communications‎‎, ‎73 ‎(2016)‎‎, ‎200--210‎.
 
‎Sarma, A. D.‎, ‎Molla, A.‎, ‎Pandurangan, G.‎, ‎Upfal, E.‎,  Fast ‎distributed ‎P‎ageRank ‎computation‎, ‎ Theoretical Computer Science‎‎‎, ‎561 (2015)‎‎‎, ‎113--121‎.
 
‎Sarma, A. D.‎, ‎Molla- A.‎, ‎Nanongkai, D.‎, ‎Pandurangan, G.‎, ‎Tetali, P.‎,  Distributed random walks‎,  ‎Journal of the ACM‎‎, ‎60 (2013)‎‎, ‎1--31‎.
 
‎Shi, S.‎, ‎Yu, J.‎, ‎Yang, G.‎, ‎Wang, D‎,  Distributed page ranking in structured P2P networks‎, ‎International Conference on Parallel Processing‎ (2003)‎, ‎Kaohsiung‎, ‎179--186‎.
 
‎Zhu, Y.‎, ‎Ye, S.‎, ‎Li, X.‎, Distributed pagerank computation based on iterative aggregation-disaggregation methods ‎CIKM Proceedings of the 14th ACM International Conference on Information and Knowledge Management ‎(2005)‎, ‎Bremen‎, ‎578--585‎.