Clustering coefficient
گراف تھیوری میں، کلسٹرنگ گتانک اس ڈگری کی پیمائش ہے جس تک گراف میں نوڈس ایک ساتھ جمع ہوتے ہیں۔ شواہد سے پتہ چلتا ہے کہ زیادہ تر حقیقی دنیا کے نیٹ ورکس، اور خاص طور پر سوشل نیٹ ورکس میں، نوڈس مضبوطی سے بنے ہوئے گروپ بناتے ہیں جن کی خصوصیت تعلقات کی نسبتا زیادہ کثافت ہوتی ہے۔ یہ امکان دو نوڈس کے درمیان تصادفی طور پر قائم ہونے والے ٹائی کے اوسط امکان سے زیادہ ہوتا ہے (ہالینڈ اور لینہارٹ، 1971 ؛ واٹز اور اسٹروگاٹز، 1998)۔ اس پیمائش کے دو ورژن موجود ہیں: عالمی اور مقامی۔ عالمی ورژن نیٹ ورک میں کلسٹرنگ کا مجموعی اشارہ دینے کے لیے ڈیزائن کیا گیا تھا، جبکہ مقامی سنگل نوڈس کی سرایت کا اشارہ دیتا ہے۔ مقامی کلسٹرنگ گتانک گراف میں کسی ورٹیکس (نوڈ) کا مقامی کلسٹرنگ گتانک اس بات کی مقدار طے کرتا ہے کہ اس کے پڑوسی کلک (مکمل گراف) ہونے کے کتنے قریب ہیں۔ ڈنکن جے واٹز اور سٹیون سٹروگاٹز نے 1998 میں یہ پیمائش متعارف کرائی تاکہ اس بات کا تعین کیا جا سکے کہ آیا گراف ایک چھوٹی دنیا کا نیٹ ورک ہے۔ ایک گراف باضابطہ طور پر عمودی حصوں کے ایک سیٹ اور ان کے درمیان کناروں کے ایک سیٹ پر مشتمل ہوتا ہے۔ ایک کنارے ورٹیکس کو ورٹیکس سے جوڑتا ہے۔ کسی ورٹیکس کے پڑوس کی تعریف اس کے فوری طور پر جڑے ہوئے پڑوسیوں کے طور پر کی گئی ہے: ہم ورٹیکس کے پڑوس میں، عمودی کی تعداد کے طور پر بیان کرتے ہیں۔ اس کے بعد کسی ورٹیکس کے لیے مقامی کلسٹرنگ گتانک اس کے پڑوس کے اندر عمودی حصوں کے درمیان روابط کی تعداد کے تناسب سے دیا جاتا ہے جسے ممکنہ طور پر ان کے درمیان موجود روابط کی تعداد سے تقسیم کیا جاتا ہے۔ ایک ہدایت شدہ گراف کے لیے، اس سے الگ ہے، اور اس لیے ہر پڑوس کے لیے ایسے روابط ہیں جو پڑوس کے اندر عمودی حصوں کے درمیان موجود ہو سکتے ہیں (ایک عمودی کے پڑوسیوں کی تعداد ہے)۔ اس طرح، ہدایت شدہ گرافوں کے لیے مقامی کلسٹرنگ گتانک اس طرح دیا جاتا ہے کہ ایک غیر ہدایت شدہ گراف میں وہ خاصیت ہوتی ہے جو یکساں سمجھی جاتی ہے۔ لہذا، اگر کسی سرے کے پڑوسی ہیں، تو پڑوس کے اندر سرے کے درمیان کنارے موجود ہو سکتے ہیں۔ اس طرح، غیر ہدایت شدہ گرافوں کے لیے مقامی کلسٹرنگ گتانک کی تعریف اس طرح کی جا سکتی ہے کہ غیر ہدایت شدہ گراف کے لیے مثلثوں کی تعداد ہو۔ یعنی 3 کناروں اور 3 عمودی کے ذیلی گرافوں کی تعداد ہے، جن میں سے ایک ہے۔ آئیے تین گنا کی تعداد پر ہوں۔ یعنی، 2 کناروں اور 3 عمودی کے ساتھ ذیلی گرافوں کی تعداد (ضروری نہیں کہ انڈیوس کی گئی ہو) ہے، جن میں سے ایک ہے اور ایسا ہے جو دونوں کناروں پر واقع ہے۔ پھر ہم کلسٹرنگ گتانک کی وضاحت بھی کر سکتے ہیں کیونکہ یہ ظاہر کرنا آسان ہے کہ پچھلی دو تعریفیں ایک جیسی ہیں، کیونکہ یہ اقدامات 1 ہیں اگر ہر پڑوسی سے جڑا ہوا پڑوس کے اندر ہر دوسرے سرے سے بھی جڑا ہوا ہے، اور 0 اگر کوئی سرے سے جڑا ہوا نہیں ہے جو کسی دوسرے سرے سے جڑا ہوا ہے۔ چونکہ کوئی بھی گراف مکمل طور پر اس کے ملحقہ میٹرکس A کے ذریعہ متعین کیا جاتا ہے، اس لیے ایک سادہ غیر ہدایت شدہ گراف کے لیے مقامی کلسٹرنگ گتانک کو A کے لحاظ سے اس طرح ظاہر کیا جا سکتا ہے: جہاں: اور Ci = 0 جب کی صفر یا ایک ہو۔ مندرجہ بالا اظہار میں، عدد مکمل مثلثوں کی تعداد سے دوگنا شمار کرتا ہے جس میں ورٹیکس i شامل ہے۔ ڈینومینیٹر میں، کی 2 کنارے کے جوڑوں کی تعداد کو شمار کرتا ہے جس میں ورٹیکس i شامل ہے اور ساتھ ہی ایک کنارے کی تعداد کو دو بار عبور کیا گیا ہے۔ کی ورٹیکس i سے منسلک کناروں کی تعداد ہے، اور کی کو گھٹانے کے بعد مؤخر الذکر کو ہٹا دیتا ہے، جس سے صرف کنارے کے جوڑوں کا ایک مجموعہ باقی رہ جاتا ہے جو ممکنہ طور پر مثلث میں جڑے ہو سکتے ہیں۔ اس طرح کے ہر کنارے کے جوڑے کے لیے، ایک اور کنارے کا جوڑا ہوگا جو ایک ہی مثلث تشکیل دے سکتا ہے، لہذا ڈینومینیٹر قابل فہم مثلث کی تعداد سے دوگنا شمار کرتا ہے جس میں ورٹیکس i شامل ہو سکتا ہے۔ گلوبل کلسٹرنگ گتانک گلوبل کلسٹرنگ گتانک نوڈس کے تین گنا پر مبنی ہے۔ ٹرپلٹ تین نوڈس ہوتے ہیں جو یا تو دو (اوپن ٹرپلٹ) یا تین (کلوزڈ ٹرپلٹ) غیر سمت بندیوں سے جڑے ہوتے ہیں۔ اس لیے ایک مثلث گراف میں تین بند ٹرپلٹس شامل ہوتے ہیں، جن میں سے ایک نوڈس پر مرکوز ہوتا ہے (n. b. اس کا مطلب یہ ہے کہ مثلث میں تین سہ رخی نوڈس کے اوور لیپنگ انتخاب سے آتے ہیں)۔ گلوبل کلسٹرنگ گتانک ٹرپلٹس کی کل تعداد (کھلی اور بند دونوں) پر بند ٹرپلٹس (یا 3 x مثلث) کی تعداد ہے۔ اس کی پیمائش کرنے کی پہلی کوشش لوس اور پیری (1949) نے کی تھی۔ یہ پیمائش پورے نیٹ ورک (عالمی) میں کلسٹرنگ کا اشارہ دیتی ہے، اور اس کا اطلاق غیر ہدایت شدہ اور ہدایت شدہ دونوں نیٹ ورکس پر کیا جا سکتا ہے (جسے اکثر منتقلی کہا جاتا ہے، دیکھیں واسرمین اور فوسٹ، 1994، صفحہ 243)۔ عالمی کلسٹرنگ گتانک کی تعریف اس طرح کی گئی ہے: بند سہ رخی کی تعداد کو ادب میں 3 × مثلث بھی کہا گیا ہے، لہذا: وزن والے نیٹ ورکس کو عمومی بنانے کی تجویز اوپسہل اور پنجارسا (2009) نے پیش کی تھی، اور اوپسہل (2009) نے دو موڈ والے نیٹ ورکس (بائنری اور وزن والے دونوں) کی نئی تعریف کی تھی۔ چونکہ کوئی بھی گراف مکمل طور پر اس کے ملحقہ میٹرکس A کے ذریعہ متعین کیا جاتا ہے، اس لیے غیر ہدایت شدہ گراف کے لیے عالمی کلسٹرنگ گتانک کو A کے لحاظ سے اس طرح ظاہر کیا جا سکتا ہے: جہاں: اور C = 0 جب ڈینومینیٹر صفر ہو۔ نیٹ ورک اوسط کلسٹرنگ گتانک عالمی کلسٹرنگ گتانک کے متبادل کے طور پر، نیٹ ورک میں کلسٹرنگ کی مجموعی سطح کو واٹز اور اسٹروگاٹز کے ذریعہ تمام عمودی حصوں کے مقامی کلسٹرنگ گتانک کی اوسط کے طور پر ماپا جاتا ہے: یہ بات قابل غور ہے کہ یہ میٹرک کم ڈگری نوڈس پر زیادہ وزن رکھتا ہے، جبکہ منتقلی کا تناسب اعلی ڈگری نوڈس پر زیادہ وزن رکھتا ہے۔ بارات اور دیگر نے وزن والے نیٹ ورکس کو عام کرنے کی تجویز پیش کی تھی۔ (2004)، اور لیٹاپی اور دیگر کے ذریعہ دو طرفہ گراف (جسے دو موڈ نیٹ ورک بھی کہا جاتا ہے) کی نئی تعریف۔ (2008) اور اوپسل (2009)۔ وزن والے اور ہدایت شدہ گرافوں کے لیے متبادل عامیاں فاجیولو (2007) اور کلیمنٹ اینڈ گراسی (2018) کے ذریعے فراہم کی گئی ہیں۔ یہ فارمولا، پہلے سے طے شدہ طور پر، الگ تھلگ عمودی گرافوں کے لیے متعین نہیں ہے۔ دیکھیں قیصر (2008) اور بارمپوٹس اور دیگر۔ سب سے بڑے ممکنہ اوسط کلسٹرنگ گتانک والے نیٹ ورکس میں ایک ماڈیولر ڈھانچہ پایا جاتا ہے، اور ساتھ ہی، ان کا مختلف نوڈس کے درمیان سب سے کم ممکنہ اوسط فاصلہ ہوتا ہے۔ کلسٹرڈ نیٹ ورکس کا پرکولیشن ڈگری ڈگری ارتباط کے بغیر بے ترتیب ٹری جیسے نیٹ ورک کے لیے، یہ دکھایا جا سکتا ہے کہ اس طرح کے نیٹ ورک میں ایک بہت بڑا جزو ہو سکتا ہے، اور پرکولیشن تھریشولڈ (ٹرانسمیشن کا امکان) اس کے ذریعے دیا جاتا ہے، جہاں اضافی ڈگری کی تقسیم کے مطابق جنریٹنگ فنکشن ہے۔ کم کلسٹرنگ والے نیٹ ورکس میں، اہم نقطہ اس طرح سکیل ہو جاتا ہے کہ: یہ اس بات کی نشاندہی کرتا ہے کہ دی گئی ڈگری کی تقسیم کے لیے، کلسٹرنگ ایک بڑی پرکولیشن حد کی طرف لے جاتی ہے، بنیادی طور پر اس وجہ سے کہ لنکس کی ایک مقررہ تعداد کے لیے، کلسٹرنگ ڈھانچہ نیٹ ورک کے مرکز کو عالمی رابطوں کو کمزور کرنے کی قیمت کے ساتھ مضبوط کرتا ہے۔ اعلی کلسٹرنگ والے نیٹ ورکس کے لیے، مضبوط کلسٹرنگ کور پیریفیری ڈھانچے کو متحرک کر سکتی ہے، جس میں کور اور پیریفیری مختلف اہم نکات پر پھیل سکتے ہیں، اور مذکورہ بالا تخمینہ علاج لاگو نہیں ہوتا ہے۔ کلسٹرڈ نیٹ ورکس کی مضبوطی کا مطالعہ کرنے کے لیے ایک پرکولیشن نقطہ نظر تیار کیا جاتا ہے۔ ڈائریکٹڈ گراف تھیوری نیٹ ورک تھیوری نیٹ ورک سائنس پرکولیشن تھیوری اسکیل فری نیٹ ورک چھوٹے عالمی حوالہ جات بیرونی روابط گراف غیر متغیر الجبرائی گراف تھیوری نیٹ ورک تھیوری نیٹ ورک تجزیہ