Skip to main content
SUPERVISOR
Naser Ghadiri modaress
ناصر قدیری مدرس (استاد راهنما)
 
STUDENT
Mahsa Asadi
مهسا اسدی

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1394

TITLE

A Scalable Method for One-mode Projection of Bipartite Networks
Human beings have been looking for models and methods to organize, dir=ltr Bipartite graph has a specific application and importance among the variety of presenting methods since the majority of systems in this field, such as recommender systems naturally model bipartite. Most of bipartite networks tend to cluster one side of graph behavior in order to recognize communications and interactions between members of that side and actually discover similar members. One-mode projection technique is an appropriate method for that purpose which recently has come to attention broadly in different areas such as Social Networks, Health Care systems, medicine and treatment, etc. Generally, some part of primary information of main bipartite graph will be missed under the projection. Hence, scientists have been trying to provide a method to determine the appropriate weight for yield projected edges in order to minimize information loss. On the other hand, performance level on big data is an important challenge within these methods. The majority of investigated databases in the field of bipartite network projection are huge, consequently, executing projection procedure takes lots of times. Therefore, we need methods which have acceptable speed as they keep accuracy and precision in projection. The following research aims to improve the existed algorithm speed by introducing a scalable method based on resource allocation for bipartite network projection, and we try to provide the appropriate speed while preserving precision through transferring the needed operations on a distributed infrastructure like Hadoop. Moreover, as a case study, we evaluate the performance of presented scalable algorithm in the field of Social Network which results to a lesser projection operation time in comparison to the undistributed mode. Also, we compared our proposed method with collaborative filtering method, a well known algorithm in recommendation field and as a result our method had higher execution speed overall. With using the biggest dataset, orkut, the proposed method has higher speed than the scalable CF by 33%. Then, we evaluate the scalability of the introduced method by a scalability metric named Speedup, which showed good scalability. Investigation accompanied with analyzing the execution time increasing in different states and configurations based on input data size growth. Keywords Bipartite Networks, Projection, Recommendation, Scalable
دشواری در نگهداری و استفاده از حجم بسیار زیاد اطلاعات باعث شده است که انسان همواره به دنبال مدل‌ها و روش‌هایی برای سازمان‌دهی، طبقه‌بندی، فشرده‌سازی و فیلتر کردن اطلاعات باشد. از جمله روش‌های فشرده‌سازی اطلاعات می‌توان به سیستم‌های توصیه‌گر اشاره کرد که به کمک روش‌های محاسباتی و هوش مصنوعی از میان انبوه اطلاعات موجود، آنچه را مورد نیاز است در زمان کمتری پیدا کرده و به کاربر پیشنهاد می‌دهند. همچنین از مدل‌های پر کاربرد نمایش سیستم‌ها و اطلاعات نهفته در آن‌ها، می‌توان از نمایش به شکل گراف نام برد. از بین انواع روش‌های نمایش در این دامنه، گراف دوبخشی کاربرد و اهمیت خاصی دارد، چرا که بسیاری از سیستم‌ها مانند سیستم‌های توصیه‌گر به طور طبیعی به صورت دوبخشی مدل می‌شوند. در اغلب مدل‌های شیکه‌های دوبخشی گرایش به سمت خوشه‌بندی رفتار یک سمت گراف وجود دارد تا بتوان ارتباطات و تعاملات بین اعضای یک سمت مجموعه را یافت و در واقع اعضای مشابه یکدیگر را پیدا نمود. روش نگاشت تک ‌حالته یک روش مناسب برای این منظور است که اخیراً در دامنه‌های مختلفی مانند شبکه‌های اجتماعی، سیستم‌های مربوط به سلامت، دارو و درمان و مانند آن به طور جدی و گسترده مورد توجه قرار گرفته است. در اثر نگاشت همواره بخشی از اطلاعات اولیه گراف دوبخشی اصلی از دست خواهد رفت، لذا پژوهشگران می‌کوشند تا با فراهم آوردن یک روش تعیین وزن مناسب برای یال‌های حاصل از نگاشت، حذف اطلاعات مهم و اساسی گراف را به حداقل برسانند. از سوی دیگر، یک چالش مهم در این روش‌ها میزان کارآیی برای داده‌های حجیم است. اغلب پایگاه داده‌های مورد بررسی در دامنه نگاشت شبکه‌های دوبخشی بسیار عظیم می‌باشند و در نتیجه اجرای عملیات نگاشت بسیار زمان‌بر خواهد بود، بنابرین نیازمند روش‌هایی هستیم که ضمن حفظ دقت و صحت در نگاشت، از سرعت عمل مناسبی نیز برخوردار باشند. در این پژوهش با هدف بهبود سرعت الگوریتم‌ موجود به ارائه یک روش مقیاس‌پذیر مبتنی بر تخصیص منبع برای نگاشت شبکه‌های دوبخشی خواهیم پرداخت و می‌کوشیم تا با انتقال عملیات مورد نیاز بر روی بستری توزیع شده مانند هدوپ، ضمن حفظ دقت، سرعت مطلوب را تامین نماییم. همچنین به عنوان مورد مطالعاتی، کارایی الگوریتم مقیاس‌پذیر ارائه شده را در دامنه شبکه اجتماعی مورد سنجش قرار می‌دهیم که در نتیجه آن انجام عملیات نگاشت در زمان کوتاه‌تری نسبت به حالت غیر توزیع شده حاصل خواهد شد. همچنین الگوریتم ارائه شده را با یک الگوریتم مقیاس‌پذیر شناخته شده در دامنه توصیه به نام الگوریتم فیلتر کردن همکارانه مقایسه کرده که در نتیجه آن الگوریتم ارائه شده در مجموع سرعت اجرای بیشتری داشته است به طوری‌‌که اجرای الگوریتم مقیاس‌پذیر ارائه شده به ازای بزرگترین مجموعه داده استفاده شده به نام orkut از اجرای الگوریتم مقیاس‌پذیر فیلتر کردن همکارانه 33% سریع‌تر بوده است‌. سپس مقیاس‌پذیری روش ارائه شده را توسط یک معیار ارزیابی به نام Speedup بررسی نموده که در نتیجه آن مقیاس‌پذیری قابل قبولی به دست آمده است و همچنین تحلیل نمودار میزان افزایش زمان اجرا در حالات و تنظیمات مختلف بر اساس رشد اندازه داده ورودی را مورد ارزیابی قرار می‌دهیم. کلمات کلیدی: 1- شبکه دوبخشی 2-نگاشت 3-توصیه 4- مقیاس‌پذیر

ارتقاء امنیت وب با وف بومی