معصومه زجاجی - دانشجوی دکترا، گروه کامپیوتر، دانشگاه آزاد اسلامی واحد میبد، میبد
محمدجواد کارگر - استادیار، گروه کامپیوتر، دانشگاه علم و فرهنگ، تهران

گراف ها نقش مهمی را در سیستم های پیچیده ایفا می کنند از شبکه های کامپیوتری گرفته تا حوزه های بیولوژی و جامعه شناسی، درواقع هر رابطه M:N در اصطلاح پایگاه دادهای می تواند به عنوان گراف ارائه شود. با توجه به محبوبیت و گسترش روز افزونشبکه های اجتماعی آنلاین، تجزیه و تحلیل آنها مورد توجه بسیاری از پژوهشگران در حوزه های مختلف علمی قرار گرفته است اعماز جامعه شناسی، بازاریابی و غیره. در این تحقیق ابتدا گراف کاوی در حوزه های مختلف نرم افزار، تصویر، سبد کالا و... بررسی وگراف کاوی در شبکه های اجتماعی انتخاب شده است. سپس روشهای مطرح شده در حوزه های مختلف گراف کاوی شبکه هایاجتماعی شامل شناسایی میزان نفوذ پذیری، مدل ها، متریک ها و پویایی ها، شناخت روابط و تعاملات گروهی، انتشار اطلاعات،روش های مختلف تشخیص همبستگی ها در گراف کاوی در نظر گرفته شده است.شبکه های اجتماعی شامل چندین همبستگی می باشند که هر همبستگی با مجموعه ای از نودهایی تعریف می شود که ارتباطات درداخل همبستگی فشرده تر از همبستگی های دیگر میباشد. روش های متفاوتی در این زمینه ارائه شده اند اما آنچه حائز اهمیت استنادیده گرفتن همپوشانی همبستگی های می باشد. هدف از ارائه این مقاله، تحلیل روش های مطرح شده در حوزه تشخیصهمبستگی های همپوشان می باشد. یکی از مشکلات این الگوریتم ها پیچیدگی زمانی آنهاست که در گراف هایی با مقیاس بزرگ نمودپیدا می کند. با توجه به اینکه برای گراف کاوی از ماتریس مجاورتی استفاده می شود بنابراین نمی توان به زمان کمتر از ((O(n(2)) دستیافت. اگرچه با ظهور الگوریتم های معنایی شاید بتوان تا حدودی این زمان را تقلیل داد.

شبکه های اجتماعی، گراف کاوی، همبستگی، همبستگی های همپوشاند