Sample entropy for graph signals: An approach to nonlinear dynamic analysis of data on networks

यहाँ शोध पत्र "Sample entropy for graph signals: An approach to nonlinear dynamic analysis of data on networks" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

जटिल प्रणालियों (जैसे ट्रैफ़िक, वित्तीय बाज़ार, पारिस्थितिकी तंत्र) को तेजी से नेटवर्क (ग्राफ) पर विकसित होने वाले डेटा के रूप में मॉडल किया जा रहा है। जबकि पारंपरिक गैर-रेखीय विश्लेषण तकनीकें जैसे कि परम्यूटेशन एंट्रॉपी (PE) और उसके डेरिवेटिव्स (डिस्पर्शन एंट्रॉपी, बबल एंट्रॉपी) को ग्राफ सिग्नल्स (PEG, DEG, BEG) के लिए सफलतापूर्वक विस्तारित किया गया है, ये विधियाँ मौलिक रूप से शैनन एंट्रॉपी (Shannon entropy) और सिंबल डायनेमिक्स (symbol dynamics) (डेटा को प्रतीकों में विभाजित करना) पर निर्भर करती हैं।

साहित्य में ग्राफ सिग्नल्स के लिए सैंपल एंट्रॉपी (SampEn) को लागू करने के क्षेत्र में एक अंतराल मौजूद है। SampEn निरंतर अवस्था स्थान (continuous state space) में कंडीशनल एंट्रॉपी (conditional entropy) और कोरिलेशन इंटीग्रल्स (correlation integrals) पर आधारित एक व्यापक रूप से उपयोग की जाने वाली, सुदृढ़ माप विधि है। सिंबल-आधारित विधियों के विपरीत, SampEn को प्रतीकात्मक विभाजन (symbolic partitioning) की आवश्यकता नहीं होती है, जो इसे शोर (noise) और लघु समय श्रृंखला (short time series) के प्रति अधिक सुदृढ़ बनाता है। हालाँकि, मनमाने ग्राफ टोपोलॉजी के लिए SampEn को परिभाषित करना गैर-तुच्छ (non-trivial) है क्योंकि:

1. शास्त्रीय SampEn कालानुक्रमिक क्रम (temporal ordering - समय चरणों) पर निर्भर करता है।
2. ग्राफ सिग्नल्स में स्वाभाविक रैखिक समय अनुक्रम का अभाव होता है; वे अनियमित, गैर-यूक्लिडियन डोमेन में मौजूद होते हैं।
3. मौजूदा ग्राफ एंट्रॉपी विधियाँ उस विशिष्ट "कंडीशनल प्रोबेबिलिटी" डायनेमिक्स को कैप्चर नहीं करती हैं जो SampEn प्रदान करता है।

2. कार्यप्रणाली: SampEnG (Methodology: SampEnG)

लेखक SampEnG (Sample Entropy for Graph Signals) प्रस्तावित करते हैं, जो एक एकीकृत ढांचा है जो शास्त्रीय SampEn को मनमाने ग्राफ टोपोलॉजी (निर्देशित/अनिर्देशित, भारित/भारहीन) तक सामान्यीकृत करता है।

मुख्य अवधारणा: टोपोलॉजी-जागरूक एम्बेडिंग्स (Topology-Aware Embeddings)

समय चरणों ($t, t+1, \dots$) का उपयोग करने के बजाय, SampEnG पैटर्न बनाने के लिए ग्राफ हॉप डिस्टेंस (graph hop distance) का उपयोग करता है।

• पैटर्न निर्माण: एक नोड $i$ के लिए, $L$-हॉप पड़ोस ($L=0, 1, \dots, m-1$) से सिग्नल मानों को एकत्रित करके एक $m$-आयामी पैटर्न वेक्टर $x^m_i$ बनाया जाता है।
• वॉक-वेटेड मीन (Walk-Weighted Mean): हॉप $L$ पर मान ($x^L_i$) को $L$-हॉप पड़ोसियों के भारित माध्य (weighted mean) के रूप में गणना किया जाता है। इसकी गणना एडजेसेंसी मैट्रिक्स ($A^L$ या भारित मैट्रिक्स $W^L$) की घातों का उपयोग करके की जाती है:
  $$x^L_i = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$$
  यह प्रभावी रूप से नोड $i$ के चारों ओर सिग्नल के एक "रेडियल प्रोफाइल" (radial profile) का निर्माण करता है, जो समय श्रृंखला में बढ़ते हुए टेम्पोरल स्टेप्स के समान है।
• मैचिंग और कोरिलेशन संकलन (Matching and Correlation Sums):
  1. पैटर्न की तुलना चेबिशेव दूरी (Chebyshev distance) का उपयोग करके की जाती है।
  2. एक मैच तब गिना जाता है जब दो पैटर्न के बीच की दूरी टॉलरेंस थ्रेशोल्ड $\epsilon = r \times \text{SD}$ (जहाँ SD सिग्नल का मानक विचलन है) से कम हो।
  3. एल्गोरिदम कोरिलेशन संकलनों $B_m$ (लंबाई $m$ के पैटर्न के लिए) और $A_m$ (लंबाई $m+1$ के पैटर्न के लिए) की गणना करता है।
  4. SampEnG इन संकलनों के अनुपात के ऋणात्मक प्राकृतिक लघुगणक (negative natural logarithm) के रूप में निकाला जाता है:
     $$\text{SampEnG} = -\ln \left( \frac{A_m}{B_m} \right)$$

सैद्धांतिक न्यूनीकरण (Theoretical Reductions)

• 1D न्यूनीकरण: एक निर्देशित पाथ ग्राफ (directed path graph) पर, SampEnG गणितीय रूप से शास्त्रीय 1D SampEn में बदल जाता है।
• 2D न्यूनीकरण: एक नियमित ग्रिड ग्राफ (8-पड़ोसी) पर, यह छवियों के लिए उपयोग किए जाने वाले 2D SampEn (SampEn2D) के एक स्वाभाविक ग्राफ-आधारित एनालॉग के रूप में कार्य करता है।

3. प्रमुख योगदान (Key Contributions)

1. प्रथम सामान्यीकरण: ग्राफ सिग्नल्स के लिए सैंपल एंट्रॉपी की पहली परिभाषा पेश करता है, जो कंडीशनल-एंट्रॉपी आधारित मापों और ग्राफ सिग्नल प्रोसेसिंग (GSP) के बीच के अंतर को पाटता है।
2. एकीकृत ढांचा: यह एक एकल मीट्रिक प्रदान करता है जो बिना किसी प्रतीकात्मक विवेकीकरण (symbolic discretization) की आवश्यकता के 1D टाइम सीरीज़, 2D इमेज और मनमाने जटिल नेटवर्क पर लागू होता है।
3. टोपोलॉजी जागरूकता: यह स्थानिक निर्भरताओं (spatial dependencies) और नेटवर्क संरचनाओं में निहित कारण प्रवाह (causal flows) को कैप्चर करने के लिए मल्टी-हॉप पड़ोस एकत्रीकरण का उपयोग करता है।
4. सुदृढ़ता (Robustness): लघु डेटा रिकॉर्डिंग और शोर युक्त सिग्नल्स पर प्रभावशीलता प्रदर्शित करता है, जो कि SampEn की एक ज्ञात शक्ति है जिसे ग्राफ डोमेन में भी लाया गया है।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने सिंथेटिक और वास्तविक दुनिया के डेटासेट पर SampEnG को मान्य किया:

• सिंथेटिक 1D (लॉजिस्टिक्स मैप):

  • एक निर्देशित पाथ ग्राफ पर SampEnG ने शास्त्रीय SampEn परिणामों को पूरी तरह से दोहराया, जिससे बाइफरकेशन पॉइंट्स (bifurcation points) और अराजक व्यवस्थाओं (chaotic regimes) की सही पहचान हुई।
  • अननिर्देशित पथों ने समान रुझान दिखाए लेकिन सममित (गैर-कारण) पड़ोस के कारण मात्रात्मक अंतर प्रदर्शित किए।

• सिंथेटिक 2D (इमेज और टेक्सचर):

  • ब्रोडैट टेक्सचर्स (Brodatz Textures): SampEnG ने टेक्सचर्स को अनियमितता के आधार पर सही ढंग से रैंक किया (नियमित टेक्सचर = कम एंट्रॉपी; अनियमित = उच्च एंट्रॉपी), जो SampEn2D के व्यवहार से मेल खाता है।
  • MIX2D प्रोसेस: उच्च शोर (high noise) के तहत, SampEnG संतृप्त (saturated) हो गया और थोड़ा कम हो गया, जबकि परम्यूटेशन एंट्रॉपी (जो बढ़ता रहता है) के विपरीत। इसका कारण $\epsilon$ थ्रॉल्ड है: उच्च-शोर वाले शासन में, मल्टी-हॉप औसत के लो-पास फ़िल्टरिंग प्रभाव के कारण पैटर्न सांख्यिकीय रूप से समान हो जाते हैं, जिससे कंडीशनल अनप्रेडिक्टेबिलिटी कम हो जाती है।

• सिंथेटिक ग्राफ्स (ER और WS नेटवर्क):

  • Erdős–Rényi (ER): SampEnG स्पार्स (sparse) से मध्यम रूप से जुड़े ग्राफों पर सबसे अधिक सूचनात्मक था। बहुत घने ग्राफों में, लंबी दूरी के कनेक्शनों के कारण पड़ोस अत्यधिक ओवरलैप होने लगे, जिससे पैटर्न की विशिष्टता कम हो गई और एंट्रॉपी शून्य की ओर चली गई।
  • Watts-Strogatz (WS): मीट्रिक ने नियमित से रैंडम संरचनाओं के संक्रमण को सफलतापूर्वक पहचाना। इसने स्मूथ शोर और पीसवाइज-कांस्टेंट सिग्नल्स के बीच अंतर किया, हालांकि उच्च रीवायरिंग संभावनाओं ने अंततः सूक्ष्म संरचनात्मक अंतरों को ढक दिया।

• वास्तविक दुनिया के अनुप्रयोग:

  • वेदर स्टेशन्स (Brittany): इसने तापमान गतिकी (temperature dynamics) के लिए दिन के समय (सौर/वायुमंडलीय अंतःक्रियाओं के कारण उच्च जटिलता) और रात के समय (स्थिर, नियमित पैटर्न) के बीच सफलतापूर्वक अंतर किया।
  • वायरलेस सेंसर नेटवर्क (Intel Berkeley): इसने एक छोटे, कम अवधि के डेटासेट ($N=23$, 108 नमूने) पर सक्रिय दिन (उच्च प्रकाश भिन्नता, मानवीय हस्तक्षेप) और शांत रात के अवधियों के बीच अंतर किया, जो लघु रिकॉर्डिंग के प्रति इसकी सुदृढ़ता को दर्शाता है।
  • फ्रीवे ट्रैफ़िक (FT-AED):
    • अपस्ट्रीम/डाउनस्ट्रीम ट्रैफ़िक प्रवाह को एनकोड करने वाले निर्देशित टोपोलॉजी पर लागू किया गया।
    • मुख्य निष्कर्ष: निर्देशित टोपोलॉजी पर SampEnG ने अननिर्देशित SampEnG और डिस्पर्शन एंट्रॉपी (DEG) की तुलना में ट्रैफ़िक कंजेशन (जाम) की शुरुआत का 20 मिनट पहले पता लगाया।
    • SampEnG की निर्देशित और कंडीशनल प्रकृति ने शैनन-एंट्रॉपी आधारित विधियों के पूरक सूचना प्रदान की, जो चरण संक्रमण (phase transitions - फ्री-फ्लो से कंजेशन) के लिए एक प्रारंभिक चेतावनी संकेत (early-warning signal) के रूप में कार्य करती है।

5. महत्व और निष्कर्ष (Significance and Conclusion)

• पूरक परिप्रेक्ष्य: SampEnG मौजूदा शैनन-एंट्रॉपी आधारित ग्राफ मापों (PEG, DEG) की तुलना में एक अलग विश्लेषणात्मक दृष्टिकोण प्रदान करता है। यह ऑर्डिनल सिंबल आवृत्तियों के बजाय निरंतर स्थान में पैटर्न के बने रहने और पुनरावृत्ति पर ध्यान केंद्रित करता है।
• प्रारंभिक चेतावनी प्रणाली (Early Warning Systems): ट्रैफ़िक प्रयोग जटिल गतिशील प्रणालियों में महत्वपूर्ण संक्रमणों (चरण परिवर्तनों) का पता लगाने के लिए SampEnG की उपयोगिता को उजागर करता है, विशेष रूप से जब ग्राफ में कारण दिशात्मकता (causal directionality) एनकोड की गई हो।
• कंप्यूटेशनल व्यवहार्यता: विधि कम्प्यूटेशनल रूप से कुशल है (लगs 1.4 सेकंड में 2,700 नोड्स को प्रोसेस करना), जो इसे बड़े पैमाने पर IoT, सेंसर नेटवर्क और मस्तिष्क कनेक्टिविटी अध्ययनों के लिए उपयुक्त बनाती है।
• सीमाएँ: विधि स्थानीय मल्टी-हॉप पड़ोस की विशिष्टता पर निर्भर करती है। अत्यंत घने ग्राफों या शोर से प्रभावित सिग्नल्स में, औसत लेने की प्रक्रिया पैटर्न को एकसमान (homogenize) बना सकती है, जिससे मीट्रिक की संवेदनशीलता कम हो जाती है।

संक्षेप में, SampEnG नेटवर्क पर डेटा के लिए कंडीशनल एंट्रॉपी की शक्तिशाली अवधारणा का विस्तार करता है, जो जटिल प्रणालियों में गैर-रेखीय गतिकी का विश्लेषण करने के लिए एक सुदृढ़, टोपोलॉजी-जागरूक उपकरण प्रदान करता है जहाँ पारंपरिक टाइम-सीरीज विधियाँ अपर्याप्त हैं।