پست ۵: مقایسهٔ همسایگی دو عنصر x و y در یک ساختار رابطهای
پس از تعریف همسایگی، پرسش مهمی مطرح میشود: آیا دو عنصر x و y رفتار رابطهای مشابهی دارند؟ یکی از راههای پاسخ، مقایسهٔ مجموعههای همسایگی آنها است.
اگر R رابطهای روی مجموعهٔ A باشد، همسایگی دو عنصر را به شکل زیر مینویسیم:
N(x) = { z ∈ A | x R z }
N(y) = { z ∈ A | y R z }
اگر:
N(x) = N(y)
باشد، میتوان گفت x و y از دید رابطهٔ مورد نظر الگوی ارتباطی یکسانی دارند.
البته برابری همسایگیها الزاماً به معنای برابر بودن خود عناصر نیست. ممکن است دو عنصر متفاوت باشند، اما هر دو دقیقاً با عناصر یکسانی ارتباط داشته باشند.
برای سنجش شباهت نسبی، اشتراک دو همسایگی را بررسی میکنیم:
N(x) ∩ N(y)
هرچه این اشتراک بزرگتر باشد، احتمالاً x و y در ساختار رابطهای شباهت بیشتری دارند.
برای مثال، فرض کنید:
N(x) = {a, b, c, d}
N(y) = {b, c, d, e}
آنگاه:
N(x) ∩ N(y) = {b, c, d}
پس سه همسایهٔ مشترک وجود دارد. همچنین اجتماع دو همسایگی برابر است با:
N(x) ∪ N(y) = {a, b, c, d, e}
یک شاخص معروف برای سنجش شباهت، نسبت ژاکار است:
J(x, y) = |N(x) ∩ N(y)| / |N(x) ∪ N(y)|
در مثال بالا داریم:
J(x, y) = 3 / 5
این مقدار نشان میدهد که بخش قابلتوجهی از همسایگیهای x و y مشترک است.
در تحلیل شبکهها، دو کاربر با دوستان مشترک فراوان ممکن است علایق نزدیک داشته باشند. در زیستشناسی، دو پروتئین با ارتباطهای مشابه میتوانند نقشهای عملکردی نزدیک داشته باشند. در نظریهٔ گراف نیز شباهت همسایگیها برای خوشهبندی رأسها مهم است.
جمعبندی: مقایسهٔ همسایگیها روشی برای تشخیص شباهت ساختاری میان عناصر است. اشتراک همسایگیها، اطلاعاتی فراتر از مقایسهٔ مستقیم خود عناصر فراهم میکند.
در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.