ارایه روشی مبتنی بر طیف گراف برای تشخیص انجمن‌ها در شبکه‌های اجتماعی

روش های مبتنی بر طیف گراف٬ یکی از روش های ریاضی است که ما می توانیم بر اساس مقادیر و بردارهای ویژه ماتریس های مختلف بر روی گراف ها تجزیه و تحلیل های گسترده ای انجام دهیم. یکی از مواردی که در آن از این روش بسیار استفاده می‌شود٬ تشخیص جوامع در شبکه های اجتماعی است که در آن با استفاده از مقادیر و بردارهای ویژه٬ گراف های بزرگ را به خوشه های با اندازه های متفاوت تقسیم بندی می کنیم. بیش‌تر روش های مبتنی بر طیف گراف٬ روش‌هایی با هزینه ی زمانی بالایی هستند٬ چرا که محاسبه مقادیر و بردارهای ویژه به تنهایی به اندازه ی O(n^3) زمان می برند٬٬ لذا به دنبال آن هستیم که الگوریتمی ارایه دهیم که علاوه بر دارا بودن پایه و اساس ریاضی٬٬ از هزینه زمانی کم‌تری برخوردار باشند. از جمله مواردی که تا کنون در جوامع علمی مطرح شده است می‌توان به موارد زیر اشاره نمود:

روش‌ها و الگوریتم‌های چند سطحی گراف٬ روش بازگشتی توان٬ بازترتیبی ماتریس‌ها برای تشخیص جوامع٬ پارتیشن بندی برداری٬ روش‌های تقسیمی مانند فاصله زاویه‌ای بردارها٬ استفاده از بردارهای ویژه ماتریس لاپلاس

 

ارائه دهنده پروژه

سینا عبداللهی
پست الکترونیک: sinaabdollahi [at] ut.ac.ir
عضو سابق
 

استاد راهنما

مسعود اسدپور
استادیار
اتاق: ساختمان جدید، 720
تلفن: 61114951
پست الکترونیکی: asadpour [AT] ut.ac.ir