اهمیت شناسایی تشکل­ها

تشکل­‌ها اطلاعات ارزشمندی در مورد نوع ارتباط بازیگران، نحوه انتقال اطلاعات بین آنها و نحوه‌ توزیع بازیگران در شبکه‌های اجتماعی ارائه می‌کنند و در واقع به عنوان جزء اصلی سازنده این شبکه‌ها محوب می‌شوند.
شناسایی تشکل ها در شبکه­ ها از اهمیت زیادی برخوردار است، زیرا با توجه به تعداد زیاد کاربران و اطلاعات بی­شمار بر روی شبکه ­های اینترنت، امکان آنالیز داده ­ها و انجام درخواست­[۳۹]ها میسر نخواهد شد. مثلا تشکل­های موجود در شبکه وب، با مجموعه­های صفحات وب موجود بر روی موضوعات مرتبط متناظر بوده، تشخیص آن­ها منجر به یافتن صفحات مشابه و مربوط به هم می­ شود. این موضوع برای بسیاری از کاربرد­ها، مثلا موتورهای جستجو و سیستم­های پیشنهاددهنده[۴۰] متناسب است. همچنین، تشکل­های موجود در شبکه ­های اجتماعی با واحدهای اجتماعی[۴۱] تناظر دارند[۲۱]. از دیگر کاربردهای شناسایی تشکل، در شبکه ­های مبتنی بر متن[۴۲] مثل [۴۳]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 به صورت زیر تعریف می­ شود.

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...