Erdős–Rényi model
গ্রাফ তত্ত্বের গাণিতিক ক্ষেত্রে, এরদোস-রেনি মডেল এলোমেলো গ্রাফ তৈরি বা এলোমেলো নেটওয়ার্কের বিবর্তনের জন্য দুটি ঘনিষ্ঠভাবে সম্পর্কিত মডেলের একটিকে বোঝায়। এই মডেলগুলির নামকরণ করা হয়েছে হাঙ্গেরিয়ান গণিতবিদ পল এরদোস এবং আলফ্রেড রেনির নামে, যিনি 1959 সালে একটি মডেল চালু করেছিলেন। এডগার গিলবার্ট অন্য মডেলটি সমসাময়িকভাবে এরদোস এবং রেনির সাথে এবং স্বাধীনভাবে প্রবর্তন করেছিলেন। এরদোস এবং রেনির মডেলে, একটি নির্দিষ্ট সংখ্যক প্রান্ত সহ একটি নির্দিষ্ট শীর্ষের সেটের সমস্ত গ্রাফ সমানভাবে সম্ভাব্য। গিলবার্ট দ্বারা প্রবর্তিত মডেলে, যাকে এরডোস-রেনি-গিলবার্ট মডেলও বলা হয়, প্রতিটি প্রান্তের অন্যান্য প্রান্ত থেকে স্বাধীনভাবে উপস্থিত বা অনুপস্থিত থাকার একটি নির্দিষ্ট সম্ভাবনা রয়েছে। এই মডেলগুলি সম্ভাব্য পদ্ধতিতে বিভিন্ন বৈশিষ্ট্যকে সন্তুষ্ট করে এমন গ্রাফের অস্তিত্ব প্রমাণ করতে বা প্রায় সমস্ত গ্রাফের জন্য কোনও সম্পত্তি ধরে রাখার অর্থ কী তার একটি কঠোর সংজ্ঞা প্রদান করতে ব্যবহার করা যেতে পারে। সংজ্ঞা এরদোস-রেনি র্যান্ডম গ্রাফ মডেলের দুটি ঘনিষ্ঠভাবে সম্পর্কিত রূপ রয়েছে। মডেলে, নোড এবং প্রান্তযুক্ত সমস্ত গ্রাফের সংগ্রহ থেকে একটি গ্রাফ এলোমেলোভাবে সমানভাবে বেছে নেওয়া হয়। নোডগুলিকে লেবেলযুক্ত বলে মনে করা হয়, যার অর্থ হল যে শীর্ষগুলি বিন্যস্ত করে একে অপরের থেকে প্রাপ্ত গ্রাফগুলি স্বতন্ত্র বলে মনে করা হয়। উদাহরণস্বরূপ, মডেলটিতে, তিনটি লেবেলযুক্ত শীর্ষে তিনটি দ্বিমুখী গ্রাফ রয়েছে (দ্বিমুখী পথে মধ্য শীর্ষের প্রতিটি পছন্দের জন্য একটি), এবং এই তিনটি গ্রাফের প্রত্যেকটি সম্ভাব্যতা সহ অন্তর্ভুক্ত করা হয়েছে। মডেলটিতে, লেবেলযুক্ত নোডগুলিকে এলোমেলোভাবে সংযুক্ত করে একটি গ্রাফ তৈরি করা হয়। প্রতিটি প্রান্ত প্রতিটি অন্য প্রান্ত থেকে স্বাধীনভাবে সম্ভাব্যতা সহ গ্রাফে অন্তর্ভুক্ত করা হয়েছে। সমতুল্যভাবে, নোড এবং প্রান্তযুক্ত প্রতিটি গ্রাফ তৈরির সম্ভাবনা হল এই মডেলের পরামিতিটিকে একটি ওজন ফাংশন হিসাবে ভাবা যেতে পারে; যত থেকে যত বৃদ্ধি পায়, মডেলটি আরও বেশি প্রান্তযুক্ত গ্রাফ অন্তর্ভুক্ত করার সম্ভাবনা কমতে থাকে এবং কম প্রান্তযুক্ত গ্রাফ অন্তর্ভুক্ত করার সম্ভাবনা কমতে থাকে। বিশেষত, কেসটি সেই ক্ষেত্রে মিলে যায় যেখানে শীর্ষে সমস্ত গ্রাফ সমান সম্ভাবনার সাথে বেছে নেওয়া হয়। এলোমেলো গ্রাফের আচরণ প্রায়শই এমন ক্ষেত্রে অধ্যয়ন করা হয় যেখানে, শীর্ষগুলির সংখ্যা অনন্তের দিকে থাকে। যদিও এবং এই ক্ষেত্রে স্থির করা যেতে পারে, তারা উপর নির্ভর করে ফাংশনও হতে পারে। উদাহরণস্বরূপ, প্রায় প্রতিটি গ্রাফ সংযুক্ত থাকার বিবৃতির অর্থ হল, যেমন অনন্তের দিকে প্রবণতা রয়েছে, প্রান্তের সম্ভাব্যতা সহ শীর্ষে একটি গ্রাফ সংযুক্ত হওয়ার সম্ভাবনা রয়েছে। দুটি মডেলের মধ্যে তুলনা জি (এন, পি)-তে প্রান্তের প্রত্যাশিত সংখ্যা হল, এবং বড় সংখ্যার আইন অনুসারে জি (এন, পি)-তে যে কোনও গ্রাফের প্রায় এতগুলি প্রান্ত থাকবে (যদি প্রান্তের প্রত্যাশিত সংখ্যা অসীমের দিকে থাকে)। অতএব, একটি মোটামুটি অনুসন্ধানমূলক বিষয় হল যে, যদি pn2 → φ হয়, তাহলে G (n, p)-এর G (n, M)-এর মতো একই আচরণ করা উচিত, যেমন n বৃদ্ধি পায়। অনেক গ্রাফের বৈশিষ্ট্যের ক্ষেত্রে, এটি হয়। যদি পি কোনও গ্রাফের বৈশিষ্ট্য হয় যা উপগ্রাফ ক্রমের ক্ষেত্রে একমুখী হয় (অর্থাৎ যদি এ বি-এর একটি উপগ্রাফ হয় এবং বি পি-কে সন্তুষ্ট করে, তবে এ পি-কে সন্তুষ্ট করবে), তবে বিবৃতিগুলি "পি জি (এন, পি)-এর প্রায় সমস্ত গ্রাফের জন্য ধারণ করে" এবং "পি প্রায় সমস্ত গ্রাফের জন্য ধারণ করে" সমতুল্য (প্রদত্ত পিএন2 → φ)। উদাহরণস্বরূপ, এটি ধারণ করে যদি পি সংযুক্ত হওয়ার বৈশিষ্ট্য হয়, অথবা যদি পি হ্যামিল্টনিয়ান চক্র ধারণ করার বৈশিষ্ট্য হয়। যাইহোক, এটি অগত্যা অ-মনোটোন বৈশিষ্ট্যের জন্য প্রযোজ্য হবে না (যেমন। জোড় সংখ্যক প্রান্ত থাকার বৈশিষ্ট্য)। বাস্তবে, জি (এন, পি) মডেলটি আজ আরও বেশি ব্যবহৃত হয়, আংশিকভাবে প্রান্তগুলির স্বাধীনতা দ্বারা অনুমোদিত বিশ্লেষণের স্বাচ্ছন্দ্যের কারণে। জি (এন, পি)-এর বৈশিষ্ট্যগুলি উপরের স্বরলিপির সাথে, জি (এন, পি)-এর একটি গ্রাফের গড় প্রান্ত রয়েছে। যে কোনও নির্দিষ্ট শীর্ষের ডিগ্রির বন্টন দ্বিপদীঃ যেখানে n হল গ্রাফের মোট শীর্ষ সংখ্যা। যেহেতু এই বন্টনটি বড় n এর জন্য পয়সন এবং np = স্থির। 1960 সালের একটি গবেষণাপত্রে, এরদোস এবং রেনি পি-এর বিভিন্ন মানের জন্য জি (এন, পি)-এর আচরণ খুব সুনির্দিষ্টভাবে বর্ণনা করেছেন। তাদের ফলাফলের মধ্যে রয়েছেঃ যদি এনপি <1 হয়, তবে জি (এন, পি)-এর একটি গ্রাফের প্রায় অবশ্যই ও (লগ (এন))-এর চেয়ে বড় আকারের কোনও সংযুক্ত উপাদান থাকবে না। যদি np = 1 হয়, তাহলে G (n, p)-এর একটি গ্রাফের প্রায় অবশ্যই একটি বৃহত্তম উপাদান থাকবে যার আকার n2/3 ক্রমের হবে। যদি np → c> 1 হয়, যেখানে c একটি ধ্রুবক, তাহলে G (n, p)-এর একটি গ্রাফের প্রায় অবশ্যই একটি অনন্য দৈত্য উপাদান থাকবে যা শীর্ষগুলির একটি ধনাত্মক ভগ্নাংশ ধারণ করবে। অন্য কোনও উপাদান ও (লগ (এন)) শীর্ষের চেয়ে বেশি থাকবে না। যদি, তাহলে জি (এন, পি)-এর একটি গ্রাফে প্রায় নিশ্চিতভাবে বিচ্ছিন্ন শীর্ষ থাকবে, এবং এইভাবে সংযোগ বিচ্ছিন্ন হয়ে যাবে। যদি, তাহলে জি (এন, পি)-এর একটি গ্রাফ প্রায় নিশ্চিতভাবে সংযুক্ত থাকবে। এইভাবে জি (এন, পি)-এর সংযোগের জন্য একটি তীক্ষ্ণ সীমা। গ্রাফের আরও বৈশিষ্ট্যগুলি প্রায় সুনির্দিষ্টভাবে বর্ণনা করা যেতে পারে যেমন n অনন্তের দিকে ঝোঁক রাখে। উদাহরণস্বরূপ, একটি k (n) (প্রায় 2log2 (n) এর সমান) রয়েছে যাতে G (n, 0.5)-এর বৃহত্তম চক্রের প্রায় নিশ্চিত আকার হয় k (n) বা k (n) + 1। সুতরাং, যদিও একটি গ্রাফে বৃহত্তম গোষ্ঠীর আকার খুঁজে পাওয়া এনপি-সম্পূর্ণ, একটি "সাধারণ" গ্রাফে বৃহত্তম গোষ্ঠীর আকার (এই মডেল অনুসারে) খুব ভালভাবে বোঝা যায়। এরডোস-রেনি গ্রাফের প্রান্ত-দ্বৈত গ্রাফগুলি প্রায় একই ডিগ্রি বিতরণ সহ গ্রাফ, তবে ডিগ্রি পারস্পরিক সম্পর্ক এবং উল্লেখযোগ্যভাবে উচ্চতর ক্লাস্টারিং সহগ সহ। পারকোলেশনের সাথে সম্পর্ক পারকোলেশন তত্ত্বে একজন একটি সীমাবদ্ধ বা অসীম গ্রাফ পরীক্ষা করে এবং এলোমেলোভাবে প্রান্তগুলি (বা লিঙ্কগুলি) সরিয়ে দেয়। এইভাবে এরদোস-রেনি প্রক্রিয়াটি প্রকৃতপক্ষে সম্পূর্ণ গ্রাফের উপর ভারহীন লিঙ্ক পারকোলেশন। (একটি পারকোলেশনকে বোঝায় যেখানে নোড এবং/অথবা লিঙ্কগুলি ওজনযুক্ত পারকোলেশন হিসাবে ভিন্ন ওজনের সাথে সরানো হয়)। যেহেতু পারকোলেশন তত্ত্বের বেশিরভাগ শিকড় পদার্থবিজ্ঞানে রয়েছে, তাই বেশিরভাগ গবেষণা ইউক্লিডীয় স্থানের জালের উপর করা হয়েছিল। এন. পি = 1-এ বিশাল উপাদান থেকে ছোট উপাদানের রূপান্তরের জন্য এই গ্রাফগুলির সাদৃশ্য রয়েছে, তবে ল্যাটিসের জন্য রূপান্তর বিন্দু নির্ধারণ করা কঠিন। পদার্থবিজ্ঞানীরা প্রায়শই সম্পূর্ণ গ্রাফের অধ্যয়নকে গড় ক্ষেত্র তত্ত্ব হিসাবে উল্লেখ করেন। এইভাবে এরদোস-রেনি প্রক্রিয়া হল পারকোলেশনের গড় ক্ষেত্র। এলোমেলো গ্রাফের উপর কিছু উল্লেখযোগ্য কাজও করা হয়েছিল। একজন পদার্থবিজ্ঞানীর দৃষ্টিকোণ থেকে এটি এখনও একটি গড়-ক্ষেত্রের মডেল হবে, তাই গবেষণার ন্যায্যতা প্রায়শই গ্রাফের দৃust়তার পরিপ্রেক্ষিতে প্রণয়ন করা হয়, যা একটি যোগাযোগ নেটওয়ার্ক হিসাবে দেখা হয়। একটি গড় ডিগ্রি সহ n′1 নোডের একটি র্যান্ডম গ্রাফ দেওয়া হয়েছে। এলোমেলোভাবে নোডের একটি ভগ্নাংশ সরিয়ে ফেলুন এবং নেটওয়ার্ক থেকে শুধুমাত্র একটি ভগ্নাংশ রেখে দিন। একটি ক্রিটিক্যাল পারকোলেশন থ্রেশহোল্ড রয়েছে যার নীচে নেটওয়ার্কটি খণ্ডিত হয়ে যায় এবং উপরে অর্ডার এন-এর একটি বিশাল সংযুক্ত উপাদান বিদ্যমান। দৈত্য উপাদানের আপেক্ষিক আকার, পি ≤, ক্যাভিটস দ্বারা দেওয়া হয়েছে জি (এন, পি) মডেলের দুটি প্রধান অনুমান (যে প্রান্তগুলি স্বাধীন এবং প্রতিটি প্রান্ত সমানভাবে সম্ভাব্য) নির্দিষ্ট বাস্তব জীবনের ঘটনাগুলির মডেলিংয়ের জন্য অনুপযুক্ত হতে পারে। অনেক সামাজিক নেটওয়ার্কের মতো নয়, এরদোস-রেনি গ্রাফের ক্লাস্টারিং কম। কিছু মডেলিং বিকল্পের মধ্যে রয়েছে বারাবাসি-আলবার্ট মডেল এবং ওয়াটস এবং স্ট্রোগাটজ মডেল। এই বিকল্প মডেলগুলি পারকোলেশন প্রক্রিয়া নয়, বরং যথাক্রমে একটি বৃদ্ধি এবং পুনর্ব্যবহারযোগ্য মডেলের প্রতিনিধিত্ব করে। র্যান্ডম গ্রাফ মডেলের আরেকটি বিকল্প পরিবার, যা অনেক বাস্তব জীবনের ঘটনা পুনরুত্পাদন করতে সক্ষম, তা হল এক্সপোনেনশিয়াল র্যান্ডম গ্রাফ মডেল। জি (এন, পি) মডেলটি প্রথম 1959 সালে এডগার গিলবার্ট একটি গবেষণাপত্রে উপরে উল্লিখিত সংযোগের সীমা অধ্যয়ন করে প্রবর্তন করেছিলেন। জি (এন, এম) মডেলটি এরদোস এবং রেনি তাদের 1959 সালের গবেষণাপত্রে প্রবর্তন করেছিলেন। গিলবার্টের মতো, তাদের প্রথম তদন্তগুলি ছিল জি (এন, এম)-এর সংযোগ সম্পর্কে, 1960 সালে আরও বিস্তারিত বিশ্লেষণ সহ। ক্রিটিক্যাল জি (এন, পি)-এর কন্টিনিউম সীমা উপস্থাপনা গ্রাফের একটি কন্টিনিউম সীমা প্রাপ্ত হয় যখন ক্রমানুসারে থাকে। বিশেষ করে, এর জন্য গ্রাফের ক্রম বিবেচনা করুন। সীমা বস্তুটি নিম্নরূপ তৈরি করা যেতে পারেঃ প্রথমে, একটি বিস্তার তৈরি করুন যেখানে একটি আদর্শ ব্রাউনিয়ান গতি। এই প্রক্রিয়া থেকে আমরা প্রতিফলিত প্রক্রিয়াটিকে সংজ্ঞায়িত করি। এই প্রক্রিয়াটিকে ধারাবাহিকভাবে অনেক ভ্রমণের অন্তর্ভুক্ত হিসাবে দেখা যেতে পারে (বেশ ব্রাউনিয়ান ভ্রমণ নয়, দেখুন)। যেহেতু এর প্রবাহ দ্বারা প্রভাবিত হয়, তাই এই ভ্রমণগুলি ছোট এবং ছোট হয়ে যায়। বিশেষত, এগুলি ক্রমহ্রাসমান দৈর্ঘ্যের ক্রমে সাজানো যেতে পারেঃ আমরা হ্রাসমান দৈর্ঘ্যের বিরতিতে বিভক্ত করতে পারি যা কোনও ব্রাউনীয় ভ্রমণের মধ্যে সীমাবদ্ধ। এখন, একটি ভ্রমণের কথা ভাবুন। নিম্নরূপ একটি এলোমেলো গ্রাফ তৈরি করুনঃ একটি প্রকৃত গাছ তৈরি করুন (ব্রাউনিয়ান গাছ দেখুন)। একক তীব্রতার সঙ্গে একটি পয়সন বিন্দু প্রক্রিয়া বিবেচনা করুন। প্রতিটি বিন্দুতে, একটি অন্তর্নিহিত অভ্যন্তরীণ নোড এবং গাছের একটি পাতার সাথে মিলে যায়। দুটি শীর্ষকে চিহ্নিত করে, গাছটি একটি গ্রাফে পরিণত হয় এই পদ্ধতিটি প্রয়োগ করে, হ্রাসমান আকারের এলোমেলো অসীম গ্রাফের একটি ক্রম পাওয়া যায়ঃ উপপাদ্যটি বলে যে এই গ্রাফটি একটি নির্দিষ্ট অর্থে সীমা বস্তুর সাথে মিলে যায়। আরও দেখুন, জি (এন, পি) মডেলটি গণনাযোগ্যভাবে অসীম সংখ্যক শীর্ষ সহ গ্রাফগুলিতে প্রসারিত করে তৈরি করা গ্রাফ। সীমাবদ্ধ ক্ষেত্রে ভিন্ন, এই অসীম প্রক্রিয়ার ফলাফল হল (সম্ভাব্যতা 1 সহ) সমরূপতা পর্যন্ত একই গ্রাফ। এরদোস-রেনি মডেলের সাথে সম্পর্কিত বৈশিষ্ট্যগুলি সিস্টেমে অর্ডারের উত্থানে অবদান রাখে এমন উপায়গুলি বর্ণনা করে। নেটওয়ার্ক পরিসংখ্যান এবং তাদের সাথে সম্পর্কিত বিভিন্ন পরামিতিগুলির একটি সেট দেওয়া "এন" নোডগুলিতে গ্রাফগুলির একটি সাধারণ সম্ভাব্যতা বিতরণ বর্ণনা করুন। , সুপ্ত সম্প্রদায় কাঠামো সহ গ্রাফের জন্য এরদোস-রেনি মডেলের একটি সাধারণীকরণ তথ্যসূত্র সাহিত্য ওয়েবলিংক ভিডিওঃ এরদোস-রেনি র্যান্ডম গ্রাফ র্যান্ডম গ্রাফ রেনি মডেল