توزیع درجه

درجه گره در یک شبکه (گاهی اوقات به اشتباه به عنوان همبندی) تعداد اتصالات یا لبه های یک گره به گره‌های دیگر است. اگر یک گراف جهت‌دار باشد به این معنی است لبه‌ها از یک گره به گره دیگر دارای جهت می‌باشند. در نتیجه هر گره دارای دو درجه متفاوت خواهد بود: درجه ورودی که تعداد لبه‌های ورودی آن گره و درجه خروجی تعداد لبه‌های خروجی آن گره می‌باشد.

به کسری از گره‌های یک شبکه با درجه k، درجه توزیع P(k).بنابراین اگر شبکه n گره داشته باشد و n_k تای آن‌ها درجه k داشته باشند, درجه توزیع P(k) = n_k/n خواهد بود.

به همین صورت می‌توان تعاریف دیگری را ارائه کرد. درجه توزیع تجمعی کسری از گره‌های با درجه کوچکتر از k و متمم درجه توزیع تجمعی کسری از گره‌ها با درجه بزرگتر یا مساوی باهای نودها که درجه همان اطلاعات نیز گاهی در قالب یک تجمعی درجه توزیعکسر از با درجه بزرگتر یا مساوی (k (1 - C;که در اینجا C درجه توزیع تجمعی می‌باشد،یعنی مکمل C).

توزیع درجات در مطالعه هر دو شبکه‌های دنیای واقعی مانند اینترنت و شبکه‌های اجتماعی و شبکه‌های نظری بسیار مهم می‌باشد. ساده‌ترین مدل شبکه گراف تصادفی (برنولی) می‌باشد، که در آن هر یک از n گره با احتمال مستقل P( یا 1-p) وصل (یا غیروصل) هست. توزیع درجات k بسط دو جمله ای است:

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(و اگر n بسیار بزرگ باشد از توزیع پواسون خواهد داشت). اکثر شبکه‌ها در دنیای واقعی، توزیع درجات متفاوت با این مدل دارند. توزیع درجات دارای کشیدگی (چولگی) به سمت راست می‌باشد. به این معنی که تعداد زیادی از گره‌ها درجات کمی دارند و درجه پایین اما تعداد کمی از گره‌ها ، که هاب نامیده می‌شوند، درجات بالایی دارند.در بعضی از شبکه ها، برای مثال اینترنت، شبکه جهانی وب ، و بعضی از شبکه‌های اجتماعی توزیع درجهات به صورت تقریبی از قانون توان پیروی می‌کنند. در قانون توان توزیع درجات به صورت  P(k) ~ kمی باشد که در آن γ ثابت است. چنین شبکه هایی، شبکه‌های مقیاس-مستقل(هر بخشی از شبکه ساختار مشابهی با کل شبکه دارد) نامیده می‌شوند.

• نظریه گراف
• شبکه‌های پیچیده
• شبکه‌های مقیاس مستقل
• گراف تصادفی
• ساختار قطع