بخشی از مقاله
چکیده
به هر ساختار اجتماعی از افراد که بر اساس یک رابطه اجتماعی ایجاد میشود، یک شبکه اجتماعی گفته میشود. هر شبکه اجتماعی شامل مجموعهای از انسانها و روابط اجتماعی بین آنها است. مشکلات خوشهبندی گراف در رابطه با تعادل ساختاری با عنوان خوشهبندی همبستگی - cc - و خوشهبندی همبستگی متعادل شده - - Rcc در نظر گرفته شده است. مهمترین چالش حل این مشکلات به صورت بهینه بهعنوان ابزار سنجش تعادل ساختاری در شبکههای اجتماعی است. در این مقاله اولین فرمولبندی ریاضی برای مساله RCC بیان شده است. آزمایشهای عددی به همراه فرمولبندی، به روی مجموعهای از نمونههای موجود در مقاله انجام شده است.
.1 مقدمه
شبکههای اجتماعی گروهی از افراد یا سازمانهای دارای سلیقه یا منافع مشترک هستند که برای دستیابی به اهداف خاصی گرد هم میآیند. با گسترش شبکههای اجتماعی و روی آوردن کاربران در نقاط مختلف دنیا به آنها، مطالعه و تحلیل عملکرد افراد در این شبکهها نیز گسترش یافته است.
گرافهای جهتدار مورد توجه محققین شبکههای اجتماعی بوده است، گرافهای علامتدار با هدف شرح دادن روابط احساسی بین مردم، با توجه به گروههای اجتماعی که در آن هستند، و تهیه کردن یک بیان سیستماتیک تئوری تعادل اجتماعی، معرفی شد. یک گراف علامتدار، میتواند به دو زیر گروه متضادٌ و دو سره تقسیم شود[2]، که هر کدام تعهدات و وظایف خود را دارد. یک چالش در این زمینه، ارزیابی تعادل در شبکههای اجتماعی است، درجه تعادل در یک گروه اجتماعی میتواند بهعنوان یک ابزار برای مطالعه اینکه آیا این گروه میتواند به حالت تعادل رشد و نمو پیدا کند واینکه چطور این اتفاق میافتد، استفاده شود.معیارهای متفاوتی به این منظور میتواند مورد استفاده قرارگیرد.
راه حل بهینه برای مشکلات خوشهبندی که در گرافهای علامتدار تعریف شده است، قبلا به عنوان یک معیار برای اندازهگیری درجه تعادل در شبکههای اجتماعی استفاده شده است مهمترین چالش در این مقاله پیدا کردن راه حلی است برای افراز مجموعهای از رأسها که تعداد یالهای منفی در خوشهها به اضافه تعداد یالهای مثبت در بین خوشهها را مینیمم ٍکند.
برای حل این مشکل باید نزدیکترین افراز راس به حالت تعادل را پیدا کرده و بهعنوان یک واحد اندازهگیری عدم تعادل در گراف علامتدار شبکهاجتماعی معرفی کرد. اطلاعات بهدست آمده در آزمایشهای محاسباتی برای مشخص کردن تئوریها و نظریههای الحاقی در مورد تعادل ساختاری در شبکههای اجتماعی مورد استفاده قرار گرفت. با توجه به نظر نویسندگان امکان رشد و نمو شبکهها به حالتی که در آن عناصر دو گروه با هم همکاری کنند و یا عناصر یک گروه با یکدیگر مخالف باشند، وجود دارد.
این مقاله برروی مطالعه فرمولبندی برنامهریزی خطی اعداد صحیحَ - ILP - ، برای مشکلات خوشهبندی مربوط به تعادل ساختاری تمرکز میکند. این مساله در سه قسمت مورد بررسی قرار گرفته است. ابتدا مشکلات خوشهبندی در گرافهای سودار علامتدار را فرمولبندی کرده، سپس مجموعهای از مشکلات خوشهبندی را که در گرافهای سودار علامتدار تعریف شدهاند که میتوانند در ارزیابی تعادل ساختاری در شبکههای اجتماعی مورد استفاده قرار گیرندرا با یک علامتگذاری خاص استفاده کرده و سپس ارائه آزمایشات محاسباتی وهمچنین فرمولبندی برنامهریزی خطی اعداد صحیح ونتایج عددی را ارائه میدهیم.
.2 روشهای پیشین
خوشهبندی اطلاعات و منابع اطلاعاتی یکی از راهکارهای مؤثر در سازماندهی اطلاعات بهشمار میآید. با انجام فرایندهای خوشهبندی اطلاعات، حیطه گستردهای از دادههای پراکنده در گروههای مدون و سازمانیافته قرار میگیرند. گروههای متعدد ایجاد شده، که با برخورداری از ویژگیهای مشترک درون هر گروه، دارای ارتباط ارگانیک و ساختاری با یکدیگر هستند
فرایند گروهبندی مجموعهای از داده ها و قرار دادن آنها در طبقاتی از نمونههای مشابه خوشهبندی نام دارد. یک خوشه مجموعهای از دادههاست که نسبت به دیگر دادههای همان خوشه شبیه بوده ولی متفاوت از نمونههای دیگر خوشهها هستند. خوشهبندی به عمل تقسیم جمعیت ناهمگن به تعدادی از زیر مجموعهها یا خوشههای همگن گفته میشود.
خوشهبندی عبارت است از مرتب کردن واژهها یا مدار شبیه به هم در یک رده با عنوان کلی از لحاظ کاربردی، خوشهبندی سبب بهینهسازی فعالیت جستجو یا اطلاعات شده و زمان جستجوی کاربر را کاهش میدهد. هدف خوشهبندی یافتن خوشههای مشابه از اشیا در بین نمونههای ورودی میباشد اما چگونه میتوان گفت که یک خوشهبندی مناسب است و خوشهبندی دیگر مناسب نیست؟
در واقع هیچ معیار مطلقی برای بهترین خوشهبندی وجود ندارد بلکه این بستگی به مسئله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونهها بهدرستی خوشهبندیشدهاند یا خیر، بااینحال معیارهای مختلفی برای خوب بودن یک خوشهبندی ارائهشده است که میتوانند کاربر را برای رسیدن به یک خوشهبندی مناسب راهنمایی کند که در قسمتهای بعد چند نمونه از این معیارها آورده شده است. یکی از مسائل مهم در خوشهبندی انتخاب تعداد خوشهها میباشد.
در بعضی از الگوریتمها تعداد خوشهها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم میگیرد که دادهها به چند خوشه تقسیم شوند. خوشهبندی برای انواع الگوهای تحلیل اکتشافیٌ، گروهبندیٍ، تصمیمگیری، و موقعیتهای فراگیری ماشینی ، شامل: دادهکاویَ، بخشبندی تصویرُ و طرح ردهبندی سودمند است. خوشهبندی یک فعالیت توصیفی است که شناسایی و گروهبندی طبیعی دادهها را مورد کاوش قرار میدهد.
.3روش پیشنهادی
یک گراف جهتدار میباشد و مجموعهای از رئوس و مجموعهای از یالها است که هر دو رأس را به هم متصل میکند. در این مقاله فرض بر این است که گراف جهتدار هیچ حلقهای ندارد. یک افراز از مجموعه یعنی تقسیم آن مجموعه به زیر مجموعههای غیر تهی و مجزا. افراز به زیر مجموعه در این جا افراز نامیده میشود. به تابع که به هر یال در مجموعه یک علامت میدهد توجه کنید. گراف جهتدار به اضافه تابع گراف جهتدار علامتدار نامیده میشود.
مشخص کننده یک گراف جهتدار علامتدار است. یک یال منفی نامیده میشود اگر و مثبت نامیده میشود اگر . به ترتیب مشخص کننده مجموعه یالهای منفی و مجموعه یالهای مثبت در یک گراف جهتدار علامتدار میباشد.
