به نام پروردگار هدایت کننده به راه راست
دانشگاه اصفهان
ساختمان داده – دکتر رمضانی
پاییز ۰۲-۰۳
پروژه پنجم - شبکه اجتماعی
طراحان پروژه : امیرعلی گلی – محمد توکلی - امیرارشیا همت
اهداف پروژه :
- کار با ساختمان داده گراف
- پیاده‌سازی عملیات‌های پرکاربرد گراف
- آشنایی با فرمت داده جیسان
در این پروژه قرار است با استفاده از گراف یک شبکه اجتماعی مشابه لینکدین را شبیه‌سازی کنید.
شما برای این پروژه باید گراف را خودتان پیاده سازی کنید.
قبل از خواندن فایل زیر، ابتدا فایل Graph-Implementation را مطالعه کرده و سپس این فایل را مطالعه فرمایید.
هدف این پروژه پیاده‌سازی یک شبکه اجتماعی برای لینک کردن افراد به هم براساس مهارت‌های هر شخص می‌باشد. در این پروژه باید به هرکدام از کاربرهای انتخابی، افرادی دیگر که در این شبکه اجتماعی عضو هستند را برای کانکت شدن به یکدیگر پیشنهاد دهید(همانند شبکه‌هایی نظیر لینکدین که افرادی را برای دنبال کردن به شما پیشنهاد می‌دهد)
حال بیایید کمی پروژه را دقیق‌تر بررسی نماییم. تصور کنید شما در شبکه اجتماعی‌تان فردی با مشخصات زیر دارید.
مشخصات کلی:
- آیدی کاربر : 1
- نام: ارشیا
- نام خانوادگی: همت
- تاریخ تولد: 2/5/1380
مشخصات تخصصی:
- محل دانشگاه: دانشگاه اصفهان
- رشته تحصیلی: مهندسی کامپیوتر
- محل کار: مارکوت
تخصص‌های شخص:
- یادگیری ماشین
- یادگیری تقویتی
- برنامه‌نویسی بلاکچین
لیست کانکشن‌ها:
- امیرعلی گلی
- توکل محمدی
- رستم علوی نیا
- جهان امیری
دقت کنید که در فایل ورودی لیست کانکشن¬ها بصورت لیست آیدی¬های افراد است.
همانطور که مشاهده کردید، هر شخص چهار فیلد دارد که شامل اطلاعات عمومی، اطلاعات تخصصی، تخصص‌ها و همینطور کانکشن‌های وی می‌باشد. حال شما باید براساس کانکشن‌های هر کانکشن، به آن شخص هدف(مثلا در این مثال ارشیا هست) یک‌سری از کانکشن‌های کانکشن‌های آن را پیشنهاد دهید.
نکته مهم: صرفا کانکشن‌های درجه اول مد نظر نیستند و باید تا پنج درجه این کانکشن‌ها بررسی شود!
احتمالا نکته مهم بالا کمی برایتان گنگ است، پس بیایید با هم بیشتر بررسی کنیم.
فرض کنید، ارشیا یک کانکشن به‌نام امیرعلی دارد که اون هم یک کانکشن به نام احسان دارد و احسان هم یک کانکشن به‌نام کامبیز دارد. حالا می‌توانیم بگوییم کامبیز با دو واسطه به ارشیا متصل است و به این معنی است که درجه کامبیز برای ارشیا سه می‌باشد. به بیان ساده‌تر می‌توانیم بگوییم:
حال شما باید برای پیشنهاد دادن افراد، تا پنج درجه را بررسی نمایید. در صورتی که یک نفر با شخص مدنظر(در این مثال ارشیا) از طریق کانکشن های مختلف ، درجات مختلفی داشته باشد، کمترین درجه آن در نظر گرفته می¬شود.
برای مثال فردی به نام علیرضا را در نظر بگیرید . اگر علیرضا هم کانکشن امیرعلی و هم کانکشن احسان باشد، برای پیدا کردن درجه علیرضا نسبت به ارشیا، باید کمترین درجه یعنی 2 را در نظر بگیریم.
اکنون شما باید بتوانید براساس خلاقیت خودتان، سعی کنید افرادی با نزدیک‌ترین تشابه را به فرد هدف پیشنهاد دهید. این پیشنهاد صرفا نباید با پیمایش برروی کانکشن‌ها باشد و موارد دیگری نظیر تخصص‌های اشخاص از اولویت خیلی بالایی برخوردار هستند که شما باید با خلاقیت خود، سعی کنید یک اولویت‌دهی درستی از تمام این موارد را داشته باشید.
بیایید پیرامون این موضوع باهم مثالی را حل کنیم.
فرض کنید نقی معمولی با مشخصات زیر موجود است:
- آیدی کاربر : 1245
- نام: نقی
- نام خانوادگی: معمولی
- تاریخ تولد: 1/1/1340
- محل دانشگاه: دانشگاه نوشیروانی بابل
- رشته تحصیلی: مهندسی کامپیوتر
- محل کار: فدراسیون کشتی
- تخصص: o گچ‌کاری o داور کشتی o پرورش ماهی قرمز
فرض کنید نقی با شخص هدف ما (مثلا ارشیا) درجه دو دارد.
آیا بنظر شما باید این شخص را با توجه به مشخصاتی که از فرد هدف دارید باید به شخص هدف کانکت کنید؟
احتمالا جواب‌تان خیر است؛ پس نکته‌ای که حائز اهمیت این است که صرفا با پیمایش کردن برای روی کانکشن‌های یک فرد و یافتن درجه نمی‌توانید از پیشنهاد دادن آن شخص به شخص هدف مطمئن شوید.
راهنمایی: اصلی‌ترین مشخصاتی که باید مدنظر قرار گیرند، مسلما مهارت افراد است چون بسیاری از ارتباط افراد براساس مهارت‌ها و تخصص‌های مشترک آن‌ها شکل می‌گیرد؛ پس حتما تخصص را در بالاترین اولویت قرار دهید و سعی کنید براساس اطلاعات داده شده موارد دیگری که برای لینک شدن(نظیر دانشگاه و رشته و حتی درجه‌ای که با شخص هدف دارند) مهم هستند را امتیاز دهید و بر همین اساس افرادی را به شخص هدف پیشنهاد دهید(درواقع باید برای هرکدام از ویژگی‌ها یک وزن درنظر بگیرید و بر آن اساس میزان اولویت برای پیشنهاد دادن را مشخص کنید.)
به شما یک فایل json حاوی اطلاعات اشخاص داده می¬شود پس از خواندن اطلاعات فایل json ، به عنوان ورودی آیدی یکی از افراد داده می‌شود و برنامه شما باید ۲۰ فرد را برای کانکت شدن به ترتیب اولویت پیشنهاد دهد.
- امکان اینکه کاربر هدف بگویید کدام یکی از موارد برایش اولویت بیشتری دارد(مثلا کاربر هدف در ورودی بیان کند که مهم‌ترین اولویت برای او درجه کانکشن و سپس مهارت و سپس محل سکونت است؛ توجه کنید شما در این‌صورت نباید همه کانکشن‌های درجه او را به آن پیشنهاد دهید بلکه صرفا باید ضریب بیشتری برای کانکشن‌ها قائل شوید)
- امکان ثبت نام کردن افراد جدید در شبکه اجتماعی و دادن پیشنهاد برای کانکت شدن به دیگران با توجه به مهارت ها و .... پس از ثبت نام کردن
- سایر بخش‌های یک شبکه اجتماعی مثل گرافیکی زدن آن ،پست، کامنت و ... را می‌توانید برای زیباتر کردن پروژه خود اضافه نمایید؛ اما از لحاظ نمره‌ی اضافه وزن کمتری نسبت به قابلیت‌های الگوریتمی دارند.
- این پروژه بصورت گروه های دونفری باید پیاده سازی شود.
- بستر پیاده سازی پروژه روی گیت‌هاب می‌باشد.
- سعی کنید هریک از بخش‌ها را در یک کامیت جداگانه انجام دهید.
- رعایت اصول کدنویسی تمیز بخش بسیار زیادی از نمره را به خود اختصاص می‌دهد و درصورتی که کد کاملا به شکل غیراصولی پیاده سازی شده باشد. تحویل گرفته نمی‌شود.
- استفاده از هر زبان، فریمورک و رابط‌های گرافیکی کاملا آزاد است. ( به غیر از زبان و فریمورک های پایتون )
- به افرادی که از تکلنولوژی‌های جدید استفاده کنند، توکن تمدید اضافه‌تر داده خواهد شد.