گراف تصادفی با توزیع درجه دلخواه (Random Graph with Arbitrary Degree Distribution)، در ریاضیات (Mathematics)
انواع گراف های تصادفی (Random Graphs) را در آموزش زیر شرح دادیم :
گراف تصادفی با توزیع درجه دلخواه (Random Graph with Arbitrary Degree Distribution) :
در مدل های کلاسیک
\[ G(n,p) \]، توزیع درجه ها عمدتا پواسونی (Poisson) است، در حالی که در بسیاری از شبکه های واقعی مانند شبکه اینترنت یا شبکه هم نویسندگی، توزیع درجه از قانون توانی (Power Law) پیروی می کند (شبکه های بدون مقیاس - Scale-free Networks). برای تولید چنین گراف هایی، ابتدا یک توالی از درجه ها را مشخص می کنیم (مثلا با استفاده از تابعی مانند
\[ P(k) \sim k^{-\gamma} \]). سپس الگوریتم پیکربندی (Configuration Model) را به کار می بندیم. در این الگوریتم، به هر رأس به تعداد درجه اش "شاخک" (Stub) می دهیم و سپس شاخک ها را به صورت تصادفی جفت می کنیم تا یال ها شکل بگیرند. این مدل به ما اجازه می دهد گراف هایی با هر توزیع درجه دلخواهی تولید کنیم.
نویسنده علیرضا گلمکانی
شماره کلید 5558
گزینه ها 
نظرات 0 0 0