SimRank
سم رینک ایک عام مماثلت کی پیمائش ہے، جو ایک سادہ اور بدیہی گراف تھیوریٹک ماڈل پر مبنی ہے۔ سم رینک کسی بھی ڈومین میں آبجیکٹ ٹو آبجیکٹ تعلقات کے ساتھ لاگو ہوتا ہے، جو ساختی سیاق و سباق کی مماثلت کی پیمائش کرتا ہے جس میں اشیاء واقع ہوتی ہیں، دوسری اشیاء کے ساتھ ان کے تعلقات کی بنیاد پر۔ مؤثر طور پر، سم رینک ایک پیمائش ہے جس میں کہا گیا ہے کہ "دو اشیاء کو ایک جیسا سمجھا جاتا ہے اگر ان کا حوالہ ایک جیسی اشیاء سے دیا جائے"۔ اگرچہ سم رینک کو بڑے پیمانے پر اپنایا جاتا ہے، لیکن یہ غیر معقول مماثلت کے اسکور پیدا کر سکتا ہے جو مختلف عوامل سے متاثر ہوتے ہیں، اور اسے کئی طریقوں سے حل کیا جا سکتا ہے، جیسے کہ ثبوت وزن کا عنصر متعارف کرانا، اضافی اصطلاحات داخل کرنا جنہیں سم رینک نے نظر انداز کیا ہے یا پیج رینک پر مبنی متبادلات کا استعمال کرنا۔ تعارف بہت سی ایپلی کیشنز کے لیے اشیاء کے درمیان "مماثلت" کی پیمائش کی ضرورت ہوتی ہے۔ ایک واضح مثال روایتی ٹیکسٹ کارپورا یا ورلڈ وائڈ ویب پر "فائنڈ-سمائرل-ڈاکیومنٹ" استفسار ہے۔ زیادہ عام طور پر، مماثلت کی پیمائش کو کلسٹر آبجیکٹ کے لیے استعمال کیا جا سکتا ہے، جیسے کہ ریکومینڈر سسٹم میں باہمی تعاون کے ساتھ فلٹر کرنے کے لیے، جس میں "مماثل" صارفین اور آئٹمز کو صارفین کی ترجیحات کی بنیاد پر گروپ کیا جاتا ہے۔ مماثلت کا تعین کرنے کے لیے اشیاء کے مختلف پہلوؤں کا استعمال کیا جا سکتا ہے، عام طور پر ڈومین اور اس ڈومین کے لیے مماثلت کی مناسب تعریف پر منحصر ہے۔ دستاویز کارپس میں، مماثل متن استعمال کیا جا سکتا ہے، اور باہمی تعاون کے ساتھ فلٹر کرنے کے لیے، اسی طرح کے صارفین کی شناخت عام ترجیحات سے کی جا سکتی ہے۔ سم رینک ایک عمومی نقطہ نظر ہے جو دلچسپی کے بہت سے ڈومینز میں پائے جانے والے آبجیکٹ ٹو آبجیکٹ تعلقات کا استحصال کرتا ہے۔ ویب پر، مثال کے طور پر، دو صفحات متعلقہ ہیں اگر ان کے درمیان ہائپر لنک ہیں۔ اسی طرح کا نقطہ نظر سائنسی کاغذات اور ان کے حوالہ جات، یا کراس حوالہ کی معلومات کے ساتھ کسی بھی دوسرے دستاویز کارپس پر لاگو کیا جا سکتا ہے۔ سفارش کے نظام کے معاملے میں، کسی آئٹم کے لیے صارف کی ترجیح صارف اور آئٹم کے درمیان تعلق تشکیل دیتی ہے۔ اس طرح کے ڈومینز کو قدرتی طور پر گراف کے طور پر ماڈل کیا جاتا ہے، جس میں نوڈس اشیاء کی نمائندگی کرتے ہیں اور کنارے تعلقات کی نمائندگی کرتے ہیں۔ سم رینک الگورتھم کے پیچھے وجدان یہ ہے کہ، بہت سے ڈومینز میں، اسی طرح کی اشیاء کا حوالہ اسی طرح کی اشیاء کے ذریعے دیا جاتا ہے۔ مزید واضح طور پر، اشیاء اور ان کو مماثل سمجھا جاتا ہے اگر وہ اشیاء سے بالترتیب اشارہ کیے گئے ہوں، اور خود بھی مماثل ہوں۔ بنیادی معاملہ یہ ہے کہ اشیاء زیادہ سے زیادہ خود سے ملتی جلتی ہیں۔ یہ نوٹ کرنا ضروری ہے کہ سم رینک ایک عمومی الگورتھم ہے جو صرف ساختی سیاق و سباق کی مماثلت کا تعین کرتا ہے۔ سم رینک کا اطلاق کسی بھی ڈومین پر ہوتا ہے جہاں رشتوں پر مماثلت کے کم از کم کچھ تصور کی بنیاد رکھنے کے لیے اشیاء کے درمیان کافی متعلقہ تعلقات ہوتے ہیں۔ ظاہر ہے، ڈومین کے دیگر مخصوص پہلوؤں کی مماثلت بھی اہم ہے۔ ان کو مجموعی مماثلت کی پیمائش کے لیے رشتہ دار ساختی-سیاق و سباق کی مماثلت کے ساتھ جوڑا جا سکتا ہے اور کیا جانا چاہیے۔ مثال کے طور پر، ویب صفحات کے لیے سم رینک کو روایتی متن کی مماثلت کے ساتھ جوڑا جا سکتا ہے ؛ یہی خیال سائنسی کاغذات یا دیگر دستاویز کارپورا پر لاگو ہوتا ہے۔ سفارش کے نظام کے لیے، اشیاء کے درمیان بلٹ ان معروف مماثلت ہو سکتی ہے (مثال کے طور پر، دونوں کمپیوٹر، دونوں کپڑے، وغیرہ)۔ )، نیز صارفین کے درمیان مماثلت (مثال کے طور پر، ایک ہی جنس، ایک ہی خرچ کی سطح)۔ ایک بار پھر، ان مماثلتوں کو مماثلت کے اسکور کے ساتھ جوڑا جا سکتا ہے جو ترجیحی نمونوں کی بنیاد پر شمار کیے جاتے ہیں، تاکہ مجموعی طور پر مماثلت کی پیمائش پیدا کی جا سکے۔ بنیادی سم رینک مساوات ایک ہدایت شدہ گراف میں نوڈ کے لیے، ہم بالترتیب ان پڑوسیوں اور آؤٹ پڑوسیوں کے سیٹ کی طرف اشارہ کرتے ہیں۔ انفرادی پڑوسیوں کو، کے لیے، اور انفرادی بیرونی پڑوسیوں کو، کے طور پر ظاہر کیا جاتا ہے۔ آئیے اشیاء اور کے درمیان مماثلت کی نشاندہی کرتے ہیں۔ پہلے کے محرک کے بعد، ایک تکراری مساوات کے لیے لکھا جاتا ہے۔ اگر تب اس کی وضاحت کی جاتی ہے۔ ورنہ، اور کے درمیان مستقل کہاں ہے۔ یہاں ایک چھوٹی سی تکنیکی بات یہ ہے کہ یا تو کوئی پڑوسی ہو یا نہ ہو۔ چونکہ اس معاملے میں اور کے درمیان کسی مماثلت کا اندازہ لگانے کا کوئی طریقہ نہیں ہے، اس لیے مماثلت مقرر کی گئی ہے، لہذا مندرجہ بالا مساوات میں خلاصہ اس طرح بیان کیا گیا ہے کہ کب یا۔ سم رینک کی میٹرکس نمائندگی اور کے درمیان ایک صوابدیدی مستقل کو دیکھتے ہوئے، مماثلت میٹرکس ہونے دیں جس کی اندراج مماثلت کے اسکور کو ظاہر کرتی ہے، اور کالم کو معمول پر لانے والا ملحقہ میٹرکس ہو جس کی اندراج اگر سے کوئی کنارے ہو، اور بصورت دیگر 0 ہو۔ پھر، میٹرکس نوٹیشن میں، سم رینک کو اس طرح وضع کیا جا سکتا ہے کہ شناخت میٹرکس کہاں ہے۔ سم رینک کا حساب لگانا گراف کے لیے سم رینک مساوات کا حل ایک مقررہ نقطہ پر تکرار کے ذریعے حاصل کیا جا سکتا ہے۔ چلو نوڈس کی تعداد میں ہو. ہر تکرار کے لیے، ہم اندراجات رکھ سکتے ہیں، جہاں تکرار کے درمیان اسکور ملتا ہے۔ ہم لگاتار اس کی بنیاد پر حساب لگاتے ہیں۔ ہم اس جگہ سے شروع کرتے ہیں جہاں اصل سم رینک اسکور پر ہر ایک کم باؤنڈ ہے: اس سے حساب لگانے کے لیے، ہم حاصل کرنے کے لیے بنیادی سم رینک مساوات کا استعمال کرتے ہیں: کے لیے، اور کے لیے۔ یعنی، ہر تکرار پر، ہم بنیادی سم رینک مساوات کے مطابق پچھلے تکرار سے پڑوسیوں کے مماثلت اسکور کو استعمال کرنے کی مماثلت کو اپ ڈیٹ کرتے ہیں۔ جیسے جیسے اضافہ ہوتا ہے اقدار غیر کم ہوتی جا رہی ہیں۔ یہ اس میں دکھایا گیا تھا کہ اقدار بنیادی سم رینک مساوات، سم رینک اسکور، یعنی سب کے لیے، کو مطمئن کرنے والی حدود میں یکجا ہوتی ہیں۔ اصل سم رینک تجویز نے کارکردگی کا مظاہرہ کرنے کے لیے ڈیک فیکٹر اور ایک مقررہ تعداد میں تکرار کا انتخاب کرنے کی تجویز پیش کی۔ تاہم، حالیہ تحقیق سے پتہ چلتا ہے کہ دی گئی اقدار اور عام طور پر بار بار حساب شدہ سم رینک اسکور کی نسبتا کم درستگی کا اشارہ کرتی ہیں۔ زیادہ درست کمپیوٹیشن کے نتائج کی ضمانت کے لیے، مؤخر الذکر کا مقالہ یا تو چھوٹے ڈیک فیکٹر (خاص طور پر) کا استعمال کرنے یا مزید تکرار کرنے کا مشورہ دیتا ہے۔ CoSimRank CoSimRank سم رینک کی ایک قسم ہے جس میں مقامی فارمولیشن ہونے کا فائدہ بھی ہے، یعنی۔ ایک واحد نوڈ جوڑی کے لیے کوسم رینک کا حساب لگایا جا سکتا ہے۔ مماثلت میٹرکس ہونے دیں جس کا اندراج مماثلت کے اسکور کی نشاندہی کرتا ہے، اور کالم نارملائزڈ ملحقہ میٹرکس ہے۔ پھر، میٹرکس نوٹیشن میں، CoSimRank کو اس طرح وضع کیا جا سکتا ہے: جہاں ایک شناختی میٹرکس ہے۔ صرف ایک نوڈ جوڑے کے مماثلت اسکور کا حساب لگانے کے لیے، معیاری بنیاد کا ویکٹر ہونے کے ساتھ، یعنی-th اندراج 1 ہے اور دیگر تمام اندراجات 0 ہیں۔ پھر، کوسم رینک کا حساب دو مراحل میں لگایا جا سکتا ہے: پہلا مرحلہ پرسنلائزڈ پیج رینک کا ایک آسان ورژن دیکھا جا سکتا ہے۔ دوسرا مرحلہ ہر تکرار کی ویکٹر مماثلت کا خلاصہ کرتا ہے۔ میٹرکس اور مقامی نمائندگی دونوں ایک ہی مماثلت اسکور کا حساب لگاتے ہیں۔ کوسم رینک کو ترمیم کرکے نوڈس کے سیٹوں کی مماثلت کا حساب لگانے کے لیے بھی استعمال کیا جا سکتا ہے۔ سم رینک فوگراس اور ریکس پر مزید تحقیق نے مونٹی کارلو طریقہ کار کا استعمال کرتے ہوئے ممکنہ حساب کے ذریعے سم رینک کے حساب کو تیز کرنے کا مشورہ دیا۔ انتونیلس اور دیگر۔ توسیع شدہ سم رینک مساوات (i) واقع نوڈس کے لیے ثبوت عنصر اور (ii) لنک وزن پر غور کرنے کے لیے۔ یو اور دیگر۔ مختلف جزوی رقوم کے درمیان چھوٹے مشترکہ حصوں کو بانٹنے کے لیے باریک دانے والے یادداشت کے طریقہ کار کے ذریعے سم رینک کے حساب کو مزید بہتر بنایا۔ چن اور جائلز نے سم رینک کی حدود اور مناسب استعمال کے معاملات پر تبادلہ خیال کیا۔ جزوی خلاصہ یادداشت لیزورکن اور دیگر۔ سم رینک کے حساب کو تیز کرنے کے لیے تین اصلاح کی تکنیکیں تجویز کی گئیں: ضروری نوڈس کا انتخاب ایک ترجیحی صفر اسکور کے ساتھ نوڈ جوڑوں کے ایک حصے کے حساب کو ختم کر سکتا ہے۔ جزوی رقم کی یادداشت بعد میں دوبارہ استعمال کے لیے مماثلت کے مجموعوں کے حصے کو کیشنگ کرکے مختلف نوڈ جوڑوں کے درمیان مماثلت کے بار بار ہونے والے حسابات کو مؤثر طریقے سے کم کر سکتی ہے۔ مماثلت پر ایک حد کی ترتیب گنتی کے لیے نوڈ جوڑوں کی تعداد میں مزید کمی کے قابل بناتی ہے۔ خاص طور پر، جزوی رقم کی یادداشت کا دوسرا مشاہدہ سم رینک کے حساب کو بہت تیز کرنے میں ایک اہم کردار ادا کرتا ہے، جہاں تکرار کی تعداد ہے، گراف کی اوسط ڈگری ہے، اور گراف میں نوڈس کی تعداد ہے۔ جزوی رقوم کی یادداشت کا مرکزی خیال دو مراحل پر مشتمل ہوتا ہے: پہلے، جزوی رقوم کو یاد کیا جاتا ہے اور پھر بار بار اس سے شمار کیا جاتا ہے۔ اس کے نتیجے میں، کے نتائج کو بعد میں دوبارہ استعمال کیا جا سکتا ہے جب ہم کسی دیئے گئے ورٹیکس کے لیے مماثلتوں کو پہلی دلیل کے طور پر شمار کرتے ہیں۔ یہ بھی دیکھیں پیج رینک حوالہ جات ذرائع کلسٹر تجزیہ الگورتھم مماثلت کے اقدامات