مقدمهای بر نظریهٔ گراف و تحلیل شبکههای پیچیده
مقدمهای بر نظریهٔ گراف و تحلیل شبکههای پیچیده¶
بسیاری از مسئلهها را میتوان بر پایهٔ موجودیتها و رابطههای میان آنها مدل کرد. نظریهٔ گراف (GT) به ما اجازه میدهد گرهها و پیوندهای میانشان را تعریف کنیم تا فرایندهای پیچیدهای را که در حوزههای گوناگون علم و فناوری دیده میشوند بازنمایی و تحلیل کنیم. امروز دادهٔ فراوانی در دست است که با آن میتوان جهان پیرامونمان را از راه «چیزها»، روابط میانشان و بومسازگانشان شناخت.
در این درس با مقدمهای بر GT و تحلیل شبکههای پیچیده، همراه با کاربردی روی دادهٔ رسانههای اجتماعی، آغاز میکنیم. ابزارهای پرکاربرد GT، سنجههای توپولوژی شبکه، رایجترین معیارهای مرکزیت و چند کاربرد را بررسی میکنیم. با پایتون کد مینویسیم و کتابخانههایی برای ساخت، کاوش، تحلیل و مصورسازی شبکههای پیچیده میآزماییم. برای این کار گرافها را با کتابخانهٔ NetworkX، تبدیل داده را با NumPy و Pandas و مصورسازی را با Matplotlib میسازیم. تحلیل طولی شبکههای در حال تغییر را بر پایهٔ توپولوژی و معیارهای مرکزیت دنبال میکنیم. در پایان، توان ساخت، تحلیل و مصورسازی شبکههای پیچیده را خواهید داشت.
هدفهای یادگیری
در پایان این درس با موارد زیر آشنا میشوید:
مفاهیم مقدماتی نظریهٔ گراف (GT) و کاربردهایش.
ساخت، تحلیل و مصورسازی شبکهها با ماژول NetworkX.
توصیف و مقایسهٔ شبکهها با ویژگیهای توپولوژی شبکه.
کار با معیارهای سنتی مرکزیت و تمایز میان آنها در کاربردهای عملی.
انجام تحلیل روی شبکههایی که در زمان تغییر میکنند (تحلیل طولی).
پیشنیازها
تسلط بر پایتون با NumPy و Matplotlib (یا بستهها و زبانهای مشابه) لازم است. آشنایی مقدماتی با جبرخطی مطلوب است.
منابع
این محتوا عمدتاً بر دو منبع استوار است:
Van Steen, M. (2010). Graph theory and complex networks. An introduction.
Newman, M. (2010). Networks: An Introduction.
فهرست کامل منابع در پایان هر بخش (نوتبوک) آمده است.
یادآوری میکنم که مطالب اصلی از درس «دادهکاوی و یادگیری» دورهٔ کارشناسی ارشد انفورماتیک، دانشگاه آسترال شیلی، دانشکدهٔ علوم مهندسی شیلی گرفته شده است. من محتوا را برای نیازها و سلیقهٔ خودم تغییر دادهام و از پدیدآورندگان این مطالب سپاسگزارم.
تمرینها¶
دنبالهٔ درجات یک گراف کوچک دلخواه را حساب کنید و توزیع درجهاش را رسم کنید. متمرکز است یا دُمسنگین؟
ثابت کنید مجموع درجات دو برابر تعداد یالها است و از آن نتیجه بگیرید هیچ گرافی دقیقاً یک رأس با درجهٔ فرد ندارد.
دو گراف نایزومورف با دنبالهٔ درجات یکسان بدهید و توضیح دهید چرا دنبالهٔ درجات ناوردای کامل نیست.