Erdős–Rényi model
வரைபடக் கோட்பாட்டின் கணிதத் துறையில், எர்டாஸ்-ரெனி மாதிரி சீரற்ற வரைபடங்களை உருவாக்குவதற்கான இரண்டு நெருக்கமான தொடர்புடைய மாதிரிகளில் ஒன்றைக் குறிக்கிறது அல்லது சீரற்ற நெட்வொர்க்கின் பரிணாமம். 1959 ஆம் ஆண்டில் ஒரு மாதிரியை அறிமுகப்படுத்திய ஹங்கேரிய கணிதவியலாளர்களான பால் எர்டாஸ் மற்றும் ஆல்ஃப்ரெட் ரெனி ஆகியோரின் பெயரால் இந்த மாதிரிகள் பெயரிடப்பட்டுள்ளன. எட்கர் கில்பர்ட் மற்ற மாதிரியை எர்டாஸ் மற்றும் ரெனியுடன் சமகாலத்திலும் சுயாதீனமாகவும் அறிமுகப்படுத்தினார். எர்டாஸ் மற்றும் ரென்யியின் மாதிரியில், ஒரு நிலையான உச்சியில் ஒரு நிலையான எண்ணிக்கையிலான விளிம்புகளுடன் கூடிய அனைத்து வரைபடங்களும் சமமாக சாத்தியமாகும். கில்பர்ட் அறிமுகப்படுத்திய மாதிரியில், எர்டாஸ்-ரெனி-கில்பர்ட் மாதிரி என்றும் அழைக்கப்படுகிறது, ஒவ்வொரு விளிம்பும் மற்ற விளிம்புகளிலிருந்து சுயாதீனமாக இருக்கும் அல்லது இல்லாத ஒரு நிலையான நிகழ்தகவைக் கொண்டுள்ளது. பல்வேறு பண்புகளை திருப்திப்படுத்தும் வரைபடங்களின் இருப்பை நிரூபிக்க அல்லது கிட்டத்தட்ட அனைத்து வரைபடங்களுக்கும் ஒரு பண்பு வைத்திருப்பது என்றால் என்ன என்பதற்கான கடுமையான வரையறையை வழங்க இந்த மாதிரிகள் நிகழ்தகவு முறையில் பயன்படுத்தப்படலாம். வரையறை எர்டாஸ்-ரெனி சீரற்ற வரைபட மாதிரியின் இரண்டு நெருக்கமான தொடர்புடைய வகைகள் உள்ளன. மாதிரியில், முனைகள் மற்றும் விளிம்புகளைக் கொண்ட அனைத்து வரைபடங்களின் தொகுப்பிலிருந்தும் ஒரு வரைபடம் சீரற்ற முறையில் ஒரே மாதிரியாகத் தேர்ந்தெடுக்கப்படுகிறது. முனைகள் பெயரிடப்பட்டதாகக் கருதப்படுகின்றன, அதாவது செங்குத்துகளை வரிசைப்படுத்துவதன் மூலம் ஒருவருக்கொருவர் பெறப்பட்ட வரைபடங்கள் தனித்துவமானதாகக் கருதப்படுகின்றன. எடுத்துக்காட்டாக, மாதிரியில், மூன்று பெயரிடப்பட்ட செங்குத்துகளில் மூன்று இரண்டு முனை வரைபடங்கள் உள்ளன (இரண்டு முனை பாதையில் நடுத்தர உச்சியின் ஒவ்வொரு தேர்வுக்கும் ஒன்று), மேலும் இந்த மூன்று வரைபடங்களில் ஒவ்வொன்றும் நிகழ்தகவுடன் சேர்க்கப்பட்டுள்ளன. மாதிரியில், பெயரிடப்பட்ட முனைகளை சீரற்ற முறையில் இணைப்பதன் மூலம் ஒரு வரைபடம் கட்டமைக்கப்படுகிறது. ஒவ்வொரு விளிம்பும் ஒவ்வொரு விளிம்பிலிருந்தும் சுயாதீனமாக நிகழ்தகவுடன் வரைபடத்தில் சேர்க்கப்பட்டுள்ளது. சமமாக, முனைகள் மற்றும் விளிம்புகளைக் கொண்ட ஒவ்வொரு வரைபடத்தையும் உருவாக்குவதற்கான நிகழ்தகவு இந்த மாதிரியில் உள்ள அளவுருவை ஒரு எடை செயல்பாடாக கருதலாம்; முதல் முதல் வரை அதிகரிக்கும் போது, மாதிரி அதிக விளிம்புகளைக் கொண்ட வரைபடங்களை சேர்க்க அதிக வாய்ப்புள்ளது மற்றும் குறைவான விளிம்புகளைக் கொண்ட வரைபடங்களை சேர்க்க குறைவான வாய்ப்புள்ளது. குறிப்பாக, செங்குத்துகளில் உள்ள அனைத்து வரைபடங்களும் சமமான நிகழ்தகவுடன் தேர்ந்தெடுக்கப்படும் வழக்குடன் இந்த வழக்கு ஒத்திருக்கிறது. சீரற்ற வரைபடங்களின் நடத்தை பெரும்பாலும் செங்குத்துகளின் எண்ணிக்கை முடிவிலிக்குச் செல்லும் விஷயத்தில் ஆய்வு செய்யப்படுகிறது. இந்த விஷயத்தில் சரிசெய்ய முடியும் என்றாலும், அவை பொறுத்து செயல்பாடுகளாகவும் இருக்கலாம். எடுத்துக்காட்டாக, கிட்டத்தட்ட ஒவ்வொரு வரைபடமும் இணைக்கப்பட்டுள்ளது என்ற கூற்று, முடிவிலிக்குச் செல்வதைப் போல, விளிம்பு நிகழ்தகவுடன் செங்குத்துகளில் ஒரு வரைபடம் இணைக்கப்படுவதற்கான நிகழ்தகவு என்று பொருள்படும். இரண்டு மாதிரிகளுக்கிடையேயான ஒப்பீடு G (n, p) இல் எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை, மற்றும் பெரிய எண்களின் சட்டத்தின்படி G (n, p) இல் உள்ள எந்தவொரு வரைபடமும் கிட்டத்தட்ட இந்த பல விளிம்புகளைக் கொண்டிருக்கும் (எதிர்பார்க்கப்படும் விளிம்புகளின் எண்ணிக்கை முடிவிலிக்கு முனைகிறது). எனவே, ஒரு தோராயமான ஹூரிஸ்டிக் என்னவென்றால், pn2 → ν என்றால், G (n, p), n அதிகரிக்கும் போது G (n, M) ஐப் போலவே செயல்பட வேண்டும். பல வரைபட பண்புகளுக்கு, இது பொருந்தும். துணை வரைபட வரிசைமுறையைப் பொறுத்தவரை மோனோடோனாக இருக்கும் எந்தவொரு வரைபட பண்பாகவும் P இருந்தால் (அதாவது A என்பது B இன் துணை வரைபடமாகவும், B என்பது P ஐ திருப்திப்படுத்துவதாகவும் இருந்தால், A என்பது P ஐ திருப்திப்படுத்தும்), பின்னர் "G (n, p) இல் உள்ள கிட்டத்தட்ட அனைத்து வரைபடங்களுக்கும் P வைத்திருக்கிறது" மற்றும் "P கிட்டத்தட்ட அனைத்து வரைபடங்களுக்கும் வைத்திருக்கிறது" என்ற அறிக்கைகள் சமமானவை (pn2 → φ வழங்கப்பட்டால்). எடுத்துக்காட்டாக, P என்பது இணைக்கப்பட்டிருப்பதன் பண்பு என்றால் அல்லது P என்பது ஹாமில்டோனியன் சுழற்சியைக் கொண்டிருப்பதன் பண்பு என்றால் இது பொருந்தும். இருப்பினும், இது மோனோடோன் அல்லாத பண்புகளுக்கு பொருந்தாது (எ. கா. சம எண்ணிக்கையிலான விளிம்புகளைக் கொண்டிருப்பதன் பண்பு). நடைமுறையில், ஜி (என், பி) மாதிரி இன்று பொதுவாகப் பயன்படுத்தப்படுகிறது, ஓரளவு விளிம்புகளின் சுதந்திரத்தால் அனுமதிக்கப்பட்ட பகுப்பாய்வின் எளிமை காரணமாக. G (n, p) இன் பண்புகள் மேலே உள்ள குறியீட்டுடன், G (n, p) இல் உள்ள ஒரு வரைபடம் சராசரி விளிம்புகளைக் கொண்டுள்ளது. எந்தவொரு குறிப்பிட்ட உச்சியின் டிகிரியின் விநியோகமும் பைனாமியல் ஆகும்ஃ இங்கு n என்பது வரைபடத்தில் உள்ள மொத்த உச்சிகளின் எண்ணிக்கை. இந்த விநியோகம் பெரிய n மற்றும் np = கான்ஸ்ட்டுக்கு பாய்சான் என்பதால். 1960 ஆம் ஆண்டு ஆய்வறிக்கையில், எர்டாஸ் மற்றும் ரேனி ஆகியோர் p இன் பல்வேறு மதிப்புகளுக்கு G (n, p) இன் நடத்தையை மிகவும் துல்லியமாக விவரித்தனர். அவற்றின் முடிவுகள் பின்வருமாறுஃ np <1 என்றால், G (n, p) இல் உள்ள ஒரு வரைபடம் கிட்டத்தட்ட நிச்சயமாக O (log (n)) ஐ விட பெரிய அளவிலான இணைக்கப்பட்ட கூறுகளைக் கொண்டிருக்காது. np = 1 என்றால், G (n, p) இல் உள்ள ஒரு வரைபடம் கிட்டத்தட்ட நிச்சயமாக n2/3 வரிசையில் இருக்கும் மிகப்பெரிய கூறுகளைக் கொண்டிருக்கும். np → c> 1 என்றால், c ஒரு மாறிலி என்றால், G (n, p) இல் உள்ள ஒரு வரைபடம் கிட்டத்தட்ட நிச்சயமாக செங்குத்துகளின் நேர்மறை பின்னத்தைக் கொண்ட ஒரு தனித்துவமான மாபெரும் கூறுகளைக் கொண்டிருக்கும். வேறு எந்த கூறுகளும் O (log (n)) செங்குத்துகளுக்கு மேல் இருக்காது. அப்படியானால், G (n, p) இல் உள்ள ஒரு வரைபடம் கிட்டத்தட்ட நிச்சயமாக தனிமைப்படுத்தப்பட்ட செங்குத்துகளைக் கொண்டிருக்கும், இதனால் துண்டிக்கப்படும். அப்படியானால், G (n, p) இல் உள்ள ஒரு வரைபடம் கிட்டத்தட்ட நிச்சயமாக இணைக்கப்படும். எனவே G (n, p) இன் இணைப்புக்கு ஒரு கூர்மையான வரம்பு உள்ளது. வரைபடத்தின் மேலும் பண்புகள் கிட்டத்தட்ட துல்லியமாக விவரிக்கப்படலாம், ஏனெனில் n முடிவிலிக்கு முனைகிறது. எடுத்துக்காட்டாக, ஒரு k (n) (தோராயமாக 2log2 (n) க்கு சமம்) உள்ளது, அதாவது G (n, 0.5) இல் உள்ள மிகப்பெரிய குழு கிட்டத்தட்ட நிச்சயமாக அளவு k (n) அல்லது k (n) + 1 ஐக் கொண்டுள்ளது. எனவே, ஒரு வரைபடத்தில் மிகப்பெரிய குழுவின் அளவைக் கண்டுபிடிப்பது NP-முழுமையானது என்றாலும், ஒரு "வழக்கமான" வரைபடத்தில் (இந்த மாதிரியின் படி) மிகப்பெரிய குழுவின் அளவு நன்கு புரிந்து கொள்ளப்படுகிறது. எர்டோஸ்-ரென்யி வரைபடங்களின் விளிம்பு-இரட்டை வரைபடங்கள் கிட்டத்தட்ட ஒரே டிகிரி விநியோகத்தைக் கொண்ட வரைபடங்கள், ஆனால் டிகிரி தொடர்புகள் மற்றும் கணிசமாக அதிக கிளஸ்டரிங் குணகம் கொண்டவை. துளையிடுதல் கோட்பாட்டில் ஒருவர் ஒரு வரையறுக்கப்பட்ட அல்லது எல்லையற்ற வரைபடத்தை ஆராய்ந்து விளிம்புகளை (அல்லது இணைப்புகள்) சீரற்ற முறையில் அகற்றுகிறார். எனவே எர்டாஸ்-ரெனி செயல்முறை உண்மையில் முழுமையான வரைபடத்தில் எடை இல்லாத இணைப்பு ஊடுருவல் ஆகும். (ஒன்று கணுக்கள் மற்றும்/அல்லது இணைப்புகள் எடை உட்செலுத்தலாக பன்முக எடைகளுடன் அகற்றப்படும் உட்செலுத்துதலைக் குறிக்கிறது). ஊடுருவல் கோட்பாடு இயற்பியலில் அதன் வேர்களைக் கொண்டிருப்பதால், செய்யப்பட்ட ஆராய்ச்சியின் பெரும்பகுதி யூக்ளிடியன் இடைவெளிகளில் உள்ள லட்டிஸ்களில் இருந்தது. np = 1 இல் மாபெரும் கூறுகளிலிருந்து சிறிய கூறுகளுக்கு மாறுவது இந்த வரைபடங்களுக்கான ஒப்புமைகளைக் கொண்டுள்ளது, ஆனால் லட்டிஸ்களுக்கு மாற்றம் புள்ளியை தீர்மானிப்பது கடினம். இயற்பியலாளர்கள் பெரும்பாலும் முழுமையான வரைபடத்தைப் பற்றிய ஆய்வை ஒரு சராசரி புலக் கோட்பாடாகக் குறிப்பிடுகின்றனர். எனவே எர்டாஸ்-ரெனி செயல்முறை என்பது கசிவுக்கான சராசரி-புலம் வழக்கு ஆகும். சீரற்ற வரைபடங்களில் ஊடுருவல் குறித்து சில குறிப்பிடத்தக்க வேலைகளும் செய்யப்பட்டன. ஒரு இயற்பியலாளரின் பார்வையில் இது இன்னும் ஒரு சராசரி-கள மாதிரியாக இருக்கும், எனவே ஆராய்ச்சியின் நியாயப்படுத்தல் பெரும்பாலும் வரைபடத்தின் வலுவான தன்மையின் அடிப்படையில் வடிவமைக்கப்படுகிறது, இது ஒரு தகவல்தொடர்பு வலையமைப்பாக பார்க்கப்படுகிறது. ஒரு சராசரி டிகிரியுடன் n′1 முனைகளின் சீரற்ற வரைபடம் கொடுக்கப்பட்டுள்ளது. தோராயமாக முனைகளின் ஒரு பகுதியை அகற்றி நெட்வொர்க்கிலிருந்து ஒரு பகுதியை மட்டுமே விட்டு விடுங்கள். ஒரு முக்கியமான ஊடுருவல் வரம்பு உள்ளது, அதற்குக் கீழே நெட்வொர்க் துண்டிக்கப்படுகிறது, அதே நேரத்தில் வரிசை n இன் ஒரு மாபெரும் இணைக்கப்பட்ட கூறு மேலே உள்ளது. ஜி (என், பி) மாதிரியின் இரண்டு முக்கிய அனுமானங்கள் (விளிம்புகள் சுயாதீனமானவை மற்றும் ஒவ்வொரு விளிம்பும் சமமாக இருக்கலாம்) சில நிஜ வாழ்க்கை நிகழ்வுகளை மாதிரியாக்குவதற்கு பொருத்தமற்றதாக இருக்கலாம். பல சமூக வலைப்பின்னல்களைப் போலல்லாமல், எர்டாஸ்-ரென்னி வரைபடங்கள் குறைந்த தொகுப்பைக் கொண்டுள்ளன. சில மாடலிங் மாற்றுகளில் பரபாசி-ஆல்பர்ட் மாடல் மற்றும் வாட்ஸ் மற்றும் ஸ்ட்ரோகாட்ஸ் மாடல் ஆகியவை அடங்கும். இந்த மாற்று மாதிரிகள் ஊடுருவல் செயல்முறைகள் அல்ல, மாறாக முறையே வளர்ச்சி மற்றும் ரீவைரிங் மாதிரியைக் குறிக்கின்றன. சீரற்ற வரைபட மாதிரிகளின் மற்றொரு மாற்று குடும்பம், பல நிஜ வாழ்க்கை நிகழ்வுகளை இனப்பெருக்கம் செய்யும் திறன் கொண்டது, அதிவேக சீரற்ற வரைபட மாதிரிகள் ஆகும். ஜி (என், பி) மாதிரி முதன்முதலில் எட்கர் கில்பெர்ட் என்பவரால் 1959 ஆம் ஆண்டு மேலே குறிப்பிடப்பட்ட இணைப்பு வரம்பைப் படிக்கும் ஆய்வறிக்கையில் அறிமுகப்படுத்தப்பட்டது. ஜி (என், எம்) மாடல் எர்டாஸ் மற்றும் ரென்யி ஆகியோரால் அவர்களின் 1959 ஆய்வறிக்கையில் அறிமுகப்படுத்தப்பட்டது. கில்பெர்ட்டைப் போலவே, அவர்களின் முதல் விசாரணைகள் ஜி (என், எம்) இன் இணைப்பு குறித்து இருந்தன, மேலும் விரிவான பகுப்பாய்வு 1960 இல் தொடர்ந்தது. முக்கியமான G (n, p) இன் தொடர்ச்சியான வரம்பு பிரதிநிதித்துவம் ஒரு தொடர்ச்சியான வரம்பின் வரைபடம் வரிசையில் இருக்கும்போது பெறப்பட்டது. குறிப்பாக, வரைபடங்களின் வரிசையைக் கவனியுங்கள். வரம்பு பொருளை பின்வருமாறு கட்டமைக்க முடியும்ஃ முதலில், ஒரு நிலையான பிரவுனியன் இயக்கத்தில் ஒரு பரவலை உருவாக்கவும். இந்த செயல்முறையிலிருந்து, பிரதிபலித்த செயல்முறையை வரையறுக்கிறோம். இந்த செயல்முறை பல தொடர்ச்சியான பயணங்களைக் கொண்டிருப்பதாகக் காணலாம் (ஒரு பிரவுனியன் பயணம் அல்ல, பார்க்கவும்). நகர்வுகள் ஆதிக்கம் செலுத்துவதால், இந்த பயணங்கள் குறுகியதாகவும் குறுகியதாகவும் மாறும். குறிப்பாக, நீளங்களைக் குறைக்கும் வரிசையில் அவற்றை வரிசைப்படுத்தலாம்ஃ எந்த ஒரு பிரவுனியன் பயணத்திற்கும் கட்டுப்படுத்தப்பட்ட நீளங்களைக் குறைக்கும் இடைவெளிகளாக நாம் பிரிக்கலாம். இப்போது, ஒரு சுற்றுலாவைப் பற்றி சிந்தியுங்கள். பின்வருமாறு ஒரு சீரற்ற வரைபடத்தை உருவாக்குங்கள்ஃ ஒரு உண்மையான மரத்தை உருவாக்குங்கள் (பிரவுனியன் மரத்தைப் பார்க்கவும்). ஒரு பாய்சான் புள்ளி செயல்முறையை அலகு தீவிரத்துடன் கருத்தில் கொள்ளுங்கள். ஒவ்வொரு புள்ளிக்கும், ஒரு அடிப்படை உள் முனை மற்றும் மரத்தின் இலைக்கு ஒத்திருக்கிறது. இரண்டு செங்குத்துகளையும் அடையாளம் கண்டு, மரம் ஒரு வரைபடமாக மாறுகிறது இந்த செயல்முறையைப் பயன்படுத்தி, ஒருவர் குறைந்து வரும் அளவுகளின் சீரற்ற எல்லையற்ற வரைபடங்களின் வரிசையைப் பெறுகிறார்ஃ இந்த வரைபடம் ஒரு குறிப்பிட்ட அர்த்தத்தில் வரம்பு பொருளுடன் ஒத்திருக்கிறது என்று தேற்றம் கூறுகிறது. மேலும், G (n, p) மாதிரியை எண்ணற்ற எண்ணிக்கையிலான செங்குத்துகளுடன் வரைபடங்களுக்கு விரிவுபடுத்துவதன் மூலம் உருவாக்கப்பட்ட வரைபடத்தையும் பார்க்கவும். வரையறுக்கப்பட்ட வழக்கில் போலல்லாமல், இந்த எல்லையற்ற செயல்முறையின் விளைவு (நிகழ்தகவு 1 உடன்) ஐசோமார்பிசம் வரை ஒரே வரைபடமாகும். எர்டாஸ்-ரெனி மாதிரியுடன் தொடர்புடைய பண்புகள் அமைப்புகளில் ஒழுங்கின் தோற்றத்திற்கு பங்களிக்கும் வழிகளை விவரிக்கிறது. நெட்வொர்க் புள்ளிவிவரங்கள் மற்றும் அவற்றுடன் தொடர்புடைய பல்வேறு அளவுருக்களின் தொகுப்பு கொடுக்கப்பட்ட "n" முனைகளில் வரைபடங்களின் பொதுவான நிகழ்தகவு விநியோகத்தை விவரிக்கவும். மறைந்த சமூக கட்டமைப்பைக் கொண்ட வரைபடங்களுக்கான எர்டாஸ்-ரெனி மாதிரியின் பொதுமைப்படுத்தல் குறிப்புகள் இலக்கிய வலை இணைப்புகள் வீடியோஃ எர்டாஸ்-ரெனி சீரற்ற வரைபடம் சீரற்ற வரைபடங்கள் ரெனி மாதிரி