Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

مقدمه‌ای بر نظریهٔ گراف و تحلیل شبکه‌های پیچیده

English · فارسی

مقدمه‌ای بر نظریهٔ گراف و تحلیل شبکه‌های پیچیده

بسیاری از مسئله‌ها را می‌توان بر پایهٔ موجودیت‌ها و رابطه‌های میان آن‌ها مدل کرد. نظریهٔ گراف (GT) به ما اجازه می‌دهد گره‌ها و پیوندهای میانشان را تعریف کنیم تا فرایندهای پیچیده‌ای را که در حوزه‌های گوناگون علم و فناوری دیده می‌شوند بازنمایی و تحلیل کنیم. امروز دادهٔ فراوانی در دست است که با آن می‌توان جهان پیرامونمان را از راه «چیزها»، روابط میانشان و بوم‌سازگانشان شناخت.

در این درس با مقدمه‌ای بر GT و تحلیل شبکه‌های پیچیده، همراه با کاربردی روی دادهٔ رسانه‌های اجتماعی، آغاز می‌کنیم. ابزارهای پرکاربرد GT، سنجه‌های توپولوژی شبکه، رایج‌ترین معیارهای مرکزیت و چند کاربرد را بررسی می‌کنیم. با پایتون کد می‌نویسیم و کتابخانه‌هایی برای ساخت، کاوش، تحلیل و مصورسازی شبکه‌های پیچیده می‌آزماییم. برای این کار گراف‌ها را با کتابخانهٔ NetworkX، تبدیل داده را با NumPy و Pandas و مصورسازی را با Matplotlib می‌سازیم. تحلیل طولی شبکه‌های در حال تغییر را بر پایهٔ توپولوژی و معیارهای مرکزیت دنبال می‌کنیم. در پایان، توان ساخت، تحلیل و مصورسازی شبکه‌های پیچیده را خواهید داشت.

هدف‌های یادگیری

در پایان این درس با موارد زیر آشنا می‌شوید:

پیش‌نیازها

تسلط بر پایتون با NumPy و Matplotlib (یا بسته‌ها و زبان‌های مشابه) لازم است. آشنایی مقدماتی با جبرخطی مطلوب است.

منابع

این محتوا عمدتاً بر دو منبع استوار است:

  1. Van Steen, M. (2010). Graph theory and complex networks. An introduction.

  2. Newman, M. (2010). Networks: An Introduction.

فهرست کامل منابع در پایان هر بخش (نوت‌بوک) آمده است.


یادآوری می‌کنم که مطالب اصلی از درس «داده‌کاوی و یادگیری» دورهٔ کارشناسی ارشد انفورماتیک، دانشگاه آسترال شیلی، دانشکدهٔ علوم مهندسی شیلی گرفته شده است. من محتوا را برای نیازها و سلیقهٔ خودم تغییر داده‌ام و از پدیدآورندگان این مطالب سپاسگزارم.

تمرین‌ها

  1. دنبالهٔ درجات یک گراف کوچک دلخواه را حساب کنید و توزیع درجه‌اش را رسم کنید. متمرکز است یا دُم‌سنگین؟

  2. ثابت کنید مجموع درجات دو برابر تعداد یال‌ها است و از آن نتیجه بگیرید هیچ گرافی دقیقاً یک رأس با درجهٔ فرد ندارد.

  3. دو گراف نایزومورف با دنبالهٔ درجات یکسان بدهید و توضیح دهید چرا دنبالهٔ درجات ناوردای کامل نیست.