आरेख गतिकीय प्रणाली (जीडीएस)

गणित में, आरेख गतिकीय प्रणाली की अवधारणा का उपयोग आरेख़ या नेटवर्क पर होने वाली प्रक्रियाओं की एक विस्तृत श्रृंखला को कैप्चर करने के लिए किया जा सकता है। जीडीएस के गणितीय और कम्प्यूटेशनल विश्लेषण में एक प्रमुख विषय उनके संरचनात्मक गुणों (जैसे नेटवर्क कनेक्टिविटी) और परिणामी वैश्विक गतिकीयता से संबंधित है।

जीडीएस पर काम परिमित रेखांकन और परिमित अवस्था समष्टि पर विचार करता है। जैसे, अनुसंधान में सामान्यतः तकनीकों को सम्मिलित किया जाता है, उदाहरण के लिए, अंतर ज्यामिति के बजाय आरेख सिद्धांत, साहचर्य, बीजगणित और गतिकीय प्रणालियां सिद्धांत रूप में, एक अनंत आरेख पर जीडीएस को परिभाषित और अध्ययन कर सकता है उदाहरण के लिए $\mathbb {Z} ^{k}$ पर कोशिकीय रोबोट या संभाव्य कोशिकीय रोबोट या कुछ यादृच्छिकता सम्मिलित होने पर कण प्रणालियों को अन्योन्यक्रिया के साथ ही अनंत के जीडीएस अवस्था समष्टि (जैसे $\mathbb {R}$ कपल मैप लैटिस के रूप में) देखें, उदाहरण के लिए निम्नलिखित में, जब तक अन्यथा न कहा जाए, सब कुछ निहित रूप से परिमित माना जाता है।

औपचारिक परिभाषा

निम्नलिखित घटकों से एक आरेख गतिकीय प्रणाली का निर्माण किया जाता है:

• लंबकोणीय समुच्चय v[Y] = {1,2, ... , n} के साथ एक परिमित आरेख Y। संदर्भ के आधार पर आरेख को निर्देशित या अप्रत्यक्ष किया जा सकता है।
• एक परिमित समुच्चय K से लिए गए Y के प्रत्येक शीर्ष v के लिए एक स्थिति xv प्रणाली स्थिति n-tuple x = (x₁, x₂, ... , x_n) है, और x[v] अवस्थाओं से युक्त टपल है Y (कुछ निश्चित क्रम में) में v के 1-पड़ोस में कोने से जुड़ा हुआ है।
• प्रत्येक लंबकोणीय v के लिए एक लंबकोणीय फलन f_v लंबकोणीय फलन वाई में v के 1-पड़ोस से जुड़े अवस्थाओं के आधार पर समय t + 1 पर लंबकोणीय अवस्था पर लंबकोणीय वी की स्थिति को मैप करता है।
• एक अद्यतन योजना उस तंत्र को निर्दिष्ट करती है जिसके द्वारा अलग-अलग शीर्ष अवस्थाओं की मैपिंग की जाती है ताकि मानचित्र F: Kn → Kn के साथ एक असतत गतिकीय प्रणाली को प्रेरित किया जा सके।.

मानचित्र F: Kⁿ → Kⁿ के साथ एक गतिकीय प्रणाली से जुड़ा चरण समष्टि शीर्ष समुच्चय Kn और निर्देशित किनारों (x, F (x)) के साथ परिमित निर्देशित आरेख है। चरण समष्टि की संरचना आरेख वाई, लंबकोणीय फलन (f_i)_i और अद्यतन योजना के गुणों द्वारा नियंत्रित होती है। इस क्षेत्र में अनुसंधान प्रणाली घटकों की संरचना के आधार पर चरण समष्टि गुणों का अनुमान लगाना चाहता है। विश्लेषण में एक समष्टिीय-से-वैश्विक चरित्र है।

सामान्यीकृत कोशिकीय रोबोट (जीसीए)

यदि, उदाहरण के लिए, अद्यतन योजना में लंबकोणीय फलन को समकालिक रूप से प्रयुक्त करना सम्मिलित है, तो सामान्यीकृत कोशिकीय रोबोट (सीए) की श्रेणी प्राप्त होती है। इस स्थिति में, वैश्विक मानचित्र F: Kⁿ → Kⁿ द्वारा दिया गया है

$F(x)_{v}=f_{v}(x[v])\;$

जीसीए

इस वर्ग को सामान्यीकृत कोशिकीय रोबोट के रूप में संदर्भित किया जाता है क्योंकि शास्त्रीय या मानक कोशिकीय रोबोट को सामान्यतः नियमित आरेख या ग्रिड पर परिभाषित और अध्ययन किया जाता है, और शीर्ष कार्यों को सामान्यतः समान माना जाता है।

उदाहरण: मान लें कि Y कोने {1,2,3,4} पर सर्कल आरेख है, किनारों {1,2}, {2,3}, {3,4} और {1,4} के साथ, सर्किल 4 को दर्शाता है। चलो K = {0,1} प्रत्येक शीर्ष के लिए अवस्था समष्टि बनें और फलन का उपयोग करें nor₃ : K³ → K को nor₃(x,y,z) = (1 + x)(1 + y)(1 + z) द्वारा परिभाषित किया गया है। सभी लंबकोणीय फलनों के लिए अंकगणित मॉड्यूलो 2 के साथ। फिर उदाहरण के लिए प्रणाली स्थिति (0,1,0,0) को सिंक्रोनस अपडेट का उपयोग करके (0, 0, 0, 1) मैप किया जाता है। सभी संक्रमण नीचे चरण समष्टि में दिखाए गए हैं।

अनुक्रमिक गतिकीय प्रणाली (एसडीएस)

यदि लंबकोणीय फलन अतुल्यकालिक रूप से एक शब्द w = (w1, w2, ..., wm) या क्रमचय { $\pi$ = ( $\pi _{1}$, $\pi _{2},\dots ,\pi _{n}$ द्वारा निर्दिष्ट अनुक्रम में प्रयुक्त होते हैं, तो v[Y] एक प्राप्त करता है अनुक्रमिक गतिकीय प्रणालियों (एसडीएस) का वर्ग इस स्थिति में लंबकोणीय फलन से निर्मित वाई-लोकल मैप्स फाई को प्रस्तुत करना सुविधाजनक है

$F_{i}(x)=(x_{1},x_{2},\ldots ,x_{i-1},f_{i}(x[i]),x_{i+1},\ldots ,x_{n})\;$

एसडीएस मानचित्र F = [F_Y , w] : Kⁿ → Kⁿ फलन संयोजन है:$[F_{Y},w]=F_{w(m)}\circ F_{w(m-1)}\circ \cdots \circ F_{w(2)}\circ F_{w(1)}\;$यदि अद्यतन अनुक्रम एक क्रमचय है तो इस बिंदु पर जोर देने के लिए प्रायः एक क्रमचय एसडीएस की बात की जाती है।

उदाहरण: मान लें कि Y शीर्षों {1,2,3,4} पर वृत्त का आरेख़ है, जिसके शीर्ष {1,2}, {2,3}, {3,4} और {1,4} हैं, जो वृत्त4 द्वारा दर्शाए गए हैं। माना कि K={0,1} प्रत्येक शीर्ष के लिए अवस्था समष्टि हो और फलन का उपयोग करें nor₃ : K³ → K को nor₃(x,y,z) = (1 + x)(1 + y)(1 + z) द्वारा परिभाषित किया गया है। सभी लंबकोणीय फलनों के लिए अंकगणित मॉड्यूलो 2 के साथ अद्यतन अनुक्रम (1,2,3,4) का उपयोग करके प्रणाली स्थिति (0, 1, 0, 0) को (0, 0, 1, 0) पर मैप किया जाता है। इस अनुक्रमिक गतिकीय प्रणाली के लिए सभी प्रणाली स्थिति संक्रमण नीचे चरण समष्टि में दिखाए गए हैं।

प्रसंभाव्य आरेख गतिकीय प्रणाली

उदाहरण के लिए, अनुप्रयोगों के दृष्टिकोण से उस स्थिति पर विचार करना दिलचस्प है जहां जीडीएस के एक या अधिक घटकों में प्रसंभाव्य तत्व होते हैं। प्रेरक अनुप्रयोगों में ऐसी प्रक्रियाएं सम्मिलित हो सकती हैं जो पूर्ण रूप से समझ में नहीं आती हैं (उदाहरण के लिए एक सेल के भीतर गतिकीयता) और जहां सभी व्यावहारिक उद्देश्यों के लिए कुछ पहलुओं को कुछ संभाव्यता वितरण के अनुसार व्यवहार करना प्रतीत होता है। नियतात्मक सिद्धांतों द्वारा शासित अनुप्रयोग भी हैं जिनका विवरण इतना जटिल या बोझिल है कि संभाव्य अनुमानों पर विचार करना समझ में आता है।

आरेख़ गतिकीय प्रणाली के प्रत्येक तत्व को कई तरह से प्रसंभाव्य बनाया जा सकता है। उदाहरण के लिए, अनुक्रमिक गतिकीय प्रणाली में अद्यतन अनुक्रम को स्टोकास्टिक बनाया जा सकता है। प्रत्येक पुनरावृति चरण में संबंधित संभावनाओं के साथ अद्यतन अनुक्रमों के दिए गए वितरण से यादृच्छिक रूप से अद्यतन अनुक्रम w चुन सकते हैं। अद्यतन अनुक्रमों का मिलान प्रायिकता समष्टि एसडीएस मानचित्रों के प्रायिकता समष्टि को प्रेरित करता है। इस संबंध में अध्ययन करने के लिए एक प्राकृतिक वस्तु एसडीएस मानचित्रों के इस संग्रह से प्रेरित अवस्था अंतरिक्ष पर मार्कोव श्रृंखला है। इस स्थिति को अद्यतन अनुक्रम प्रसंभाव्य जीडीएस के रूप में संदर्भित किया जाता है और उदा। प्रक्रियाएं जहां "घटनाएं" निश्चित दरों के अनुसार यादृच्छिक रूप से घटित होती हैं (जैसे रासायनिक प्रतिक्रियाएं) समांतर संगणना/असतत घटना सिमुलेशन में और बाद में वर्णित कम्प्यूटेशनल प्रतिमानों में तुल्यकालन स्टोचैस्टिक अपडेट सीक्वेंस वाला यह विशिष्ट उदाहरण ऐसी प्रणालियों के लिए दो सामान्य तथ्यों को दिखाता है: स्टोचैस्टिक आरेख गतिकीय प्रणाली से गुजरने पर सामान्यतः (1) मार्कोव चेन (जीडीएस के घटकों द्वारा शासित विशिष्ट संरचना के साथ) का अध्ययन किया जाता है, और (2) परिणामी मार्कोव श्रृंखला अवस्थाओं की एक घातीय संख्या के साथ बड़ी होती है। स्टोचैस्टिक जीडीएस के अध्ययन में एक केंद्रीय लक्ष्य कम मॉडल प्राप्त करने में सक्षम होना है।

कोई उस स्थिति पर भी विचार कर सकता है जहां लंबकोणीय फलन प्रसंभाव्य फलन हैं अर्थात, प्रसंभाव्य जीडीएस फलन उदाहरण के लिए, रैंडम लियन नेटवर्क एक सिंक्रोनस अपडेट स्कीम का उपयोग करते हुए फलन प्रसंभाव्य जीडीएस के उदाहरण हैं और जहां अवस्था समष्टि K = {0, 1} है। परिमित संभाव्य कोशिकीय रोबोट (पीसीए फलन प्रसंभाव्य जीडीएस का एक और उदाहरण है। सिद्धांत रूप में अंतःक्रियात्मक कण प्रणाली (आईपीएस) की श्रेणी परिमित और अनंत पीसीए को आच्छादन करती है लेकिन व्यवहार में आईपीएस पर काम काफी हद तक अनंत स्थिति से संबंधित है क्योंकि यह अवस्था अंतरिक्ष पर अधिक दिलचस्प टोपोलॉजी प्रस्तुत करने की स्वीकृति देता है।

अनुप्रयोग

आरेख़ गतिकीय प्रणाली सामाजिक नेटवर्क पर जैविक नेटवर्क और महामारी जैसे वितरित प्रणाली को कैप्चर करने के लिए एक प्राकृतिक संरचना बनाते हैं जिनमें से कई को प्रायः जटिल प्रणाली के रूप में संदर्भित किया जाता है।

यह भी देखें

• रासायनिक प्रतिक्रिया नेटवर्क सिद्धांत
• गतिकीय नेटवर्क विश्लेषण (सामाजिक विज्ञान)
• परिमित अवस्था मशीनें
• हॉपफील्ड नेटवर्क
• कॉफ़मैन नेटवर्क
• पेट्री जाल

अग्रिम पठन

• Macauley, Matthew; Mortveit, Henning S. (2009). "Cycle equivalence of graph dynamical systems". Nonlinearity. 22 (2): 421–436. arXiv:0802.4412. Bibcode:2009Nonli..22..421M. doi:10.1088/0951-7715/22/2/010. S2CID 17978550.
• Golubitsky, Martin; Stewart, Ian (2003). The Symmetry Perspective. Basel: Birkhauser. ISBN 0-8176-2171-7.

बाहरी संबंध

• Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit