عنوان
ارائه يک روش جديد براي نمونه برداري از شبکه هاي اجتماعي
نویسنده (گان)
سقطي جلالي,زينب;ميبدي,محمدرضا;رضوانيان,عليرضا
چکیده مقاله
در سال¬هاي اخير تحليل شبکه¬هاي اجتماعي توسعه چشمگيري داشته است اما با توجه به بزرگي شبکه¬هاي اجتماعي، اعمال الگوريتم¬ها و تحليل مستقيم بر روي شبکه وجود ندارد بنابراين از نمونه برداري براي انجام تحليل استفاده مي¬شود. اکثر روش¬هاي نمونه¬برداري به انتخاب تصادفي رئوس يا يال¬ها تاکيد دارند و به خوبي نمي¬توانند خصوصيات شبکه اوليه را حفظ کنند در حالي که هدف اصلي از نمونه¬برداري، توليد شبکه¬ نمونه¬اي با شباهت بالا به شبکه اوليه است تا بتوان به تحليل¬هاي بدست آمده به خوبي اعتماد کرد. در اين مقاله، يک روش جديد براي نمونه¬برداري از شبکه¬هاي اجتماعي به کمک درخت¬هاي پوشا براي گراف¬هاي بدون وزن ارائه مي¬گردد. در الگوريتم پيشنهادي در ابتدا چندين درخت پوشا از نقاط شروع تصادفي بدست مي¬آيد. سپس يال¬هاي به دست آمده در اين درخت¬هاي پوشا براساس تعداد دفعات تکرارشان رتبه¬بندي شده و در نهايت گراف نمونه توسط مجموعه¬اي از يال¬هاي با رتبه¬ بالا ايجاد مي¬شود. ايده اصلي اين روش بر اين اساس استوار است که يال¬هايي که در درخت¬هاي پوشاي مختلف تکرار مي¬شوند داراي خصوصيات ساختاري مشابه با شبکه هستند و نمونه¬اي که حاوي اين يال¬ها است، خصوصيات مختلفي از شبکه اوليه را داراست. براي ارزيابي کارايي روش پيشنهادي، آزمايشات متعددي ترتيب داده شده است و نتايج الگوريتم پيشنهادي با ساير الگوريتم¬هاي نمونه¬برداري مقايسه شده¬اند که نتايج بدست آمده بيان¬گر اين است که روش پيشنهادي به مراتب بهتر از ساير روشهاي متداول عمل مي¬کند.

متن کامل مقاله