اهمیت شناسایی تشکلها
تشکلها اطلاعات ارزشمندی در مورد نوع ارتباط بازیگران، نحوه انتقال اطلاعات بین آنها و نحوه توزیع بازیگران در شبکههای اجتماعی ارائه میکنند و در واقع به عنوان جزء اصلی سازنده این شبکهها محوب میشوند.
شناسایی تشکل ها در شبکه ها از اهمیت زیادی برخوردار است، زیرا با توجه به تعداد زیاد کاربران و اطلاعات بیشمار بر روی شبکه های اینترنت، امکان آنالیز داده ها و انجام درخواست[۳۹]ها میسر نخواهد شد. مثلا تشکلهای موجود در شبکه وب، با مجموعههای صفحات وب موجود بر روی موضوعات مرتبط متناظر بوده، تشخیص آنها منجر به یافتن صفحات مشابه و مربوط به هم می شود. این موضوع برای بسیاری از کاربردها، مثلا موتورهای جستجو و سیستمهای پیشنهاددهنده[۴۰] متناسب است. همچنین، تشکلهای موجود در شبکه های اجتماعی با واحدهای اجتماعی[۴۱] تناظر دارند[۲۱]. از دیگر کاربردهای شناسایی تشکل، در شبکه های مبتنی بر متن[۴۲] مثل [۴۳]DBLP یا [۴۴]Twitter مطرح می شود. از یک دیدگاه، در این شبکه، رأسها با اسناد[۴۵] تناظر داشته و دو رأس، در صورتیکه یک نویسنده سند متناظر با آنها را نوشته باشد با یک یال به هم مربوط میشوند. نتیجه شناسایی تشکلها در این شبکه، یافتن اسناد با محتوای مشابه است. از طرف دیگر یکی دیگر از مهمترین کاربرد شناسایی تشکل در شبکه هایی از این دست ، مسالهی رفع ابهام در نام نویسندگان[۴۶] است. بدین ترتیب که با شناسایی تشکلهای مربوط به نویسندگانی با نامهای مشابه، میتوان دریافت که هر کدام از این نویسندگان به چه تشکلی تعلق دارند و در نتیجه بین آنها تمیز داد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
یکی دیگر از کاربردهای اصلی شناسایی تشکلها در کسب و کار الکترونیکی است. از جمله کاربردها در این حوزه میتوان به قسمتبندی بازار، بازاریابی ویروسی، پیدا کردن افراد تاثیرگذار و حامیان تشکلهای اعتماد در وب اشاره کرد. یادگیری مشارکتی از جمله رویکردهای موفق یادگیری است که طی آن، فراگیران طی تعامل با یکدیگر مباحث را فرا میگیرند. به سبب تاثیر مثبت یادگیری این روش در یادگیری، شیوه های نوین آموزش الکترونیکی به دنبال تحقق آن در محیط مجازی و به صورت خاص، در شبکه های اجتماعی میباشند. از چالشهای مهم پیش روی یادگیری مشارکتی، چگونگی ایجاد تعامل و نحوه نظارت معلم بر فراگیران میباشد. شناسایی تشکلهای اجتماعی می تواند در مواجهه با این چالشها به معلمان یاری رساند.
کاربرد دیگر تشکلها که شناسایی آنها را با اهمیت می کند در جامعه شناسی و روانشناسی است. با بهره گرفتن از تشکل ها در این علوم، جامعه مجازی و رفتار هر فرد در جامعه مجازی به نحو کاراتری بررسی می شود و با الگو برداری از این رفتارها، دنیای واقعی بهتر مدل می شود. از مدل به دست آمده برای اتخاذ تصمیمات در بسیاری از زمینه ها استفاده می شود.
انگیزه از انجام این پایان نامه
همانطور که پیشتر نیز بیان شد، تحلیل شبکه های اجتماعی به عنوان یک تکنیک کلیدی در جامعه شناسی، انسان شناسی، روانشناسی اجتماعی، بازاریابی و مدیریت بازار، مطالعات سازمانی، سیاست، اقتصاد و… همانند یک موضوع محبوبدر زمینه تفکر و مطالعه پدیدار شده است.
تشکلها به سبب ارائه اطلاعات مفیدی در مورد نوع ارتباط کاربران حاظر در شبکه، نحوه توزیع آنها و نحوه انتقال اطلاعات بین بازیگران در شبکههای، به عنوان جزء اصلی سازنده این شبکهها محسوب میشوند. بنابراین شناسایی تشکلها امری بسیار مهم و حیاتی است.
روشهای پیشین برای شناسایی تشکلها فقط از اطلاعات ساختاری و لینکهای موجود در شبکه استفاده میکردند اما دادههایی که امروزه در رسانههای اجتماعی[۴۷] یافت میشوند علاوه بر لینکهای بین گرهها شامل محتوایی برای توصیف خود گرهها یا ارتباطات بین آنهاست. در سایتهای اینترنتی شبکه های اجتماعی، کاربران دارای صفحات پروفایل شخصی[۴۸] هستند، نظرات[۴۹] خود را در شبکه به اشتراک میگذارند و مقالات[۵۰] را بازیابی و آشکار می کنند. در سایتهای بحث در مورد عکسها و فیلمها، مشتریان درمورد عکسها و فیلمها توضیح می دهند و از متنهای کوتاه برای برچسب زدن[۵۱] به آنها استفاده می کنند. اما با توجه به حجم بالای محتوای متنی و رشد و توسعه بسیار سریع آنها، مطالعه همه این سندها و استخراج اطلاعات از آنها کار بسیار دشواری است. روشهای مدل کردن عناوین به ما این امکان را میدهد که این حجم بالا از اطلاعات را بررسی کرده و اطلاعات لازم را از آنها استخراج کنیم.
اهمیت شناسایی تشکلها با توجه به تمامی مطالب ذکر شده در بالا و موارد و مشکلات موجود در اکثر روشهای متداول برای شناسایی تشکلها، ما را بر آن داشت تا در این پایان نامه، از اطلاعات متنی نیز در کنار داده های معمول استفاده کنیم بهطوریکه تشکلهای مناسب تری را کشف کنیم که هم ساختاری را داشته باشد که اعضای نزدیکتر را در یک گروه قرار دهد هم اینکه از نظر معنایی قابل فهمتر و قابل توصیفتر باشند.
نگاه کلی به فصول رساله
این رساله مشتمل بر پنج فصل میباشد که در ادامه مقدمه، در فصل دوم به بررسی و تحلیل روشهای ارائه شده در این حوزه خواهیم پرداخت. در فصل سوم، روشهای پیشنهادی با تمامی جزئیات ارائه خواهند شد و در فصل چهارم، نتایج حاصل از اجرای آنها بر روی مجموه داده[۵۲]های معرفی شده به همراه تحلیل نتایج آورده شده است. در انتها در فصل پنجم به شرح نتیجه گیری و کارهای آینده پرداختهایم.
فصل دوم
مروری بر کارهای پیشین
فصل دوم:
مروری بر کارهای انجام شده
مقدمه
مطالعه ساختار تشکل در شبکه ها تاریخچهای بسیار طولانی داشته و الگوریتمهایی که به این منظور مطرحشدهاند در دو دسته کلی قرار میگیرند:
دسته اول: الگوریتمهایی که فقط بر اساس ساختار ارتباط [۵۳] بین رأسها عمل میکنند.
دسته دوم: الگوریتمهایی که علاوه بر ساختار ارتباط بین رأسها، از اطلاعات مفهومی گراف شبکه نیز استفاده میکنند.
همانطور که در فصل قبل اشاره شد، تشکل به گروهی از اعضا اطلاق می شود که از لحاظ لینک، ارتباطات بسیار نزدیکی با یکدیگر دارند و از نظر محتوا، در یک حوزه مشترک فعالیت می کنند.
در این فصل با توجه به تعریف فوق و تعاریف قبلی، به مطالعه روشهای ارائه شده در این حوزه از نقطه نظرات گوناگون خواهیم پرداخت.
روشهای ارائه شده
همانطور که در بخش ۲-۱ اشار شد، الگوریتمهای شناسایی تشکل در دو دسته کلی قرار میگیرند که دسته اول بر اساس ساختار لینک میباشد. خود روشهای تعریف شده در این حوزه در سه دستهی کلی زیر قرار میگیرند:
روشهایی که به دنبال بهینه کردن[۵۴] یک هدف سراسری[۵۵] میباشند.
روشهایی که بر اساس بهینهسازی هیچ معیاری عمل نمیکنند.
روشهای مبتنی بر مدل [۵۶].
روشهای ارائه شده در دسته دوم به طور پراکنده، سعی در یافتن تشکلها بر اساس محتوا می کنند.
در ادامه نمونههایی از هر دسته را شرح خواهیم داد.
روشهای مبتنی بر لینک
بهینه کردن یک هدف سراسری
روشهایی که به دنبال بهینه کردن یک هدف سراسری میباشند، مانند بهینه کردن معیارهای اندازه برش گراف [۲۱] پیمانهای بودن[۵۷] [۲۲] و نوع فازی آن [۲۳]، مابین بودن[۲۴] و هدایت[۵۸] [۲۵] و یا بهینه کردن پارامترهای احتمالات موجود در GMM[59] [۲۶]در گروه اول جای دارند. الگوریتمهای افراز گراف[۶۰] و خوشهبندی سلسله مراتبی[۶۱] از این دستهاند.
۲-۳-۱-۱- افراز گراف در نظریه گراف و علوم کامپیوتر
مسئله افراز گراف[۲۱] شامل تقسیم رأسهای یک گراف در g گروه با اندازه های از پیش معلوم است به طوری که تعداد یالهای بین گروه ها که اندازه برش نامیده میشود کمینه شود(شکل ۲). این مسئله در راستای حل مسائلی همچون محاسبه موازی[۶۲]مطرح می شود. در اینجا هدف تخصیص پروسهها به پردازندههاست، به طوری که بار[۶۳] بر روی هر پردازنده به طور متعادل توزیع شود و از طرفی ارتباط بین پردازندهها که باعث کاهش سرعت اجرا میشود، کمینه شود. این مسئله NP-دشوار است و با الگوریتمهای مکاشفهای[۶۴] که بهترین آنها الگوریتم Kernighan-Lin [27] با زمان اجرای O(n3) است، قابل اجرا است.
به طور کلی پیدا کردن راه حل برای مسئله افراز گراف، چندان هم در تحلیل شبکه ها سودمند نیست، زیرا در شبکه ها، بر خلاف مسئله افراز گراف تعداد تشکلها مشخص نیست و لزومی هم بر هم اندازه بودن این تشکلها وجود ندارد. از طرفی، نیازی به کمینه کردن ارتباط بین تشکلها نیست، چرا که طبق انتظار، ارتباط بین تشکلهای بزرگ نسبت به ارتباط بین تشکلهای کوچک، بسیار بیشتر است. بنابراین، مسئله شناسایی تشکلها در شبکه ها تفاوت اساسی با مسئله افراز گراف دارد.
امروزه، تا حدی مشکلات این روش با بهره گرفتن از الگوریتمهای طیفی[۶۵] که از بردارهای ویژه[۶۶] ماتریس شبکه استفاده می کنند حل شده است[۲۸].
شکل۲-۱- افراز گراف.
خط قرمز نشاندهنده حل مسئله است که در آن رأسها به دو گروه با اندازه های یکسان
تقسیم شده و یالهای بین دو گروه، کمینه است.
راه حل بهتری که در این راستا ارائه می شود، روش های خوشه بندی سلسله مراتبی است.
۲-۳-۱-۲- خوشهبندی سلسله مراتبی
هدف این روشها شناسایی تقسیمبندی طبیعی شبکه ها بر اساس معیار شباهت[۶۷] بین رأسها یا قدرت[۶۸] ارتباطات بین آنهاست. این روشها در دو دسته کلی تودهای[۶۹] و تقسیم شونده[۷۰] جای میگیرند.
روشهای خوشهبندی سلسله مراتبی تودهای: در این روشها، در ابتدا شباهت بین هر زوج رأس بر اساس یک معیار محاسبهشده و یالهای بین آنها به ترتیب از بیشترین میزان شباهت به کمترین، به شبکه تهی اضافه میشوند. این روال میتواند در هر لحظه متوقف شود و اجزای حاصل، تشکلهای تشکیلشده تا آن لحظه هستند (شکل ۳٫ب). روشهای تودهای اغلب نمیتوانند تشکلهای شبکه را به طور صحیح شناسایی کنند، در نتیجه قابلاعتماد نیستند. به علاوه با توجه به اینکه رأسهای موجود در تشکلها شباهت قوی تری نسبت به دیگر رأسها دارند، در مراحل اولیه به هم متصل شده و رأسهای مرزی کنار گذاشته میشوند. بنابراین این روش، نسبت به روشهای تقسیم شونده در شناسایی تشکلها ضعیفتر عمل میکنند.
روشهای خوشهبندی سلسله مراتبی تقسیم شونده: این روشها با یک شبکه غیر تهی شروع کرده، یالهای مربوط به زوج رأسهایی که شباهت کمتری دارند به ترتیب حذف میشوند(شکل ۳٫الف). در روش ارائهشده توسط Grivan و Newmanیالهایی برای حذف انتخاب میشوند که معیار مابین[۷۱] بودن بیشتری داشته باشند. از مشکلات این روش میتوان به زمان اجرای بالای این روش اشاره کرد که O(n3) است[۲۹].
الف) ب)
شکل ۲-۲- الف) خوشهبندی سلسله مراتبی. ب) خوشهبندی تودهای
دایرههای پایین تصویر نماینده رأسهای گراف هستند.
خط نقطه چین در هر سطح، تشکل های آن سطح را نشان می دهد
۲-۳-۱-۳- الگوریتم CHEN
در [۲۴] معیار جدیدی به نام L برای انتخاب راس مناسب جهت اضافه نمودن به گروه، معرفی شده است. این الگوریتم سعی دارد تا این معیار را ماکزیمم کند. معیارهایی که تاکنون معرفی شده بودند در راستای افزایش یالهای داخلی و کاهش یالهای خارجی گروه هستند. مهمترین جنبهای که در این معیارها فراموش شده است تراکم گروه است. به عبارت دیگر، توجهی به رئوس دورافتاده[۷۲] ندارند. رئوس دورافتاده رئوسی هستند که با اضافه شدن به گروه تعداد یالهای خارجی را افزایش نمیدهند، در حالی که عضو گروه نیز نمیباشند. به طور مثال، گروهی را با یک میلیون یال داخلی و بدون یال خارجی تصور کنید که در آن هر راس به یک الی دو را متصل است. با وجود اسن نمی توان ادعا کرد که این مجموعه یک گروه خوب است. به همین دلیل معیار جدیدی به نام Lin معرفی شده است که نسان دهنده میانگین درجات گروه است.
که در آن IKi تعداد یالهای بین راس i و رئوس گروه S وجود دارد را نشان می دهد. به طور مشابه، معیار Lext نیز به همین شیوه تعریف می شود.
در این فرمول EKj تعداد یالهای بین راس j و رئوس داخل مجموعه N را نشان میدهد. این الگوریتم به دنبال افزایش مقدار Lin و کاهش Lext به صورت همزمان است. در همین راستا، معیار L بر اساس دو معیار Lin و Lext به صورت زیر تعریف می شود.