تشخيص ساختار جوامع همپوشان در شبكه هاي اجتماعي با استفاده از تجزيه شبكه

بسياري از ساختارهاي پيچيده را مي توان به صورت يك شبكه در نظر گرفت. جاده ها، پايگاه هاي اينترنتي، شبكه هاي اجتماعي، ارتباطات سازماني، روابط خويشاوندي، تبادل نام هاي الكترونيك، تماس هاي تلفني و تراكنش هاي مالي تنها چند نمونه از اين شبكه ها هستند. يكي از مهم ترين فعاليت هايي كه در رابطه با اين تحقيقات مطرح شده، پيدا كردن گروه هايي از افراد است كه ممكن است بيشتر از سايرين باهم در ارتباط باشند كه اين مسيله تحت عنوان تشخيص ساختار جوامع در شبكه هاي اجتماعي، شناخته مي شود. روش هاي متعددي با پياده سازي مختلف وجود دارند كه هركدام داراي نقاط ضعف و قوت مي باشند. برخي از اين نقاط ضعف عبارت اند از: زمان اجراي زياد، حساسيت به شرايط اوليه، نياز به تعيين مقادير پارامترهاي مختلف، عدم كارايي در گراف هاي بااتصال كم و عدم امكان مقياس پذيري. در الگوريتم پيشنهادي NDOCD تكنيك خوشه بندي گره ها را جهت شناسايي اتصالات جوامع بكار گرفته و به طور تكراري همه اتصالات تعيين كننده جوامع را حذف و شبكه را به يك شبكه با مولفه هاي كوچك تر تقسيم مي كند. تجزيه شبكه و بهينه سازي تكنيك خوشه بندي گره به طور مشترك براي ساخت يك الگوريتم كارا و باصرفه ازلحاظ زماني بكار مي رود. نتايج بررسي ها نشان مي دهد كه الگوريتم طراحي شده در جريان تحقيقات اين مقاله ازلحاظ كارايي و زمان اجرا داراي برتري مشهودي بر اكثر الگوريتم هاي مطرح شده قبلي در اين زمينه است.