Erdős–Rényi model
گراف تھیوری کے ریاضیاتی میدان میں، ایرڈس-رینی ماڈل سے مراد بے ترتیب گراف تیار کرنے یا بے ترتیب نیٹ ورک کے ارتقاء کے لیے دو قریب سے متعلق ماڈلز میں سے ایک ہے۔ ان ماڈلز کا نام ہنگری کے ریاضی دان پال ایرڈس اور الفریڈ رینی کے نام پر رکھا گیا ہے، جنہوں نے 1959 میں ایک ماڈل متعارف کرایا تھا۔ ایڈگر گلبرٹ نے دوسرے ماڈل کو معاصر طور پر ایردوس اور رینی کے ساتھ اور آزادانہ طور پر متعارف کرایا۔ ایرڈس اور رینی کے ماڈل میں، کناروں کی ایک مقررہ تعداد کے ساتھ ایک مقررہ ورٹیکس سیٹ پر موجود تمام گراف یکساں طور پر ممکنہ ہیں۔ گلبرٹ کے متعارف کردہ ماڈل میں، جسے ایرڈس-رینی-گلبرٹ ماڈل بھی کہا جاتا ہے، ہر کنارے کے دوسرے کناروں سے آزادانہ طور پر موجود یا غیر حاضر ہونے کا ایک مقررہ امکان ہوتا ہے۔ ان ماڈلز کو ممکنہ طریقہ کار میں استعمال کیا جا سکتا ہے تاکہ مختلف خصوصیات کو مطمئن کرنے والے گراف کے وجود کو ثابت کیا جا سکے، یا اس بات کی سخت تعریف فراہم کی جا سکے کہ کسی پراپرٹی کے لیے تقریبا تمام گرافوں کو برقرار رکھنے کا کیا مطلب ہے۔ تعریف ایرڈس-رینی بے ترتیب گراف ماڈل کی دو قریب سے متعلق قسمیں ہیں۔ ماڈل میں، ایک گراف کو تمام گرافوں کے مجموعے سے بے ترتیب طور پر یکساں طور پر منتخب کیا جاتا ہے جن میں نوڈس اور کنارے ہوتے ہیں۔ نوڈس کو لیبل شدہ سمجھا جاتا ہے، جس کا مطلب ہے کہ عمودی حصوں کو پرموٹ کرکے ایک دوسرے سے حاصل کردہ گراف کو الگ سمجھا جاتا ہے۔ مثال کے طور پر، ماڈل میں، تین لیبل والے عمودی حصوں پر تین دو کنارے والے گراف ہوتے ہیں (دو کنارے والے راستے میں درمیانی عمودی کے ہر انتخاب کے لیے ایک)، اور ان تینوں گرافوں میں سے ہر ایک کو امکان کے ساتھ شامل کیا جاتا ہے۔ ماڈل میں، لیبل شدہ نوڈس کو تصادفی طور پر جوڑ کر گراف بنایا جاتا ہے۔ ہر کنارے کو ہر دوسرے کنارے سے آزادانہ طور پر امکان کے ساتھ گراف میں شامل کیا گیا ہے۔ اسی طرح، نوڈس اور کناروں والے ہر گراف کو تیار کرنے کا امکان ہے۔ اس ماڈل میں پیرامیٹر کو ویٹنگ فنکشن کے طور پر سوچا جا سکتا ہے۔ جیسے جیسے یہ بڑھتا جاتا ہے، ماڈل میں زیادہ کناروں والے گراف شامل ہونے کا امکان بڑھتا جاتا ہے اور کم کناروں والے گراف شامل ہونے کا امکان کم ہوتا جاتا ہے۔ خاص طور پر، معاملہ اس معاملے سے مطابقت رکھتا ہے جہاں عمودی مقامات پر موجود تمام گرافوں کو مساوی امکانات کے ساتھ منتخب کیا جاتا ہے۔ بے ترتیب گرافوں کے رویے کا اکثر اس صورت میں مطالعہ کیا جاتا ہے جہاں عمودی حصوں کی تعداد لامحدود ہوتی ہے۔ اگرچہ اور اس معاملے میں طے کیا جا سکتا ہے، وہ پر منحصر افعال بھی ہو سکتے ہیں۔ مثال کے طور پر، اس بیان کا کہ تقریبا ہر گراف جڑا ہوا ہے مطلب یہ ہے کہ، جیسا کہ انفینیٹی کی طرف جاتا ہے، امکان ہے کہ کناروں پر موجود گراف کنارے کے امکان کے ساتھ جڑا ہوا ہے۔ دونوں ماڈلز کے درمیان موازنہ G (n، p) میں کناروں کی متوقع تعداد ہے، اور بڑی تعداد کے قانون کے مطابق G (n، p) میں کسی بھی گراف میں تقریبا اتنے ہی کنارے ہوں گے (بشرطیکہ کناروں کی متوقع تعداد لامحدود ہو)۔ لہذا، ایک کھردری تحقیق یہ ہے کہ اگر pn2 → φ، تو G (n, p) کو G (n, M) کے ساتھ اسی طرح برتاؤ کرنا چاہیے جس طرح n میں اضافہ ہوتا ہے۔ گراف کی بہت سی خصوصیات کے لیے، یہ معاملہ ہے۔ اگر P کوئی گراف پراپرٹی ہے جو سب گراف آرڈرنگ کے حوالے سے مونوٹون ہے (مطلب یہ ہے کہ اگر A B کا سب گراف ہے اور B P کو مطمئن کرتا ہے، تو A P کو بھی مطمئن کرے گا)، تو بیانات "P تقریبا تمام گرافوں کے لیے G (n، p) میں رکھتا ہے" اور "P تقریبا تمام گرافوں کے لیے رکھتا ہے" مساوی ہیں (بشرطیکہ pn2 → φ)۔ مثال کے طور پر، اگر P منسلک ہونے کی خاصیت ہے، یا اگر P ہیملٹنین سائیکل پر مشتمل ہونے کی خاصیت ہے۔ تاہم، یہ ضروری نہیں کہ غیر مونوٹون خصوصیات کے لیے ہو (جیسے۔ کناروں کی یکساں تعداد ہونے کی خاصیت)۔ عملی طور پر، جی (این، پی) ماڈل آج کل زیادہ عام طور پر استعمال ہوتا ہے، جزوی طور پر کناروں کی آزادی کی اجازت سے تجزیہ میں آسانی کی وجہ سے۔ G (n، p) کی خصوصیات اوپر کے اشارے کے ساتھ، G (n، p) میں گراف کے اوسط کنارے ہوتے ہیں۔ کسی خاص ورٹیکس کی ڈگری کی تقسیم بائنومیل ہوتی ہے: جہاں n گراف میں عمودی کی کل تعداد ہے۔ چونکہ یہ تقسیم بڑے n اور np = کانسٹ کے لیے پوئسون ہے۔ 1960 کے ایک مقالے میں، ایرڈس اور رینی نے پی کی مختلف اقدار کے لیے جی (این، پی) کے رویے کو بہت واضح طور پر بیان کیا۔ ان کے نتائج میں یہ شامل تھا کہ: اگر این پی <1 ہے، تو جی (این، پی) میں گراف میں تقریبا یقینی طور پر او (لاگ (این)) سے بڑے سائز کے کوئی منسلک اجزاء نہیں ہوں گے۔ اگر np = 1 ہے، تو G (n، p) میں ایک گراف میں تقریبا یقینی طور پر ایک سب سے بڑا جزو ہوگا جس کا سائز n2/3 کی ترتیب کا ہو۔ اگر np → c> 1، جہاں c ایک مستقل ہے، تو G (n، p) میں ایک گراف میں تقریبا یقینی طور پر ایک منفرد وشال جزو ہوگا جس میں عمودی حصوں کا مثبت حصہ ہوگا۔ کسی دوسرے جزو میں او (لاگ (این)) عمودی سے زیادہ نہیں ہوگا۔ اگر، تو G (n، p) میں ایک گراف تقریبا یقینی طور پر الگ تھلگ عمودی پر مشتمل ہوگا، اور اس طرح منقطع ہو جائے گا۔ اگر، تو G (n، p) میں ایک گراف تقریبا یقینی طور پر منسلک ہوگا۔ اس طرح G (n، p) کے ربط کے لیے ایک تیز حد ہے۔ گراف کی مزید خصوصیات کو تقریبا عین مطابق بیان کیا جا سکتا ہے کیونکہ n کا رجحان انفینیٹی کی طرف ہوتا ہے۔ مثال کے طور پر، ایک k (n) (تقریبا 2log2 (n) کے برابر) ایسا ہے کہ G (n، 0.5) میں سب سے بڑا گروہ تقریبا یقینی طور پر یا تو سائز k (n) یا k (n) + 1 رکھتا ہے۔ اس طرح، اگرچہ گراف میں سب سے بڑے گروہ کا سائز تلاش کرنا این پی مکمل ہے، لیکن "عام" گراف میں سب سے بڑے گروہ کا سائز (اس ماڈل کے مطابق) بہت اچھی طرح سے سمجھا جاتا ہے۔ ایردوس-رینی گراف کے کنارے-دوہری گراف تقریبا ایک ہی ڈگری کی تقسیم والے گراف ہیں، لیکن ڈگری کے ارتباط اور نمایاں طور پر زیادہ کلسٹرنگ گتانک کے ساتھ۔ پرکولیشن تھیوری میں ایک محدود یا لامحدود گراف کا جائزہ لیا جاتا ہے اور کناروں (یا لنکس) کو تصادفی طور پر ہٹا دیا جاتا ہے۔ اس طرح ایرڈس-رینی عمل حقیقت میں مکمل گراف پر غیر وزنی لنک پرکولیشن ہے۔ (ایک سے مراد پرکولیشن ہے جس میں نوڈس اور/یا لنکس کو متنوع وزن کے ساتھ ہٹایا جاتا ہے)۔ چونکہ پرکولیشن تھیوری کی زیادہ تر جڑیں طبیعیات میں ہیں، اس لیے کی گئی زیادہ تر تحقیق یوکلڈین خالی جگہوں میں جالی پر تھی۔ این پی = 1 پر وشال جزو سے چھوٹے جزو میں منتقلی ان گرافوں کے لیے اینالاگ ہے، لیکن جالی کے لیے منتقلی کے نقطہ کا تعین کرنا مشکل ہے۔ طبیعیات دان اکثر مکمل گراف کے مطالعہ کو اوسط فیلڈ تھیوری کہتے ہیں۔ اس طرح ایرڈس-رینی عمل پرکولیشن کا اوسط فیلڈ کیس ہے۔ بے ترتیب گرافوں پر پرکولیشن پر بھی کچھ اہم کام کیا گیا۔ طبیعیات دان کے نقطہ نظر سے یہ اب بھی ایک اوسط فیلڈ ماڈل ہوگا، لہذا تحقیق کا جواز اکثر گراف کی مضبوطی کے لحاظ سے وضع کیا جاتا ہے، جسے مواصلاتی نیٹ ورک کے طور پر دیکھا جاتا ہے۔ اوسط ڈگری کے ساتھ n′1 نوڈس کا بے ترتیب گراف دیا گیا ہے۔ تصادفی طور پر نوڈس کا ایک حصہ ہٹا دیں اور نیٹ ورک سے صرف ایک حصہ چھوڑیں۔ ایک اہم پرکولیشن تھریشولڈ موجود ہے جس کے نیچے نیٹ ورک ٹکڑے ٹکڑے ہو جاتا ہے جبکہ اوپر آرڈر n کا ایک بڑا جڑا ہوا جزو موجود ہوتا ہے۔ وشال جزو، P ≤، کا نسبتا سائز کیوٹس کے ذریعہ دیا گیا ہے۔ G (n, p) ماڈل کے دونوں بڑے مفروضے (کہ کنارے آزاد ہیں اور ہر کنارے کا یکساں امکان ہے) بعض حقیقی زندگی کے مظاہر کی ماڈلنگ کے لیے نامناسب ہو سکتے ہیں۔ بہت سے سوشل نیٹ ورکس کے برعکس ایرڈس-رینی گراف میں کم کلسٹرنگ ہوتی ہے۔ ماڈلنگ کے کچھ متبادلات میں بارابیسی-البرٹ ماڈل اور واٹز اور سٹروگاٹز ماڈل شامل ہیں۔ یہ متبادل ماڈل پرکولیشن کے عمل نہیں ہیں، بلکہ بالترتیب گروتھ اور ری وائرنگ ماڈل کی نمائندگی کرتے ہیں۔ بے ترتیب گراف ماڈلز کا ایک اور متبادل خاندان، جو بہت سے حقیقی زندگی کے مظاہر کو دوبارہ پیش کرنے کے قابل ہے، بے ترتیب گراف ماڈل ہیں۔ جی (این، پی) ماڈل سب سے پہلے ایڈگر گلبرٹ نے 1959 کے ایک مقالے میں متعارف کرایا تھا جس میں اوپر بیان کردہ رابطے کی حد کا مطالعہ کیا گیا تھا۔ جی (این، ایم) ماڈل کو ایرڈس اور رینی نے اپنے 1959 کے مقالے میں متعارف کرایا تھا۔ گلبرٹ کی طرح، ان کی پہلی تحقیقات جی (این، ایم) کے رابطے کے بارے میں تھیں، جس کے بعد 1960 میں مزید تفصیلی تجزیہ کیا گیا۔ اہم G (n، p) کی تسلسل کی حد کی نمائندگی گراف کی تسلسل کی حد اس وقت حاصل کی گئی جب ترتیب کی ہو۔ خاص طور پر، گراف کی ترتیب پر غور کریں۔ لمٹ آبجیکٹ کو مندرجہ ذیل طریقے سے بنایا جا سکتا ہے: سب سے پہلے، ایک پھیلاؤ پیدا کریں جہاں ایک معیاری براؤنین حرکت ہے۔ اس عمل سے ہم عکاسی شدہ عمل کی وضاحت کرتے ہیں۔ اس عمل کو کئی مسلسل سیر پر مشتمل کے طور پر دیکھا جا سکتا ہے (براؤنین سیر نہیں، دیکھیں)۔ چونکہ کے بہاؤ کا غلبہ ہے، اس لیے یہ سیر مختصر اور مختصر ہوتی جاتی ہیں۔ خاص طور پر، ان کو گھٹتی ہوئی لمبائی کی ترتیب میں ترتیب دیا جا سکتا ہے: ہم گھٹتی ہوئی لمبائی کے وقفوں میں تقسیم کر سکتے ہیں جو کسی کے لیے براؤنین سیر تک محدود ہے۔ اب، ایک سیر پر غور کریں۔ مندرجہ ذیل بے ترتیب گراف بنائیں: ایک حقیقی درخت بنائیں (براؤنین ٹری دیکھیں)۔ یونٹ کی شدت کے ساتھ پوسن پوائنٹ کے عمل پر غور کریں۔ اس طرح کے ہر نقطہ کے لیے، ایک بنیادی اندرونی نوڈ اور درخت کے پتے سے مطابقت رکھتا ہے۔ دو عمودی حصوں کی شناخت کرتے ہوئے، درخت ایک گراف بن جاتا ہے۔ اس طریقہ کار کو لاگو کرتے ہوئے، کم ہوتے سائز کے بے ترتیب لامحدود گراف کی ترتیب حاصل ہوتی ہے: نظریہ بیان کرتا ہے کہ یہ گراف ایک خاص معنوں میں اس کے حد آبجیکٹ سے مطابقت رکھتا ہے۔ یہ بھی دیکھیں، G (n, p) ماڈل کو شمار کے لحاظ سے لامحدود تعداد میں عمودی نقاط کے ساتھ گراف تک بڑھا کر بنایا گیا گراف۔ محدود صورت کے برعکس، اس لامحدود عمل کا نتیجہ (امکان 1 کے ساتھ) آئسومورفزم تک ایک ہی گراف ہے۔ ان طریقوں کو بیان کرتا ہے جن میں ایرڈس-رینی ماڈل سے وابستہ خصوصیات نظام میں ترتیب کے ظہور میں معاون ہیں۔ نیٹ ورک کے اعداد و شمار اور ان سے وابستہ مختلف پیرامیٹرز کے ایک سیٹ کو دیکھتے ہوئے "این" نوڈس پر گراف کی عمومی امکانات کی تقسیم کو بیان کریں۔ لیٹنٹ کمیونٹی ڈھانچے کے ساتھ گراف کے لیے ایردوس-رینی ماڈل کی عمومی شکل حوالہ جات ادب ویب لنکس ویڈیو: ایردوس-رینی بے ترتیب گراف بے ترتیب گراف رینی ماڈل