Centrality
گراف تھیوری اور نیٹ ورک تجزیہ میں، مرکزیت کے اشارے ان کے نیٹ ورک پوزیشن کے مطابق گراف کے اندر نوڈس کو نمبر یا درجہ بندی تفویض کرتے ہیں۔ ایپلی کیشنز میں سوشل نیٹ ورک میں سب سے زیادہ بااثر شخص (افراد) کی شناخت، انٹرنیٹ یا شہری نیٹ ورک میں کلیدی انفراسٹرکچر نوڈس، بیماری کے سپر اسپریڈرز، اور دماغی نیٹ ورک شامل ہیں۔ مرکزیت کے تصورات سب سے پہلے سوشل نیٹ ورک کے تجزیے میں تیار کیے گئے تھے، اور مرکزیت کی پیمائش کے لیے استعمال ہونے والی بہت سی اصطلاحات ان کی سماجی اصل کی عکاسی کرتی ہیں۔ سنٹرلٹی انڈیکس کی تعریف اور خصوصیت سینٹرلٹی انڈیکس اس سوال کے جوابات ہیں کہ "ایک اہم ورٹیکس کی کیا خصوصیت ہے؟" جواب گراف کے عمودی حصوں پر حقیقی قدر والے فنکشن کے لحاظ سے دیا جاتا ہے، جہاں پیدا ہونے والی اقدار سے ایک درجہ بندی فراہم کرنے کی توقع کی جاتی ہے جو سب سے اہم نوڈس کی شناخت کرتی ہے۔ لفظ "اہمیت" کے بہت سے معنی ہیں، جو مرکزیت کی بہت سی مختلف تعریفوں کی طرف لے جاتے ہیں۔ درجہ بندی کی دو اسکیمیں تجویز کی گئی ہیں۔ "اہمیت" کا تصور نیٹ ورک میں کسی قسم کے بہاؤ یا منتقلی کے سلسلے میں کیا جا سکتا ہے۔ یہ مرکزیتوں کو اس بہاؤ کی قسم کے مطابق درجہ بندی کرنے کی اجازت دیتا ہے جسے وہ اہم سمجھتے ہیں۔ "اہمیت" کو متبادل طور پر نیٹ ورک کی ہم آہنگی میں شمولیت کے طور پر تصور کیا جا سکتا ہے۔ یہ مرکزیتوں کو اس بنیاد پر درجہ بندی کرنے کی اجازت دیتا ہے کہ وہ ہم آہنگی کی پیمائش کیسے کرتے ہیں۔ یہ دونوں نقطہ نظر مرکزیت کو الگ الگ زمروں میں تقسیم کرتے ہیں۔ ایک اور نتیجہ یہ ہے کہ ایک مرکزیت جو ایک زمرے کے لیے موزوں ہے اکثر کسی دوسرے زمرے پر لاگو ہونے پر "اسے غلط سمجھ لے گی"۔ بہت سے، اگرچہ سبھی نہیں، مرکزی اقدامات مؤثر طریقے سے کسی دیئے گئے سرے سے گزرنے والے کسی قسم کے راستوں کی تعداد (جسے واک بھی کہا جاتا ہے) کو شمار کرتے ہیں۔ اقدامات اس بات میں مختلف ہوتے ہیں کہ متعلقہ واک کی وضاحت اور گنتی کیسے کی جاتی ہے۔ اس گروپ پر غور کو محدود کرنا درجہ بندی کی اجازت دیتا ہے جو ایک سپیکٹرم پر بہت سی مرکزیتوں کو رکھتا ہے جن کی لمبائی ایک (ڈگری مرکزیت) سے لے کر لامحدود چہل قدمی (آئجین ویکٹر مرکزیت) تک ہے۔ مرکزیت کے دیگر اقدامات، جیسے کہ بیچنیس سینٹرلٹی نہ صرف مجموعی طور پر جڑے رہنے پر توجہ مرکوز کرتی ہے بلکہ ان پوزیشنوں پر قبضہ کرتی ہے جو نیٹ ورک کے رابطے کے لیے اہم ہیں۔ نیٹ ورک کے بہاؤ کی خصوصیت ایک نیٹ ورک کو ان راستوں کی تفصیل سمجھا جا سکتا ہے جن کے ساتھ کچھ بہتا ہے۔ یہ بہاؤ کی قسم اور مرکزیت کے ذریعہ انکوڈ شدہ راستے کی قسم پر مبنی خصوصیت کی اجازت دیتا ہے۔ ایک بہاؤ منتقلی پر مبنی ہو سکتا ہے، جہاں ہر ناقابل تقسیم آئٹم ایک نوڈ سے دوسرے نوڈ میں جاتا ہے، جیسے پیکیج ڈیلیوری ڈیلیوری سائٹ سے کلائنٹ کے گھر تک جاتی ہے۔ دوسرا معاملہ سیریل ڈپلیکیشن ہے، جس میں کسی آئٹم کی نقل کی جاتی ہے تاکہ ماخذ اور ہدف دونوں کے پاس ہو۔ ایک مثال گپ شپ کے ذریعے معلومات کا پھیلاؤ ہے، جس میں معلومات کو نجی طریقے سے پھیلایا جاتا ہے اور عمل کے اختتام پر ماخذ اور ہدف دونوں نوڈس کو مطلع کیا جاتا ہے۔ آخری کیس متوازی ڈپلیکیشن ہے، جس میں آئٹم کو ایک ہی وقت میں کئی لنکس پر ڈپلیکیٹ کیا جاتا ہے، جیسے ریڈیو براڈکاسٹ جو ایک ہی وقت میں بہت سے سامعین کو ایک ہی معلومات فراہم کرتا ہے۔ اسی طرح، راستے کی قسم کو جیوڈیسکس (مختصر ترین راستے)، راستوں (کسی بھی سرے پر ایک سے زیادہ بار نہیں جانا جاتا ہے)، راستوں (عمودی حصوں کو متعدد بار دیکھا جا سکتا ہے، کسی کنارے کو ایک سے زیادہ بار نہیں عبور کیا جاتا ہے)، یا پیدل چلنے (عمودی حصوں اور کناروں کو متعدد بار دیکھا/عبور کیا جا سکتا ہے) تک محدود کیا جا سکتا ہے۔ چہل قدمی کے ڈھانچے کے لحاظ سے خصوصیت ایک متبادل درجہ بندی اس بات سے حاصل کی جا سکتی ہے کہ مرکزیت کی تعمیر کیسے کی جاتی ہے۔ یہ دوبارہ دو کلاسوں میں تقسیم ہوتا ہے۔ مرکزیتیں یا تو شعاعی یا درمیانی ہوتی ہیں۔ شعاعی مرکزیتوں میں وہ چہل قدمی شمار کی جاتی ہے جو دیئے گئے سرے سے شروع/ختم ہوتی ہے۔ ڈگری اور آئجین ویلیو سینٹرلٹیز ریڈیل سینٹرلٹیز کی مثالیں ہیں، جو لمبائی ایک یا لمبائی انفینیٹی کی واک کی تعداد کو شمار کرتی ہیں۔ میڈیئل سینٹرلٹیز وہ چہل قدمی شمار کرتی ہیں جو دیئے گئے سرے سے گزرتی ہیں۔ کینونکل مثال فری مین کی بیچونیس سنٹرلٹی ہے، جو دیئے گئے سرے سے گزرنے والے مختصر ترین راستوں کی تعداد ہے۔ اسی طرح، گنتی یا تو حجم یا چہل قدمی کی لمبائی پر قبضہ کر سکتی ہے۔ حجم دی گئی قسم کی چہل قدمی کی کل تعداد ہے۔ پچھلے پیراگراف کی تین مثالیں اس زمرے میں آتی ہیں۔ لمبائی گراف میں دی گئی چوٹی سے باقی چوٹیوں تک کے فاصلے کو پکڑتی ہے۔ قریبی مرکزیت، کسی دیئے گئے سرے سے دوسرے تمام سرے تک کا کل جیوڈیسیک فاصلہ، سب سے مشہور مثال ہے۔ نوٹ کریں کہ یہ درجہ بندی واک گنتی کی قسم سے آزاد ہے (یعنی۔ واک، ٹریل، پاتھ، جیوڈیسیک)۔ بورگٹی اور ایوریٹ تجویز کرتے ہیں کہ یہ ٹائپولوجی اس بارے میں بصیرت فراہم کرتی ہے کہ مرکزیت کے اقدامات کا بہترین موازنہ کیسے کیا جائے۔ اس 2 × 2 درجہ بندی میں ایک ہی خانے میں رکھی گئی مرکزیتیں معقول متبادل بنانے کے لیے کافی ملتی جلتی ہیں۔ کوئی معقول طور پر موازنہ کر سکتا ہے کہ دی گئی درخواست کے لیے کون سا بہتر ہے۔ تاہم، مختلف بکسوں کے اقدامات واضح طور پر الگ ہیں۔ رشتہ دار فٹنس کی کوئی بھی تشخیص صرف اس تناظر میں ہو سکتی ہے کہ یہ پہلے سے طے کیا جائے کہ کون سا زمرہ زیادہ قابل اطلاق ہے، جس سے موازنہ متنازعہ ہو جاتا ہے۔ شعاعی حجم کی مرکزیتیں سپیکٹرم پر موجود ہیں واک ڈھانچے کی خصوصیت سے پتہ چلتا ہے کہ وسیع استعمال میں تقریبا تمام مرکزیتیں شعاعی حجم کے اقدامات ہیں۔ یہ اس عقیدے کو ظاہر کرتے ہیں کہ کسی سرے کی مرکزیت ان سرے کی مرکزیت کا ایک فعل ہے جس سے وہ وابستہ ہے۔ مرکزیتیں خود کو اس بات پر ممتاز کرتی ہیں کہ ایسوسی ایشن کی تعریف کیسے کی جاتی ہے۔ بوناچ نے دکھایا کہ اگر ایسوسی ایشن کی تعریف چہل قدمی کے لحاظ سے کی جاتی ہے، تو مرکزی خاندان کی تعریف چہل قدمی کی لمبائی کی بنیاد پر کی جا سکتی ہے۔ ڈگری سنٹرلٹی ایک لمبائی کی واک کو شمار کرتی ہے، جبکہ آئجین ویلیو سینٹرلٹی لمبائی انفینیٹی کی واک کو شمار کرتی ہے۔ ایسوسی ایشن کی متبادل تعریفیں بھی معقول ہیں۔ الفا مرکزیت عمودی کو اثر و رسوخ کا بیرونی ذریعہ رکھنے کی اجازت دیتی ہے۔ ایسٹراڈا کی ذیلی گراف مرکزیت صرف بند راستوں (مثلث، مربع وغیرہ) کی گنتی کی تجویز کرتی ہے۔ اس طرح کے اقدامات کا مرکز یہ مشاہدہ ہے کہ گراف کے ملحقہ میٹرکس کی طاقتیں اس طاقت کے ذریعہ دی گئی لمبائی کی تعداد دیتی ہیں۔ اسی طرح، میٹرکس ایکسپونینشل کا بھی کسی دی گئی لمبائی کی چہل قدمی کی تعداد سے گہرا تعلق ہے۔ ملحقہ میٹرکس کی ابتدائی تبدیلی چہل قدمی کی قسم کی ایک مختلف تعریف کی اجازت دیتی ہے۔ کسی بھی نقطہ نظر کے تحت، کسی ورٹیکس کی مرکزیت کو ایک لامحدود رقم کے طور پر ظاہر کیا جا سکتا ہے، یا تو میٹرکس پاورز کے لیے یا میٹرکس ایکسپونینشیلز کے لیے، جہاں واک لمبائی ہے، تبدیل شدہ ملحقہ میٹرکس ہے، اور یہ ایک رعایتی پیرامیٹر ہے جو رقم کی ہم آہنگی کو یقینی بناتا ہے۔ بوناسچ کے اقدامات کا خاندان ملحقہ میٹرکس کو تبدیل نہیں کرتا ہے۔ الفا سنٹرلٹی ملحقہ میٹرکس کو اس کے ریزولوینٹ سے بدل دیتی ہے۔ سب گراف کی مرکزیت ملحقہ میٹرکس کو اس کے ٹریس سے بدل دیتی ہے۔ ایک چونکا دینے والا نتیجہ یہ ہے کہ ملحقہ میٹرکس کی ابتدائی تبدیلی سے قطع نظر، اس طرح کے تمام طریقوں میں مشترکہ محدود طرز عمل ہوتا ہے۔ جیسے جیسے صفر کے قریب آتے ہیں، اشاریہ جات ڈگری مرکزیت میں بدل جاتے ہیں۔ جیسے جیسے اس کی زیادہ سے زیادہ قیمت قریب آتی ہے، اشاریہ جات آئجن ویلیو سنٹرلٹی میں بدل جاتے ہیں۔ گیم تھیوریٹک سنٹرلٹی مذکورہ بالا زیادہ تر معیاری اقدامات کی مشترکہ خصوصیت یہ ہے کہ وہ صرف اس کردار پر توجہ مرکوز کرکے نوڈ کی اہمیت کا اندازہ لگاتے ہیں جو نوڈ خود ادا کرتا ہے۔ تاہم، بہت سے ایپلی کیشنز میں اس طرح کا نقطہ نظر مطابقت پذیری کی وجہ سے ناکافی ہے جو اس صورت میں ہو سکتا ہے جب نوڈس کے کام کو گروپوں میں سمجھا جائے۔ مثال کے طور پر، وبا کو روکنے کے مسئلے پر غور کریں۔ نیٹ ورک کی اوپر کی تصویر کو دیکھتے ہوئے، ہمیں کن نوڈس کو ٹیکہ لگانا چاہیے؟ پہلے بیان کردہ اقدامات کی بنیاد پر، ہم ان نوڈس کو پہچاننا چاہتے ہیں جو بیماری کے پھیلاؤ میں سب سے اہم ہیں۔ صرف مرکزیت پر مبنی نقطہ نظر، جو نوڈس کی انفرادی خصوصیات پر توجہ مرکوز کرتے ہیں، اچھا خیال نہیں ہو سکتا۔ سرخ مربع میں نوڈس، انفرادی طور پر بیماری کے پھیلاؤ کو نہیں روک سکتے، لیکن انہیں ایک گروپ کے طور پر دیکھتے ہوئے، ہم واضح طور پر دیکھتے ہیں کہ اگر یہ نوڈس میں شروع ہوا ہے تو وہ بیماری کو روک سکتے ہیں، اور۔ گیم تھیوریٹک سینٹرلٹیز گیم تھیوری کے ٹولز کا استعمال کرتے ہوئے بیان کردہ مسائل اور مواقع سے مشورہ کرنے کی کوشش کرتی ہیں۔ میں تجویز کردہ نقطہ نظر شیپلی ویلیو کا استعمال کرتا ہے۔ شیپلی ویلیو کے حساب کی وقت کی پیچیدگی کی سختی کی وجہ سے، اس ڈومین میں زیادہ تر کوششیں نئے الگورتھم اور طریقوں کو نافذ کرنے میں کارفرما ہیں جو نیٹ ورک کی ایک مخصوص ٹوپولوجی یا مسئلے کے ایک خاص کردار پر انحصار کرتے ہیں۔ اس طرح کا نقطہ نظر وقت کی پیچیدگی کو ایکسپونینشل سے کثیر الجہتی تک کم کرنے کا باعث بن سکتا ہے۔ اسی طرح، حل کا تصور اتھارٹی ڈسٹری بیوشن () کھلاڑیوں کے درمیان دو طرفہ براہ راست اثر و رسوخ کی پیمائش کے لیے شیپلی ویلیو کے بجائے شیپلی-شوبک پاور انڈیکس کا اطلاق کرتا ہے۔ تقسیم درحقیقت ایک قسم کی آئجین ویکٹر مرکزیت ہے۔ یہ ہو (2020) میں بگ ڈیٹا آبجیکٹ کو ترتیب دینے کے لیے استعمال ہوتا ہے، جیسے کہ امریکی کالجوں کی درجہ بندی۔ مرکزی اشاریہ جات کی دو اہم حدود ہیں، ایک واضح اور دوسری باریک۔ واضح حد یہ ہے کہ ایک مرکزیت جو ایک ایپلی کیشن کے لیے بہترین ہے اکثر مختلف ایپلی کیشن کے لیے ذیلی بہترین ہوتی ہے۔ درحقیقت، اگر ایسا نہ ہوتا تو ہمیں اتنی مختلف مرکزیتوں کی ضرورت نہ ہوتی۔ اس رجحان کی ایک مثال کریک ہارٹ پتنگ گراف کے ذریعے فراہم کی گئی ہے، جس کے لیے مرکزیت کے تین مختلف تصورات انتہائی مرکزی سرے کے تین مختلف انتخاب دیتے ہیں۔ زیادہ باریک حد عام طور پر مانا جانے والا غلط فہمی ہے کہ عمودی مرکزیت عمودی کی نسبتا اہمیت کی نشاندہی کرتی ہے۔ مرکزیت کے اشاریہ جات واضح طور پر ایک درجہ بندی پیدا کرنے کے لیے بنائے گئے ہیں جو سب سے اہم عمودی اشارے کی اجازت دیتا ہے۔ یہ وہ اچھی طرح سے کرتے ہیں، ابھی نوٹ کی گئی حد کے تحت۔ وہ عام طور پر نوڈس کے اثر و رسوخ کی پیمائش کے لیے ڈیزائن نہیں کیے گئے ہیں۔ حال ہی میں، نیٹ ورک کے طبیعیات دانوں نے اس مسئلے کو حل کرنے کے لیے نوڈ انفلوئنس میٹرکس تیار کرنا شروع کر دیا ہے۔ غلطی دو گنا ہے۔ سب سے پہلے، درجہ بندی صرف اہمیت کے لحاظ سے عمودی ترتیب دیتی ہے، یہ درجہ بندی کی مختلف سطحوں کے درمیان اہمیت کے فرق کی مقدار نہیں بتاتا ہے۔ اس کو فری مین سنٹرلائزیشن کو زیر بحث سنٹرلٹی پیمائش پر لاگو کرکے کم کیا جاسکتا ہے، جو ان کے سنٹرلائزیشن اسکور کے فرق کے لحاظ سے نوڈس کی اہمیت کے بارے میں کچھ بصیرت فراہم کرتا ہے۔ مزید برآں، فری مین سنٹرلائزیشن کسی کو اپنے سب سے زیادہ سنٹرلائزیشن اسکور کا موازنہ کرکے کئی نیٹ ورکس کا موازنہ کرنے کے قابل بناتی ہے۔ تاہم، یہ نقطہ نظر عملی طور پر شاذ و نادر ہی دیکھا جاتا ہے۔ دوم، وہ خصوصیات جو (صحیح طریقے سے) کسی دیئے گئے نیٹ ورک/ایپلی کیشن میں سب سے اہم عمودی حصوں کی شناخت کرتی ہیں، ضروری نہیں کہ باقی عمودی حصوں میں عام ہو جائیں۔ دوسرے نیٹ ورک نوڈس کی اکثریت کے لیے درجہ بندی بے معنی ہو سکتی ہے۔ یہ وضاحت کرتا ہے کہ کیوں، مثال کے طور پر، گوگل امیج سرچ کے صرف پہلے چند نتائج معقول ترتیب میں ظاہر ہوتے ہیں۔ پیجرانک ایک انتہائی غیر مستحکم پیمائش ہے، جو چھلانگ کے پیرامیٹر کی چھوٹی ایڈجسٹمنٹ کے بعد بار بار رینک الٹ کو ظاہر کرتی ہے۔ اگرچہ مرکزیت کے اشاریہ جات کو باقی نیٹ ورک تک عام کرنے میں ناکامی پہلے تو متضاد لگ سکتی ہے، لیکن یہ براہ راست مندرجہ بالا تعریفوں سے ملتی ہے۔ پیچیدہ نیٹ ورکس میں متنوع ٹوپولوجی ہوتی ہے۔ اس حد تک کہ زیادہ سے زیادہ پیمائش کا انحصار سب سے اہم عمودی حصوں کے نیٹ ورک کے ڈھانچے پر ہوتا ہے، ایک پیمائش جو اس طرح کے عمودی حصوں کے لیے زیادہ سے زیادہ موزوں ہوتی ہے، باقی نیٹ ورک کے لیے کم بہتر ہوتی ہے۔ ڈگری مرکزیت تاریخی طور پر سب سے پہلے اور تصوراتی طور پر سب سے آسان ڈگری مرکزیت ہے، جس کی تعریف کسی نوڈ پر واقع لنکس کی تعداد کے طور پر کی جاتی ہے (یعنی کسی نوڈ کے تعلقات کی تعداد)۔ ڈگری کی تشریح نیٹ ورک کے ذریعے جو کچھ بہہ رہا ہے اسے پکڑنے کے لیے نوڈ کے فوری خطرے کے لحاظ سے کی جا سکتی ہے (جیسے وائرس، یا کچھ معلومات)۔ ڈائریکٹڈ نیٹ ورک کے معاملے میں (جہاں تعلقات کی سمت ہوتی ہے)، ہم عام طور پر ڈگری سنٹرلٹی کے دو الگ الگ اقدامات کی وضاحت کرتے ہیں، یعنی انڈیگری اور آؤٹ ڈگری۔ اس کے مطابق، انضمام نوڈ کی طرف جانے والے تعلقات کی تعداد کی گنتی ہے اور آؤٹ ڈگری ان تعلقات کی تعداد ہے جو نوڈ دوسروں کو بھیجتا ہے۔ جب تعلقات کو کچھ مثبت پہلوؤں جیسے دوستی یا تعاون سے جوڑا جاتا ہے، تو انڈیگری کو اکثر مقبولیت کی ایک شکل کے طور پر سمجھا جاتا ہے، اور آؤٹ ڈگری کو گریگریئس کے طور پر سمجھا جاتا ہے۔ عمودی اور کناروں کے ساتھ دیئے گئے گراف کے لیے عمودی کی ڈگری مرکزیت کی تعریف اس طرح کی جاتی ہے کہ گراف میں موجود تمام نوڈس کے لیے ڈگری مرکزیت کا حساب لگانا گراف کی گھنے ملحقہ میٹرکس کی نمائندگی کرتا ہے، اور کناروں کے لیے ایک غیر معمولی میٹرکس کی نمائندگی کرتا ہے۔ نوڈ کی سطح پر مرکزیت کی تعریف کو پورے گراف تک بڑھایا جا سکتا ہے، اس صورت میں ہم گراف مرکزیت کی بات کر رہے ہیں۔ آئیے وہ نوڈ بنیں جس میں سب سے زیادہ ڈگری مرکزیت ہو۔ آئیے-نوڈ سے منسلک گراف جو مندرجہ ذیل مقدار کو زیادہ سے زیادہ کرتا ہے (سب سے زیادہ ڈگری مرکزیت کے ساتھ نوڈ ہونے کے ساتھ): اسی کے مطابق، گراف کی ڈگری مرکزیت مندرجہ ذیل ہے: کی قیمت زیادہ سے زیادہ ہوتی ہے جب گراف میں ایک مرکزی نوڈ ہوتا ہے جس سے دوسرے تمام نوڈز جڑے ہوتے ہیں (ایک اسٹار گراف)، اور اس معاملے میں تو، کسی بھی گراف کے لیے، ٹینڈینسی ٹو میک ہب (ٹی ایم ایچ) نامی ڈگری مرکزیت کے لیے ایک نئی وسیع عالمی پیمائش مندرجہ ذیل طور پر بیان کرتی ہے: جہاں ٹی ایم ایچ نیٹ ورک میں ڈگری مرکزیت کے ظہور سے بڑھتا ہے۔ قریبی مرکزیت منسلک گراف میں، نوڈ کی معمول کی قربت مرکزیت (یا قربت) گراف میں نوڈ اور دیگر تمام نوڈس کے درمیان مختصر ترین راستے کی اوسط لمبائی ہے۔ اس طرح ایک نوڈ جتنا زیادہ مرکزی ہوتا ہے، اتنا ہی یہ دوسرے تمام نوڈس کے قریب ہوتا ہے۔ قریب ہونے کی تعریف الیکس باویلس (1950) نے فارمیس کے باہمی کے طور پر کی تھی، یہی وہ جگہ ہے جہاں عمودی یو اور وی کے درمیان فاصلہ ہوتا ہے۔ تاہم، جب قربت کی مرکزیت کی بات کی جاتی ہے، تو لوگ عام طور پر اس کی معمول کی شکل کا حوالہ دیتے ہیں، جو پچھلے فارمولے سے ضرب دی جاتی ہے، جہاں گراف میں نوڈس کی تعداد ہے۔ یہ معمول مختلف سائز کے گراف کے نوڈس کے درمیان موازنہ کی اجازت دیتا ہے۔ بہت سے گرافوں کے لیے، قربت کے الٹا اور ڈگری کے لوگرتھم کے درمیان ایک مضبوط ارتباط ہے، جہاں ورٹیکس v کی ڈگری ہے جبکہ α اور β ہر نیٹ ورک کے لیے مستقل ہیں۔ غیر ہدایت شدہ گرافوں میں دوسرے تمام نوڈس سے یا ان تک فاصلہ رکھنا غیر متعلقہ ہے، جبکہ یہ ہدایت شدہ گرافوں میں بالکل مختلف نتائج پیدا کر سکتا ہے (جیسے۔ کسی ویب سائٹ میں باہر جانے والے لنک سے زیادہ قربت کا مرکز ہو سکتا ہے، لیکن آنے والے لنکس سے کم قربت کا مرکز ہو سکتا ہے)۔ ہم آہنگی کی مرکزیت (لازمی طور پر منسلک نہیں) گراف میں، ہم آہنگی کی مرکزیت قربت کی مرکزیت کی تعریف میں مجموعہ اور باہمی کارروائیوں کو الٹ دیتی ہے: جہاں اگر u سے v تک کوئی راستہ نہیں ہے۔ ہم آہنگی کی مرکزیت کو اس سے تقسیم کرکے معمول بنایا جا سکتا ہے، جہاں گراف میں نوڈس کی تعداد ہے۔ ہم آہنگی کی مرکزیت کی تجویز مارچیوری اور لاٹورا (2000) اور پھر آزادانہ طور پر ڈیکر (2005) نے "قابل قدر مرکزیت" کا نام استعمال کرتے ہوئے، اور روچاٹ (2009) نے پیش کی تھی۔ بیچینیسی سنٹرلٹی بیچینیسی گراف کے اندر ایک ورٹیکس کی مرکزی پیمائش ہے (ایج بیچینیسی بھی ہے، جس پر یہاں بحث نہیں کی گئی ہے)۔ بیچینیس سنٹرلٹی اس بات کی مقدار طے کرتی ہے کہ نوڈ دو دوسرے نوڈس کے درمیان مختصر ترین راستے پر پل کے طور پر کام کرتا ہے۔ اسے لنٹن فری مین کے ذریعہ سوشل نیٹ ورک میں دوسرے انسانوں کے درمیان بات چیت پر انسان کے کنٹرول کی مقدار کے طور پر متعارف کرایا گیا تھا۔ اس کے تصور میں، جن چوٹیوں کا تصادفی طور پر منتخب کردہ دو چوٹیوں کے درمیان تصادفی طور پر منتخب کردہ مختصر ترین راستے پر واقع ہونے کا زیادہ امکان ہوتا ہے، ان کے درمیان اعلی فرق ہوتا ہے۔ عمودی نقاط کے ساتھ گراف میں کسی عمودی نقاط کے درمیان کا حساب مندرجہ ذیل طریقے سے لگایا جاتا ہے: عمودی نقاط کے ہر جوڑے کے لیے، ان کے درمیان مختصر ترین راستوں کا حساب لگائیں۔ عمودی حصوں کے ہر جوڑے (s، t) کے لیے، مختصر ترین راستوں کے حصے کا تعین کریں جو زیر بحث عمودی حصے سے گزرتے ہیں (یہاں، عمودی v)۔ اس حصے کو عمودی حصوں کے تمام جوڑوں (s، t) پر جمع کریں۔ زیادہ کمپیکٹ طور پر بیچنے کو اس طرح پیش کیا جا سکتا ہے: جہاں نوڈ سے نوڈ تک مختصر ترین راستوں کی کل تعداد ہے اور ان راستوں کی تعداد ہے جو گزرتے ہیں۔ درمیان کو عمودی جوڑوں کی تعداد کے ذریعے تقسیم کرکے معمول بنایا جا سکتا ہے جس میں v شامل نہیں ہے، جو ہدایت شدہ گرافوں کے لیے ہے اور غیر ہدایت شدہ گرافوں کے لیے ہے۔ مثال کے طور پر، ایک غیر ہدایت شدہ ستارے کے گراف میں، مرکز کے سرے (جو ہر ممکنہ مختصر ترین راستے میں موجود ہے) کا بیچنا (1، اگر معمول پر لایا جائے) ہوگا جبکہ پتوں (جو مختصر ترین راستوں میں موجود نہیں ہیں) کا بیچنا 0 ہوگا۔ حساب کے پہلو سے، گراف میں تمام عمودی حصوں کے درمیان اور قربت دونوں کی مرکزی حیثیت میں گراف پر عمودی حصوں کے تمام جوڑوں کے درمیان مختصر ترین راستوں کا حساب لگانا شامل ہے، جس کے لیے فلائیڈ-وارشل الگورتھم کے ساتھ وقت درکار ہوتا ہے۔ تاہم، کم گرافوں پر، جانسن کا الگورتھم زیادہ موثر ہو سکتا ہے، جس میں وقت لگتا ہے۔ غیر وزن والے گراف کے معاملے میں حساب کتاب برانڈز کے الگورتھم کے ساتھ کیا جا سکتا ہے جس میں وقت لگتا ہے۔ عام طور پر، یہ الگورتھم یہ فرض کرتے ہیں کہ گراف غیر ہدایت شدہ ہیں اور لوپس اور متعدد کناروں کے الاؤنس سے جڑے ہوئے ہیں۔ نیٹ ورک گراف کے ساتھ خاص طور پر کام کرتے وقت، اکثر گراف سادہ تعلقات کو برقرار رکھنے کے لیے لوپس یا متعدد کناروں کے بغیر ہوتے ہیں (جہاں کنارے دو لوگوں یا عمودی کے درمیان رابطوں کی نمائندگی کرتے ہیں)۔ اس صورت میں، برانڈز کے الگورتھم کا استعمال حتمی مرکزیت کے اسکور کو 2 سے تقسیم کرے گا تاکہ ہر مختصر ترین راستے کو دو بار شمار کیا جا سکے۔ آئجین ویکٹر سنٹرلٹی (جسے آئجین سینٹرلٹی بھی کہا جاتا ہے) نیٹ ورک میں نوڈ کے اثر و رسوخ کی پیمائش ہے۔ یہ نیٹ ورک کے تمام نوڈس کو اس تصور کی بنیاد پر متعلقہ اسکور تفویض کرتا ہے کہ ہائی اسکورنگ نوڈس کے کنکشن کم اسکورنگ نوڈس کے مساوی کنکشن کے مقابلے میں نوڈ کے اسکور میں زیادہ حصہ ڈالتے ہیں۔ گوگل کا پیج رینک اور کاٹز مرکزیت آئجین ویکٹر مرکزیت کی مختلف قسمیں ہیں۔ آئجین ویکٹر کی مرکزیت کو تلاش کرنے کے لیے ملحقہ میٹرکس کا استعمال عمودی تعداد کے ساتھ دیے گئے گراف کے لیے ملحقہ میٹرکس، یعنی ملحقہ میٹرکس ہونا چاہیے۔ اگر ورٹیکس ورٹیکس سے منسلک ہے، اور بصورت دیگر۔ ورٹیکس کے رشتہ دار مرکزیت اسکور کی تعریف اس طرح کی جا سکتی ہے: جہاں پڑوسیوں کا ایک مجموعہ ہے اور ایک مستقل ہے۔ ایک چھوٹی سی ترتیب کے ساتھ اسے ویکٹر نوٹیشن میں آئجین ویکٹر مساوات کے طور پر دوبارہ لکھا جا سکتا ہے۔ عام طور پر، بہت سی مختلف آئجین ویلیوز ہوں گی جن کے لیے غیر صفر آئجین ویکٹر حل موجود ہے۔ چونکہ ملحقہ میٹرکس میں اندراجات غیر منفی ہیں، اس لیے پیرون-فروبینیوس تھیوریم کے مطابق ایک منفرد سب سے بڑی آئجن ویلیو ہے، جو حقیقی اور مثبت ہے۔ یہ سب سے بڑی آئجین ویلیو مطلوبہ مرکزیت کی پیمائش کا نتیجہ ہے۔ متعلقہ آئجین ویکٹر کا جزو پھر نیٹ ورک میں ورٹیکس کا متعلقہ مرکزی اسکور دیتا ہے۔ آئجین ویکٹر کی تعریف صرف ایک مشترکہ عنصر تک کی جاتی ہے، لہذا صرف عمودی مرکزیتوں کے تناسب کی اچھی طرح سے وضاحت کی جاتی ہے۔ مطلق اسکور کی وضاحت کے لیے کسی کو آئجن ویکٹر کو معمول بنانا چاہیے، مثال کے طور پر، کہ تمام عمودی حصوں کا مجموعہ 1 ہو یا عمودی حصوں کی کل تعداد n ہو۔ پاور تکرار بہت سے آئجن ویلیو الگورتھم میں سے ایک ہے جو اس غالب آئجن ویکٹر کو تلاش کرنے کے لیے استعمال کیا جا سکتا ہے۔ مزید برآں، اسے عام کیا جا سکتا ہے تاکہ A میں اندراجات حقیقی اعداد ہو سکتے ہیں جو کنکشن کی طاقت کی نمائندگی کرتے ہیں، جیسا کہ اسٹاکسٹک میٹرکس میں ہوتا ہے۔ کاٹز مرکزیت ڈگری مرکزیت کی عمومی شکل ہے۔ ڈگری مرکزیت براہ راست پڑوسیوں کی تعداد کی پیمائش کرتی ہے، اور کاٹز مرکزیت ان تمام نوڈس کی تعداد کی پیمائش کرتی ہے جنہیں راستے سے جوڑا جا سکتا ہے، جبکہ دور دراز نوڈس کی شراکت کو سزا دی جاتی ہے۔ ریاضیاتی طور پر، اس کی تعریف اس طرح کی گئی ہے کہ ایک تخفیف عنصر کہاں ہے۔ کاٹز مرکزیت کو آئجین ویکٹر مرکزیت کی ایک قسم کے طور پر دیکھا جا سکتا ہے۔ کاٹز مرکزیت کی ایک اور شکل آئجین ویکٹر مرکزیت کے اظہار سے موازنہ کی جاتی ہے، اس کی جگہ لے لی جاتی ہے۔ یہ دکھایا گیا ہے کہ پرنسپل آئجین ویکٹر (سب سے بڑی آئجین ویلیو، ملحقہ میٹرکس سے وابستہ) کاٹز مرکزیت کی حد ہے جیسا کہ نیچے سے آتا ہے۔ پیج رینک مرکزییت پیج رینک مندرجہ ذیل مساوات کو مطمئن کرتا ہے جہاں نوڈ کے پڑوسیوں کی تعداد (یا ہدایت شدہ گراف میں آؤٹ باؤنڈ لنکس کی تعداد) ہے۔ آئجین ویکٹر مرکزیت اور کاٹز مرکزیت کے مقابلے میں، ایک بڑا فرق اسکیلنگ فیکٹر ہے۔ پیج رینک اور آئجین ویکٹر کی مرکزیت کے درمیان ایک اور فرق یہ ہے کہ پیج رینک ویکٹر بائیں ہاتھ کا آئجین ویکٹر ہے (نوٹ کریں کہ عنصر کے اشارے الٹ گئے ہیں)۔ پرکولیشن سنٹرلٹی ایک پیچیدہ نیٹ ورک میں ایک نوڈ کی 'اہمیت' کا تعین کرنے کے لیے مرکزی اقدامات کی ایک بڑی تعداد موجود ہے۔ تاہم، یہ اقدامات خالص طور پر ٹپوولوجیکل اصطلاحات میں نوڈ کی اہمیت کی مقدار طے کرتے ہیں، اور نوڈ کی قیمت کسی بھی طرح سے نوڈ کی 'حالت' پر منحصر نہیں ہوتی ہے۔ یہ نیٹ ورک کی حرکیات سے قطع نظر مستقل رہتا ہے۔ یہ وزن کے درمیان کے اقدامات کے لیے بھی درست ہے۔ تاہم، ایک نوڈ بہت اچھی طرح سے بیچ میں مرکزیت یا کسی اور مرکزی پیمائش کے لحاظ سے مرکزی طور پر واقع ہو سکتا ہے، لیکن ہو سکتا ہے کہ 'مرکزی طور پر' کسی نیٹ ورک کے تناظر میں واقع نہ ہو جس میں پرکولیشن ہو۔ 'متعدی' کا پھیلنا پیچیدہ نیٹ ورکس میں کئی منظرناموں میں ہوتا ہے۔ مثال کے طور پر، وائرل یا بیکٹیریل انفیکشن لوگوں کے سوشل نیٹ ورکس پر پھیل سکتا ہے، جسے کانٹیکٹ نیٹ ورک کہا جاتا ہے۔ سڑک، ریل یا ہوائی رابطوں کے ذریعے جڑے قصبوں یا آبادی کے مراکز کے نیٹ ورک پر غور کرکے بیماری کے پھیلاؤ کو تجریدی کی اعلی سطح پر بھی سمجھا جا سکتا ہے۔ کمپیوٹر وائرس کمپیوٹر نیٹ ورک پر پھیل سکتے ہیں۔ کاروباری پیشکشوں اور سودوں کے بارے میں افواہیں یا خبریں لوگوں کے سوشل نیٹ ورکس کے ذریعے بھی پھیل سکتی ہیں۔ ان تمام منظرناموں میں، ایک 'متعدی' ایک پیچیدہ نیٹ ورک کے لنکس پر پھیلتا ہے، نوڈس کی 'حالتوں' کو تبدیل کرتا ہے جیسے جیسے یہ پھیلتا ہے، یا تو بازیافت یا دوسری صورت میں۔ مثال کے طور پر، وبائی امراض کے منظر نامے میں، انفیکشن پھیلتے ہی افراد 'حساس' سے 'متاثرہ' حالت میں چلے جاتے ہیں۔ مذکورہ بالا مثالوں میں انفرادی نوڈس جو ریاستیں لے سکتے ہیں وہ بائنری ہو سکتی ہیں (جیسے کہ موصول شدہ/موصول شدہ خبروں کا ایک ٹکڑا)، مجرد (حساس/متاثرہ/بازیافت شدہ)، یا یہاں تک کہ مسلسل (جیسے کسی قصبے میں متاثرہ لوگوں کا تناسب)، جیسے جیسے انفیکشن پھیلتا ہے۔ ان تمام منظرناموں میں مشترکہ خصوصیت یہ ہے کہ انفیکشن کے پھیلاؤ کے نتیجے میں نیٹ ورکس میں نوڈ کی حالتوں میں تبدیلی آتی ہے۔ پرکولیشن سنٹرلٹی (پی سی) کو ذہن میں رکھتے ہوئے تجویز کیا گیا تھا، جو خاص طور پر نیٹ ورک کے ذریعے پرکولیشن میں مدد کے لحاظ سے نوڈس کی اہمیت کی پیمائش کرتا ہے۔ یہ اقدام پیراوینن اور دیگر نے تجویز کیا تھا۔ پرکولیشن سنٹرلٹی کو کسی دیئے گئے نوڈ کے لیے، ایک مقررہ وقت پر، اس نوڈ سے گزرنے والے 'پرکولیٹڈ راستوں' کے تناسب کے طور پر بیان کیا جاتا ہے۔ ایک 'پرکولیٹڈ پاتھ' نوڈس کے جوڑے کے درمیان ایک مختصر ترین راستہ ہے، جہاں سورس نوڈ پرکولیٹڈ ہوتا ہے (مثال کے طور پر، متاثر)۔ ٹارگٹ نوڈ پرکولیٹڈ یا نان پرکولیٹڈ، یا جزوی طور پر پرکولیٹڈ حالت میں ہو سکتا ہے۔ جہاں نوڈ سے نوڈ تک مختصر ترین راستوں کی کل تعداد ہے اور ان راستوں کی تعداد ہے جو گزرتے ہیں۔ وقت پر نوڈ کی پرکولیشن حالت کو اس کے ذریعے ظاہر کیا جاتا ہے اور دو خاص معاملات ہوتے ہیں جب وہ وقت پر غیر پرکولیٹڈ حالت کی نشاندہی کرتے ہیں جبکہ جب وہ وقت پر مکمل طور پر پرکولیٹڈ حالت کی نشاندہی کرتا ہے۔ درمیان میں اقدار جزوی طور پر پھیلی ہوئی ریاستوں کی نشاندہی کرتی ہیں (مثال کے طور پر، ٹاؤن شپ کے نیٹ ورک میں، یہ اس قصبے میں متاثرہ افراد کا فیصد ہوگا)۔ پرکولیشن کے راستوں سے منسلک وزن کا انحصار سورس نوڈس کو تفویض کردہ پرکولیشن کی سطح پر ہوتا ہے، اس بنیاد پر کہ سورس نوڈ کی پرکولیشن کی سطح جتنی زیادہ ہوگی، اس نوڈ سے نکلنے والے راستے اتنے ہی اہم ہوں گے۔ نوڈس جو انتہائی پرکولیٹڈ نوڈس سے شروع ہونے والے مختصر ترین راستوں پر واقع ہوتے ہیں اس لیے ممکنہ طور پر پرکولیشن کے لیے زیادہ اہم ہوتے ہیں۔ پی سی کی تعریف کو ہدف نوڈ کے وزن کو بھی شامل کرنے کے لیے بڑھایا جا سکتا ہے۔ پرکولیشن سنٹرلٹی کے حسابات برانڈز کے تیز رفتار الگورتھم سے اپنائے گئے موثر نفاذ کے ساتھ وقت پر چلتے ہیں اور اگر حساب کتاب کو ٹارگٹ نوڈس کے وزن پر غور کرنے کی ضرورت ہے تو، بدترین صورت میں وقت ہوتا ہے۔ ایک پیچیدہ گراف میں ایک واحد نوڈ کی کراس کلک مرکزیت مختلف گروہوں سے نوڈ کے رابطے کا تعین کرتی ہے۔ اعلی کراس کلک کنیکٹوٹی والا نوڈ گراف میں معلومات یا بیماری کے پھیلاؤ کو آسان بناتا ہے۔ کلکس ذیلی گراف ہوتے ہیں جن میں ہر نوڈ کلکس کے ہر دوسرے نوڈ سے جڑا ہوتا ہے۔ عمودی اور کناروں کے ساتھ دیئے گئے گراف کے لیے نوڈ کی کراس کلک کنیکٹوٹی کی تعریف اس طرح کی جاتی ہے کہ کلکس کی تعداد کہاں ہے جس سے ورٹیکس کا تعلق ہے۔ یہ اقدام 2013 میں فغانی نے استعمال کیا تھا لیکن پہلی بار 1998 میں ایوریٹ اور بورگٹی نے اس کی تجویز پیش کی تھی جہاں انہوں نے اسے کلک اوورلیپ سنٹرلٹی کہا تھا۔ فری مین سنٹرلائزیشن کسی بھی نیٹ ورک کی سنٹرلائزیشن اس بات کی پیمائش ہے کہ اس کا سب سے مرکزی نوڈ اس سلسلے میں کتنا مرکزی ہے کہ دوسرے تمام نوڈس کتنے مرکزی ہیں۔ سنٹرلائزیشن کے اقدامات پھر (a) نیٹ ورک میں سب سے زیادہ مرکزی نوڈ اور دیگر تمام نوڈس کے درمیان مرکزیت میں فرق کے مجموعے کا حساب لگائیں ؛ اور (b) اس مقدار کو نظریاتی طور پر ایک ہی سائز کے کسی بھی نیٹ ورک میں اس طرح کے سب سے بڑے فرق کے مجموعے سے تقسیم کریں۔ اس طرح، ہر مرکزیت کے اقدام کا اپنا مرکزیت کا پیمانہ ہو سکتا ہے۔ رسمی طور پر متعین کیا گیا ہے، اگر نقطہ کی کوئی مرکزیت کی پیمائش ہے، اگر نیٹ ورک میں اس طرح کی سب سے بڑی پیمائش ہے، اور اگر: نوڈس کی ایک ہی تعداد والے کسی بھی گراف کے لیے نقطہ مرکزیت میں فرق کا سب سے بڑا مجموعہ ہے، تو نیٹ ورک کی مرکزیت یہ ہے: تصور لنٹن فری مین کی وجہ سے ہے۔ مماثلت پر مبنی مرکزیت کے اقدامات کسی دیئے گئے نیٹ ورک کے نوڈس کی درجہ بندی میں بہتر نتائج حاصل کرنے کے لیے، پیچیدہ نیٹ ورک میں مرکزیت کے اقدامات کو تقویت دینے کے لیے مماثلت کے اقدامات (درجہ بندی اور ڈیٹا مائننگ کے نظریہ کے لیے مخصوص) استعمال کیے جاتے ہیں۔ اس کی مثال آئجین ویکٹر سنٹرلٹی کے ساتھ دی گئی ہے، جس میں آئجین ویلیو کے مسئلے کے حل کے ذریعے ہر نوڈ کی مرکزیت کا حساب لگایا جاتا ہے جہاں (کوآرڈینیٹ ٹو کوآرڈینیٹ پروڈکٹ) اور یہ ایک صوابدیدی فرق میٹرکس ہے، جس کی تعریف ایک اختلاف کی پیمائش کے ذریعے کی گئی ہے، مثال کے طور پر، جیکارڈ کی عدم مساوات جہاں یہ پیمائش ہمیں ہر نوڈ کی ٹپوولوجیکل شراکت (جسے شراکت سینٹرلٹی کہا جاتا ہے) کو کسی دیئے گئے نوڈ کی مرکزیت میں شمار کرنے کی اجازت دیتی ہے، زیادہ وزن/مطابقت رکھتے ہوئے ان نوڈوں کو زیادہ فرق کے ساتھ، کیونکہ یہ دیئے گئے نوڈ تک رسائی کی اجازت دیتے ہیں جو خود براہ راست رسائی نہیں کر سکتے ہیں۔ قابل ذکر ہے کہ یہ غیر منفی ہے کیونکہ اور غیر منفی میٹرکس ہیں، لہذا ہم اس بات کو یقینی بنانے کے لیے پیرون-فروبینیوس تھیوریم کا استعمال کر سکتے ہیں کہ مندرجہ بالا مسئلے کا λ = λmax کے لیے c غیر منفی کے ساتھ ایک منفرد حل ہے، جس سے ہمیں نیٹ ورک میں ہر نوڈ کی مرکزیت کا اندازہ لگانے کی اجازت ملتی ہے۔ لہذا، i-th نوڈ کی مرکزیت یہ ہے کہ نیٹ ورک میں نوڈس کی تعداد کہاں ہے۔ مطالعہ شدہ معاملات میں بہتر نتائج حاصل کرنے کے لیے متعدد عدم مساوات کے اقدامات اور نیٹ ورکس کا تجربہ کیا گیا۔ الفا سنٹرلٹی کور-پیریفیری ڈھانچہ بھی دیکھیں گراف میں فاصلہ نوٹ اور حوالہ جات مزید پڑھنے کے لیے کوشوٹزکی، ڈی۔ ؛ لیمن، کے۔ اے۔ ؛ پیٹرز، ایل۔ ؛ ریکٹر، ایس۔ ؛ ٹینفیلڈ-پودل، ڈی۔ اور زلوٹوسکی، او۔ (2005) سینٹرلٹی انڈیکس۔ برانڈز میں، یو۔ اور ایرلیباخ، ٹی۔ (ایڈز۔) نیٹ ورک تجزیہ: طریقہ کار کی بنیادیں، پی پی۔ 16-61، LNCS 3418، سپرنگر-ورلاگ۔ گراف تھیوری گراف الگورتھم الجبرائی گراف تھیوری نیٹ ورک تجزیہ نیٹ ورک تھیوری گراف فاصلہ