تحليلي بر روش هاي تشخيص همبستگي هاي همپوشان در شبكه هاي اجتماعي

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