مریم احسانی - استادیار، دانشگاه صنعتی اراک
رضا منصوری - دانشجوی کارشناسی، دانشگاه خوارزمی

گراف علامتدار در مدلسازی بسیاری از پدیدههای طبیعی، با لحاظ علامت مثبت یا منفی در ارتباطات عناصر یک سیستم کاربرد مییابد. مفهوم تعادل ساختاری در گراف علامتدار، متناظر با امکان افراز گراف به دو بخش است چنانکه پیوندهای درون دو بخش مثبت و پیوندهای بین دو بخش منفی باشد. در شبکههای علامتدار واقعی تعادل ساختاری معمولا کامل نیست. در عین حال، در این شبکه ها افراز شبکه به دو بخش چنانکه علامت پیوندهای درون هریک از دو بخش تا حد امکان مثبت و علامت پیوندهای بین دو بخش تا حد امکان منفی باشد، یک مسئله مهم است که کاربردهای بسیاری در تحلیل ساختار و عملکرد سیستم و زیربخشهای آن دارد. این مسئله که از آن با نام افراز متعادل یاد میکنیم، به عنوان یک مسئله بهینه سازی با توابع هدف گوناگون فرمولبندی شده است و در هرحال یک مسئله NP-Hard است. از اینرو رویکردهای گوناگونی بر مبنای روشهای ابتکاری، تقریبی یا فرا ابتکاری برای آن ارائه شده است. این مقاله، رویکرد جدید و در عین حال سادهای ارائه میکند که در آن مجموعه یالهای منفی بین دو بخش بر مبنای ارزیابی شاخص بهبود وضعیت تعادل انتخاب میگردد. ارزیابی یالهای منفی و انتخاب آنها برای عضویت در مجموعه ی مزبور، به ترتیب نزولی اندازه ی بینابینی یال در گراف اصلی صورت میگیرد. ضمن محاسبات پیچیدگی الگوریتم مورد نظر، این الگوریتم روی نمونههایی از دادههای واقعی پیادهسازی شده است و نتایج حاصل، کارایی خوب آن را تایید میکند.

گراف علامت دار، تعادل ساختاری، افراز متعادل، اندازه ی بینابینی یال