Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products

एक बड़ी तस्वीर: एक विशाल जाल में त्रिभुजों (Triangles) की गिनती

कल्पना कीजिए कि आपके पास एक विशाल सोशल नेटवर्क है, जैसे दोस्तों का एक बहुत बड़ा जाल जहाँ हर कोई कई अन्य लोगों से जुड़ा हुआ है। इस जाल में, एक "त्रिभुज" (triangle) एक बहुत ही विशिष्ट पैटर्न है: व्यक्ति A, व्यक्ति B को जानता है, व्यक्ति B, व्यक्ति C को जानता है, और व्यक्ति C, व्यक्ति A को जानता है।

इन त्रिभुजों की गिनती करना डेटा वैज्ञानिकों के लिए बहुत महत्वपूर्ण है। यह उन्हें यह समझने में मदद करता है कि एक समुदाय कितना घनिष्ठ है, यह अनुमान लगाने में कि आगे कौन दोस्त बन सकता है, या अजीब व्यवहार (जैसे धोखाधड़ी वाले गिरोह) का पता लगाने में।

समस्या:
यदि नेटवर्क छोटा है, तो आप हर त्रिभुज को एक-एक करके गिन सकते हैं। लेकिन यदि नेटवर्क में लाखों लोग हैं, तो उन सभी को गिनना समुद्र तट पर रेत के हर कण को हाथ से गिनने जैसा है। इसमें बहुत अधिक समय और कंप्यूटर पावर लगती है।

त्रिभुजों को गिनने के लिए मानक गणितीय ट्रिक में एक विशाल ग्रिड (जिसे मैट्रिक्स कहा जाता है) शामिल होता है जो पूरे नेटवर्क का प्रतिनिधित्व करता है। उत्तर प्राप्त करने के लिए, आपको आमतौर पर इस ग्रिड को तीन बार खुद से गुणा करना पड़ता है। लेकिन विशाल नेटवर्क के लिए, उस "गुणा किए गए ग्रिड" को बनाना असंभव है क्योंकि इसके लिए दुनिया के सभी कंप्यूटरों के संयुक्त मेमोरी से भी अधिक मेमोरी की आवश्यकता होगी।

पुराना समाधान: "अनुमान लगाने का खेल"

इस समस्या को हल करने के लिए, गणितज्ञ हचिनसन एस्टिमेटर (Hutchinson's Estimator) नामक एक विधि का उपयोग करते हैं। इसे "औसत का अनुमान लगाने" के खेल के रूप में सोचें।

सटीक संख्या की गणना करने के बजाय, आप ग्रिड पर यादृच्छिक (random) डार्ट्स फेंकते हैं। आप कंप्यूटर से पूछते हैं: "यदि मैं इस ग्रिड को इस रैंडम डार्ट से गुणा कर दूँ, तो क्या होगा?" आप यह कई बार करते हैं, अपने परिणामों का औसत लेते हैं, और—जादुई रूप से—वह औसत आपको त्रिभुजों की कुल संख्या का एक बहुत अच्छा अनुमान देता है।

यह तेज़ है क्योंकि आपको वह विशाल गुणा किया गया ग्रिड बनाने की आवश्यकता नहीं है; आपको बस मूल ग्रिड के साथ सरल गुणा करने की आवश्यकता है।

नई समस्या: "स्ट्रैगलर" (धीमा चलने वाला) और "शोर वाला कमरा"

यह शोध पत्र एक विशिष्ट समस्या को संबोधित करता है जो तब होती है जब आप इसे एक विशाल कंप्यूटर सिस्टम पर करने की कोशिश करते हैं जिसमें कई प्रोसेसर मिलकर काम कर रहे होते हैं (जैसे कि एक पहेली सुलझाने वाली लोगों की टीम)।

कल्प_ना कीजिए कि आपके पास एक टीम है जिसमें 100 लोग हैं जो एक "डार्ट थ्रो" के परिणाम की गणना करने की कोशिश कर रहे हैं।

1. बात करने की लागत: अंतिम उत्तर प्राप्त करने के लिए, प्रत्येक व्यक्ति को अपने गणना के हिस्से को सभी अन्य लोगों के साथ साझा करना पड़ता है। एक विशाल नेटवर्क में, यह "बातचीत" (संचार) बहुत समय लेती है और सब कुछ धीमा कर देती है।
2. स्ट्रैगलर (Straggler): कभी-कभी, टीम के एक या दो लोग बाकी लोगों की तुलना में धीमे होते हैं (शायद उनका कंप्यूटर किसी और काम में व्यस्त है)। एक पारंपरिक सेटअप में, पूरी टीम को अगले चरण पर जाने से पहले सबसे धीमे व्यक्ति के पूरा होने का इंतजार करना पड़ता है। इसे "सिंक्रोनाइज़ेशन के लिए प्रतीक्षा करना" कहा जाता है।

लेखकों ने महसूस किया कि हर व्यक्ति के पूरा होने और हर एक नंबर को साझा करने का इंतजार करना समय की बर्बादी है।

नया समाधान: "आंशिक झलक" (Partial Peek)

लेखक इस अनुमान लगाने के खेल को खेलने का एक चतुर नया तरीका प्रस्तावित करते हैं। पूरी टीम के खत्म होने और हर एक नंबर को साझा करने का इंतजार करने के बजाय, वे टीम को केवल एक यादृच्छिक, आंशिक सेट (random, partial set) की झलक लेने और तुरंत आगे बढ़ने की अनुमति देते हैं।

उपमा (Analogy):
कल्पना कीजिए कि आप भीड़ की औसत ऊंचाई का अनुमान लगाने की कोशिश कर रहे हैं।

• पुराना तरीका: आप हर व्यक्ति के वजन करने वाली मशीन पर खड़े होने, अपनी ऊंचाई लिखने और उसे एक केंद्रीय कंप्यूटर को भेजने का इंतजार करते हैं। आप सबसे धीमे व्यक्ति के खत्म होने तक इंतजार करते हैं।
• नया तरीका: आप भीड़ से कहते हैं, "यदि आपको मन हो, और केवल तभी यदि आप एक यादृच्छिक स्थान पर खड़े हैं, तो अपनी ऊंचाई चिल्लाकर बताएं।" आप सभी का इंतजार नहीं करते। आप बस जो आवाजें सुनते हैं उन्हें पकड़ते हैं, एक त्वरित गणना करते हैं, और अगले दौर की ओर बढ़ जाते हैं।

पेपर में, वे इसे "आंशिक अवलोकन" (partial observation) कहते हैं। वे यादृच्छिक रूप से तय करते हैं कि गणना के किन हिस्सों को देखना है और किन को अनदेखा करना है। वे यह भी अनुमति देते हैं कि "धीमे" प्रोसेसर पूरे दल को रोके बिना अपना डेटा बाद में योगदान दे सकें।

उन्होंने क्या सिद्ध किया ( "विज्ञान" वाला हिस्सा)

आप सोच सकते हैं, "यदि मैं डेटा को अनदेखा कर रहा हूँ, तो क्या मेरा उत्तर गलत नहीं होगा?" लेखकों ने तीन चीजें सिद्ध करने के लिए भारी गणित का उपयोग किया:

1. यह अभी भी निष्पक्ष है (Unbiased): भले ही वे पहेली के यादृच्छिक, आंशिक टुकड़ों को देख रहे हैं, उनके अनुमानों का औसत पूरी तरह से सटीक है। वे धोखाधड़ी नहीं कर रहे हैं; वे बस कुशल हो रहे हैं।
2. यह विश्वसनीय है (Variance): उन्होंने गणना की कि उनका उत्तर कितना ऊपर-नीचे हो सकता है। उन्होंने सिद्ध किया कि छूटे हुए डेटा के साथ भी, उत्तर सत्य के करीब रहता है, खासकर यदि आप प्रयोग को पर्याप्त बार चलाते हैं।
3. यह तेज़ है: उन्होंने दिखाया कि "हर किसी के पूरा होने का इंतजार करने" के चरण को छोड़कर, सिस्टम बहुत तेज़ी से चलता है, विशेष रूप से जब कंप्यूटर अलग-अलग स्थानों पर या अलग-अलग गति के होते हैं।

परिणाम: क्या यह काम करता है?

उन्होंने अपने नए तरीके का परीक्षण तीन अलग-अलग प्रकार के नेटवर्क पर किया:

1. वैज्ञानिकों का एक वास्तविक नेटवर्क जिन्होंने मिलकर शोध पत्र लिखे थे।
2. एक बनावटी रैंडम नेटवर्क।
3. हार्वर्ड यूनिवर्सिटी के वेबपेजों का एक नेटवर्क।

उन्होंने अपने "पार्शियल पीक" (Partial Peek) तरीके की तुलना "फुल वेट" (Full Wait) तरीके से की।

• निष्कर्ष: उनके "पार्शियल पीक" तरीके ने पूर्ण विधि के लगभग समान सटीक उत्तर दिया।
• समझौता (Trade-off): यदि वे समय बचाने के लिए कम नंबरों को देखते थे (पीक करते थे), तो उत्तर थोड़ा अधिक "शोर वाला" (कॉन्फिडेंस इंटरवल व्यापक) था, लेकिन फिर भी बहुत अच्छा था।
• जीत: उन्होंने सबसे धीमी प्रणाली के पीछे आने का इंतजार न करके, बहुत सारा समय और कंप्यूटर संसाधन बचाए।

सारांश

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

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