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

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

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

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

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

<ब्लॉककोट>

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

</ब्लॉककोट>

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

सामान्यीकृत सेलुलर ऑटोमेटा (जीसीए)

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

$F(x)_{v}=f_{v}(x[v])\;.$ इस वर्ग को सामान्यीकृत सेलुलर ऑटोमेटा के रूप में संदर्भित किया जाता है क्योंकि शास्त्रीय या मानक सेलुलर automaton को आमतौर पर नियमित ग्राफ़ या ग्रिड पर परिभाषित और अध्ययन किया जाता है, और वर्टेक्स फ़ंक्शंस को आमतौर पर समान माना जाता है।

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

File:Circ-4-nor.jpg

326

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

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

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

एसडीएस मानचित्र एफ = [एफ_Y, डब्ल्यू] : के^एन → केⁿ फ़ंक्शन संयोजन है

$[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} हैं, जो वृत्त को निरूपित करते हैं₄. चलो K={0,1} प्रत्येक शीर्ष के लिए राज्य स्थान हो और न ही फ़ंक्शन का उपयोग करें₃ : क³ → K नॉर द्वारा परिभाषित है₃(x, y, z) = (1 + x)(1 + y)(1 + z) सभी शीर्ष कार्यों के लिए अंकगणितीय सापेक्ष 2 के साथ। अद्यतन अनुक्रम (1,2,3,4) का उपयोग करके सिस्टम स्थिति (0, 1, 0, 0) को (0, 0, 1, 0) मैप किया जाता है। इस अनुक्रमिक गतिशील प्रणाली के लिए सभी सिस्टम स्थिति संक्रमण नीचे चरण स्थान में दिखाए गए हैं।

File:Circ-4-nor-1234.jpg

326

स्टोकेस्टिक ग्राफ डायनेमिक सिस्टम

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

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

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

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

अनुप्रयोग

ग्राफ़ डायनेमिक सिस्टम सामाजिक नेटवर्क पर जैविक नेटवर्क और महामारी जैसे वितरित सिस्टम को कैप्चर करने के लिए एक प्राकृतिक ढांचा बनाते हैं, जिनमें से कई को अक्सर जटिल सिस्टम के रूप में संदर्भित किया जाता है।

यह भी देखें

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

अग्रिम पठन

• 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