پروژه نهایی دانشگاهی در حوزه نظریه گراف، تحلیل شبکههای اجتماعی و پیادهسازی الگوریتمهای گراف در Python
- معرفی پروژه
- چکیده
- اهداف پروژه
- ویژگیهای اصلی
- اعضای تیم
- دیتاست مورد استفاده
- مشخصات کلی شبکه
- معماری و طراحی پروژه
- ساختار پروژه
- الگوریتمها و تحلیلها
- محیط اجرا و وابستگیها
- نحوه نصب و اجرا
- آزمونها و تستها
- خروجیها و فایلهای تولیدشده
- نتایج تجربی
- نمایشهای بصری
- تحلیل علمی نتایج
- ملاحظات علمی و محدودیتها
- اعتبارسنجی و قابلیت بازتولید
- منابع علمی
- پیشنهاد برای توسعههای آینده
- وضعیت نهایی پروژه
این پروژه با هدف تحلیل ساختاری یک شبکه اجتماعی واقعی و بهکارگیری مفاهیم بنیادی نظریه گراف، الگوریتمهای پیمایش و تحلیل شبکههای پیچیده توسعه داده شده است. دادهی مورد استفاده، بخشی از مجموعهدادههای معتبر Stanford SNAP بوده و یک شبکه اجتماعی از نوع Facebook Ego Network را مدلسازی میکند.
در این پروژه، گراف شبکه اجتماعی از روی دادههای واقعی ساخته شده و سپس مجموعهای از تحلیلهای کلیدی روی آن انجام گرفته است؛ از جمله:
- پیمایش گراف با BFS و DFS
- یافتن کوتاهترین مسیر
- محاسبهی برخی معیارهای ساختاری
- تشخیص اجتماعهای شبکه
- بررسی ویژگیهای خوشهبندی
- تحلیل رفتار Small-World
- پیشبینی لینکهای بالقوه با روش Jaccard Similarity
- تولید نمودارها و نمایشهای بصری برای تفسیر نتایج
شبکههای اجتماعی نمونهای مهم از گرافهای بزرگ و پیچیده هستند که تحلیل آنها میتواند الگوهای ارتباطی، ساختار خوشهای و میزان تراکم روابط را آشکار کند. در این پروژه، یک شبکه اجتماعی واقعی از دیتاست SNAP بهصورت گراف بدونجهت مدلسازی شده و با استفاده از زبان Python و کتابخانههای تحلیلی، از منظر الگوریتمی و ساختاری بررسی شده است.
نتایج بهدستآمده نشان میدهند که شبکه مورد مطالعه دارای خوشهبندی بالا و ساختار اجتماعی معنادار است و از ویژگیهایی برخوردار است که با رفتار شناختهشدهی شبکههای اجتماعی واقعی سازگاری دارد.
- درک عملی مفاهیم نظریه گراف
- پیادهسازی الگوریتمهای کلاسیک روی داده واقعی
- آشنایی با تحلیل شبکههای اجتماعی
- تمرین طراحی نرمافزار ماژولار و مستندسازی دانشگاهی
- ساخت گراف از روی CSV
- پیادهسازی و اجرای BFS، DFS و Dijkstra
- تحلیل Degree Centrality
- تشخیص اجتماعهای موجود در شبکه
- بررسی ضریب خوشهبندی و تحلیل Small-World
- پیشبینی پیوندهای احتمالی بین گرهها
- تولید نمودارهای تحلیلی و فایلهای خروجی
- اعتبارسنجی نتایج با تستهای واحد
| قابلیت | شرح |
|---|---|
| مدلسازی گراف | ساخت و مدیریت گراف بدونجهت بر اساس داده واقعی |
| خواندن داده | بارگذاری ساختار شبکه از فایل CSV |
| پیمایش | پیادهسازی BFS و DFS |
| کوتاهترین مسیر | محاسبه مسیر کوتاه با BFS و Dijkstra |
| تحلیل ساختاری | محاسبه معیارهای اولیه شبکه |
| Community Detection | شناسایی اجتماعهای موجود در شبکه |
| Small-World Analysis | مقایسه ضریب خوشهبندی با گراف مرجع |
| Link Prediction | پیشبینی لینکهای بالقوه با Jaccard |
| بصریسازی | تولید نمودارها و نمایشهای تصویری |
| تستپذیری | پوشش بخشهای اصلی با تستهای واحد |
| ساختار مهندسیشده | تفکیک مسئولیت فایلها و طراحی ماژولار |
| نام | نقش اصلی | مسئولیتها |
|---|---|---|
| آلان حاتمی | سرپرست و یکپارچهساز پروژه | مدیریت ساختار پروژه، تحلیل نهایی، مستندسازی، طراحی خروجیهای تصویری |
| سبحان رئیسی | توسعهدهنده الگوریتمها | پیادهسازی ساختار گراف، BFS و DFS |
| محمدمهدی قادری | توسعهدهنده تحلیلها | پیادهسازی Dijkstra، تحلیلهای عددی و معیارهای شبکه |
| نام دیتاست | Facebook Ego Network |
| منبع | Stanford Network Analysis Project (SNAP) |
| نوع داده | شبکه اجتماعی |
| فرمت فایل | CSV |
| مسیر داده | data/social_network.csv |
| ستونها | source, target |
در این دیتاست، هر سطر نشاندهندهی یک رابطه بین دو گره در شبکه است. با توجه به ماهیت پروژه، این روابط بهصورت بدونجهت مدلسازی شدهاند؛ یعنی ارتباط بین u و v معادل ارتباط بین v و u در نظر گرفته میشود.
| شاخص | مقدار |
|---|---|
| تعداد گرهها | 4039 |
| تعداد یالها | 88234 |
| نوع گراف | بدونجهت |
| نوع داده | شبکه اجتماعی واقعی |
| منبع داده | SNAP |
پروژه با رویکرد ماژولار طراحی شده تا خوانایی، قابلیت نگهداری و تستپذیری آن افزایش یابد. هر فایل مسئولیت مشخصی دارد و کل سامانه بهصورت یک pipeline تحلیلی اجرا میشود.
CSV Dataset
↓
Graph Construction
↓
Traversal Algorithms
↓
Structural Analysis
↓
Community Detection
↓
Link Prediction
↓
Visualization & Output Export
| فایل | مسئولیت |
|---|---|
src/main.py |
نقطه شروع برنامه و اجرای کل فرایند |
src/graph_manager.py |
مدیریت ساختار گراف، گرهها، یالها و بارگذاری داده |
src/algorithms.py |
پیادهسازی BFS، DFS و Dijkstra |
src/analyzer.py |
تحلیل شبکه، محاسبه شاخصها و تولید خروجیهای تصویری |
tests/ |
مجموعه تستهای واحد و اعتبارسنجی عملکرد |
docs/ |
مستندات تکمیلی و گزارش پروژه |
benchmarks/ |
محل ذخیره نمودارها و خروجیهای نهایی |
social-network-analysis/
├── src/
│ ├── main.py
│ ├── graph_manager.py
│ ├── algorithms.py
│ └── analyzer.py
├── data/
│ └── social_network.csv
├── docs/
│ ├── dataset.md
│ └── report.md
├── benchmarks/
│ ├── degree_distribution.png
│ ├── network_plot.png
│ └── communities.png
├── tests/
│ ├── conftest.py
│ ├── test_graph_manager.py
│ ├── test_algorithms.py
│ └── test_analyzer.py
├── pyproject.toml
└── README.md
گراف با استفاده از ساختار داده مناسب برای ذخیره همسایگی گرهها ساخته شده است تا عملیات افزودن یال، جستوجو و پیمایش بهشکل کارآمد انجام شود.
برای پیمایش سطحبهسطح گراف و یافتن کوتاهترین مسیر در گرافهای بدونوزن استفاده شده است.
برای پیمایش عمقی شبکه و بررسی ساختار اتصال گرهها مورد استفاده قرار گرفته است.
برای محاسبه کوتاهترین مسیر در قالب کلاسیک الگوریتمهای گراف پیادهسازی شده است. اگرچه گراف در این پروژه وزندار نیست، اما پیادهسازی این الگوریتم بهمنظور تکمیل بخش مسیر کوتاه و تحلیل الگوریتمی انجام شده است.
برای سنجش اهمیت نسبی هر گره بر اساس تعداد یالهای متصل به آن.
برای کشف ساختار خوشهای و گروههای متراکم در شبکه.
برای مقایسه ویژگی خوشهبندی شبکه واقعی با یک گراف مرجع تصادفی و تحلیل رفتار ساختاری شبکه.
برای شناسایی جفتگرههایی که به دلیل شباهت در همسایگی، احتمال ایجاد ارتباط بین آنها بیشتر است.
| ابزار / کتابخانه | کاربرد |
|---|---|
| Python | زبان اصلی توسعه |
| NetworkX | تحلیل و پردازش گراف |
| Matplotlib | ترسیم نمودارها و نمایش خروجیها |
| Pandas | پردازش فایل CSV |
| Pytest | اجرای تستهای واحد |
pip install networkx matplotlib pandas pytestpython src/main.pypytestبرای اطمینان از صحت عملکرد بخشهای مختلف پروژه، مجموعهای از تستهای واحد برای اجزای اصلی پیادهسازی شده است.
- بارگذاری صحیح داده از CSV
- ایجاد گره و یال
- جلوگیری از افزودهشدن یالهای تکراری
- عملکرد BFS روی گرافهای ساده و ناپیوسته
- عملکرد DFS در پیمایش صحیح
- صحت کوتاهترین مسیر در BFS و Dijkstra
- رفتار گراف در حالت خالی و تکگرهی
- محاسبه برخی شاخصهای تحلیلی
- تولید فایلهای نموداری
- تشخیص اجتماعها
- پیشبینی لینک
tests/
├── conftest.py
├── test_graph_manager.py
├── test_algorithms.py
└── test_analyzer.py
در طراحی تستها، سناریوهای کوچک، قابلکنترل و تکرارپذیر استفاده شدهاند تا هم درستی الگوریتمی و هم پایداری اجرای برنامه بررسی شود.
پس از اجرای برنامه، خروجیهای تحلیلی و تصویری در پوشه benchmarks/ ذخیره میشوند.
| فایل | شرح |
|---|---|
benchmarks/degree_distribution.png |
نمودار توزیع درجه گرهها |
benchmarks/network_plot.png |
تصویر کلی شبکه |
benchmarks/communities.png |
نمایش اجتماعهای شناساییشده |
Dataset Loaded Successfully! Nodes: 4039, Edges: 88234
BFS Path: [0, 100]
Dijkstra Path: [0, 100]
Detected 13 communities.
Clustering Coefficient (Actual): 0.6055
Clustering Coefficient (Random Graph): 0.0109
Top Jaccard links:
(1430, 1560): 0.5000
(1973, 2639): 0.3973
(2151, 2198): 0.3558
(2434, 2555): 0.3064
(2835, 3149): 0.2222
All tasks completed successfully.
| شاخص | مقدار |
|---|---|
| Nodes | 4039 |
| Edges | 88234 |
| Detected Communities | 13 |
| Clustering Coefficient (Actual) | 0.6055 |
| Clustering Coefficient (Random Graph) | 0.0109 |
شکل ۱: توزیع درجه گرهها در شبکه اجتماعی
شکل ۲: نمایش ساختار کلی گراف شبکه
شکل ۳: نمایش اجتماعهای شناساییشده در شبکه
نتایج بهدستآمده نشان میدهند که شبکه مورد مطالعه دارای خوشهبندی بالا و ساختار اجتماعی مشخص است. ضریب خوشهبندی شبکه واقعی بهطور قابلتوجهی بزرگتر از گراف تصادفی مرجع است؛ این موضوع با انتظار نظری از شبکههای اجتماعی همخوانی دارد، زیرا در چنین شبکههایی دوستانِ یک فرد معمولاً با یکدیگر نیز در ارتباط هستند.
همچنین شناسایی 13 اجتماع در گراف، وجود ساختارهای محلی و خوشههای ارتباطی را تأیید میکند. در کنار این، امتیازهای Jaccard برای برخی جفتگرهها نشان میدهد که شباهت در همسایگی میتواند مبنایی مناسب برای پیشبینی لینکهای آینده باشد.
| موضوع | توضیح |
|---|---|
| نوع گراف | گراف بهصورت بدونجهت مدلسازی شده است |
| وزن یالها | یالها وزندار نیستند |
| Randomness | بخشی از نتایج تحلیلی یا بصری ممکن است تحت تأثیر پارامترهای تصادفی قرار گیرند |
| Small-World | صرف مقایسه clustering coefficient برای نتیجهگیری کامل کافی نیست و average path length نیز میتواند بررسی شود |
| تعمیم نتایج | نتایج این تحلیل محدود به همین دیتاست است |
| هویت کاربران | دادهها ناشناس هستند و نباید به اشخاص واقعی نسبت داده شوند |
برای افزایش قابلیت اعتماد به نتایج:
- ساختار پروژه بهصورت شفاف و ماژولار طراحی شده است.
- مسیر اجرای پروژه مشخص است.
- تستهای واحد برای اجزای اصلی پروژه پیادهسازی شدهاند.
- خروجیهای گرافیکی پس از هر اجرا قابل تولید مجدد هستند.
- داده ورودی مشخص، محدود و مستند است.
برای بازتولید کاملتر نتایج، پیشنهاد میشود در نسخههای بعدی seed ثابت برای بخشهای تصادفی نیز ثبت شود.
- Stanford Network Analysis Project (SNAP) — Facebook Ego Network Dataset
- NetworkX Documentation — https://networkx.org/
- Matplotlib Documentation — https://matplotlib.org/
- Dijkstra, E. W. — A note on two problems in connexion with graphs.
- Jaccard Similarity — کاربرد در تحلیل شباهت و پیشبینی لینک در شبکهها
- Watts, D. J. & Strogatz, S. H. — Collective dynamics of small-world networks.
- افزودن PageRank
- محاسبه Betweenness Centrality
- محاسبه Closeness Centrality
- تحلیل Connected Components
- افزودن Weighted Graph Support
- تولید JSON Export
- طراحی رابط کاربری گرافیکی
- مقایسه عملکرد الگوریتمها روی چند دیتاست
- افزودن گزارش آماری کاملتر
- توسعه Benchmarkهای زمانی و حافظه
| بخش | وضعیت |
|---|---|
| مدلسازی گراف | تکمیل شده |
| بارگذاری داده | تکمیل شده |
| پیمایش BFS/DFS | تکمیل شده |
| مسیر کوتاه | تکمیل شده |
| تحلیل شبکه | تکمیل شده |
| تشخیص اجتماع | تکمیل شده |
| پیشبینی لینک | تکمیل شده |
| بصریسازی | تکمیل شده |
| مستندسازی | تکمیل شده |
| تستها | تکمیل شده |
Final Academic Project – Social Network Graph Analysis
Prepared as a structured university team project with emphasis on graph theory, algorithmic correctness, analysis quality, and professional documentation.