وب گراف
وب گراف توصیف لینک‌های جهت دار بین صفحات وب گسترده جهانی است. یک گراف، به طور کلی، از چندین راس تشکیل شده است که برخی از جفت ها توسط یال ها به هم متصل می شوند. در یک گراف جهت دار، یال‌ها، خطوط یا کمان‌های جهت دار هستند. وب گراف، یک گراف جهت دار است که رئوس آن با صفحات WWW مطابقت دارد و یال‌های جهت دار آن صفحه X را به صفحه Y متصل می کند،این ارتباط در صورتی برقرار می شود که یک لینک در صفحه X وجود داشته باشد که به صفحه Y اشاره دارد.
خواص[ویرایش]
- توزیع درجه در وب گراف بسیار متمایز است توزیع درجه گراف‌های کلاسیک تصادفی مدل Erdős–Rényi مدل:[۱] در مدل Erdős–Rényi تعداد کمی از درجه‌های بزرگ راس نسبت به توزیع درجه وب گراف وجود دارد. توزیع دقیقی وجود ندارد با این حال:[۲] وب گراف به کمک توزیع لگاریتمی نرمال و همچنین مثل Barabási–آلبرت مدل برای قوانین قدرت نسبتاً به خوبی شرح داده می شود.[۳][۴]
- وب گراف یک مثال از یک مقیاس رایگان شبکه است.
کاربردها[ویرایش]
وب گراف برای موارد زیر مورد استفاده قرار می گیرد:
- برای محاسبه پیج‌رنک صفحات WWW؛
- برای محاسبه رتبه صفحات شخصی؛[۵]
- شناسایی صفحات وب با موضوعات مشابه، فقط از طریق ویژگی های نظری نمودار، مانند استناد مشترک؛[۶]
- و برای شناسایی هاب و مقامات (روش مراجع و مراکز) در وب برای الگوریتم هیتس.
منابع[ویرایش]
- ↑ P. Erdős, A. Renyi, Publ.
- ↑ Meusel, R.; Vigna, S.; Lehmberg, O.; Bizer, C. (2015). "The Graph Structure in the Web - Analyzed on Different Aggregation Levels". Journal of Web Science. 1 (1): 33–47. doi:10.1561/106.00000003.
- ↑ Clauset, A.; Shalizi, C. R.; Newman, M. E. J. (2007). "Power-law distributions in empirical data". SIAM Rev. 51 (4): 661–703. doi:10.1137/070710111.
- ↑ Barabási, Albert-László; Albert, Réka (October 1999). "Emergence of scaling in random networks" (PDF). Science. 286 (5439): 509–512. doi:10.1126/science.286.5439.509. PMID 10521342.
- ↑ Glen Jeh and Jennifer Widom. 2003.
- ↑ Kumar, Ravi; Raghavan, Prabhakar; Rajagopalan, Sridhar; Tomkins, Andrew (1999). "Trawling the Web for emerging cyber-communities". Computer Networks. 31 (11–16): 1481–1493. doi:10.1016/S1389-1286(99)00040-7.