सबसे छोटे के लिए बड़े रेखांकन का दृश्य

यदि आपको ग्राफ खींचने की आवश्यकता है, तो आपको क्या करना चाहिए, लेकिन आपके हाथ के नीचे आने वाले उपकरण बालों की एक प्रकार की गांठ खींचते हैं या यहां तक ​​कि सभी रैम को खा जाते हैं और सिस्टम को लटका देते हैं? पिछले कुछ वर्षों में बड़े रेखांकन (कोने और किनारों के सैकड़ों) के साथ काम करने के दौरान, मैंने कई उपकरण और दृष्टिकोण आजमाए, और लगभग अच्छी समीक्षा नहीं मिली। इसलिए, अब मैं खुद इस तरह की समीक्षा लिख ​​रहा हूं।

ग्राफ़ की कल्पना क्यों करें?

जो ढूंढना है वो पा लो

इनपुट पर, हमारे पास आमतौर पर केवल कोने और किनारों का एक सेट होता है, जो अनिवार्य रूप से एक ग्राफ है। हम कुछ सांख्यिकीय विशेषताओं, ग्राफ़ मेट्रिक्स की गणना कर सकते हैं, लेकिन यह आपको स्पष्ट तस्वीर नहीं देगा कि यह क्या है। एक अच्छा दृश्य दिखा सकता है कि क्या क्लस्टर में पुल या पुल हैं, या यह सजातीय है, या शायद यह एक गांठ में आकर्षण के किसी मुख्य केंद्र में विलीन हो जाता है।

के बारे में घमंड

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

संकेत प्राप्त करें

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

बड़े रेखांकन के साथ समस्या क्या है?

बड़े रेखांकन से मेरा मतलब आयाम होगा, कहते हैं, 10 हजार कोने या किनारों से शुरू होता है। छोटे आकारों के लिए, आमतौर पर कोई समस्या नहीं होती है, क्योंकि लगभग सभी उपकरण जो इंटरनेट पर त्वरित खोज से मिल सकते हैं मूल रूप से ऐसे संस्करणों के लिए उनकी समस्याओं को अच्छी तरह से हल करते हैं। बड़े रेखांकन में क्या गलत है? दो समस्याएं: यह पठनीयता और गति है। यह उम्मीद की जाती है कि अधिक वस्तुओं, उन्हें नेविगेट करना जितना मुश्किल होगा। बड़े रेखांकन के लिए, चित्र अक्सर प्राप्त किए जाते हैं जिन्हें समझना असंभव है। इसके अलावा, ग्राफ़ एल्गोरिदम आम तौर पर बहुत धीमा होता है, कई में वर्टिकल और (या किनारों) की संख्या के वर्ग (कभी-कभी क्यूब) के लिए आनुपातिक जटिलता होती है। यहां तक ​​कि अगर आप प्रतिपादन के लिए प्रतीक्षा करते हैं, तो भी आप संतोषजनक परिणाम प्राप्त करने के लिए कई विकल्पों से गुजरना नहीं कर सकते।

विभिन्न स्मार्ट लोग इस बारे में क्या लिखते हैं?

ऐसे कुछ काम हैं जिन पर मैं ध्यान आकर्षित करना चाहूंगा:
[१] हेलेन गिब्सन, जो फेथ और पॉल विकर्स: "सूचना दृश्य के लिए दो आयामी ग्राफ लेआउट तकनीकों का एक सर्वेक्षण"
लोग पहले छांटते हैं कि ड्रॉइंग ग्राफ़ में क्या दृष्टिकोण हैं, काम के सिद्धांतों की व्याख्या करें, और फिर उन सभी को आज़माने की कोशिश करें। विभिन्न एल्गोरिदम के बारे में जानकारी के साथ एक बहुत विस्तृत तालिका है, जिसमें उनकी एल्गोरिदमिक जटिलता शामिल है।

[२] ओह-ह्यून क्वोन, तारिक क्रोनोवरसन और क्वान-लियू मा "इस लेआउट में एक ग्राफ कैसा दिखेगा? एक मशीन सीखना बड़े ग्राफ़ विज़ुअलाइज़ेशन के लिए दृष्टिकोण "

यहां, हमारे कामरेड बहुत भ्रमित हो गए और उन्हें ग्राफ़ विज़ुअलाइज़ेशन एल्गोरिदम के सभी कार्यान्वयन प्राप्त हुए जो वे कर सकते थे। तब उन्होंने कई ग्राफ़ की कल्पना की और मार्कअप के लिए मार्कर दिए। परिणामों के अनुसार, हमने मॉडल को यह मूल्यांकन करने के लिए सिखाया कि ग्राफ़ अलग स्टाइलिंग विकल्पों में कैसा दिखेगा। मैंने इस लेख से कुछ तस्वीरें लीं।

सिद्धांत

स्टैकिंग एक तरीका है जो ग्राफ के प्रत्येक शीर्ष पर निर्देशांक को मैप करता है। आमतौर पर हम एक विमान पर निर्देशांक के बारे में बात कर रहे हैं, हालांकि आम तौर पर बोलना एक विमान होना नहीं है। बस 2 से अधिक आयामों का उपयोग करना लगभग आवश्यक नहीं है।

अच्छा स्टाइल क्या है?

यह कहना बहुत आसान है कि कुछ अच्छा या बुरा दिखता है, लेकिन मशीन को यह समझाना मुश्किल है कि इस तरह का आकलन कैसे दिया जाए। एक "अच्छा" स्टाइल बनाने के लिए, तथाकथित "सौंदर्यवादी" मैट्रिक्स को आमतौर पर अनुकूलित किया जाता है, जिसे अधिक निष्पक्ष रूप से तैयार किया जाता है। यहाँ उनमें से कुछ हैं:

न्यूनतम रिब क्रॉसिंग
यह सरल है: जब कई चौराहे होते हैं, तो यह "दलिया" निकलता है, जब यह पर्याप्त नहीं होता है, तो चित्र "क्लीनर" दिखता है

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

समुदायों का टकराव होता है
यह पिछले पैराग्राफ से इस प्रकार है। यदि ऐसे कई नोड्स हैं जो बाकी ग्राफ़ के साथ एक-दूसरे के साथ अधिक जुड़े हुए हैं, तो वे एक "समुदाय" बनाते हैं और चित्र में एक घने क्लस्टर की तरह दिखना चाहिए

कोने और किनारों की न्यूनतम ओवरले
बहुत स्पष्ट है। यदि हम एक वस्तु या यहाँ कई नहीं बना सकते हैं, तो दृश्य खराब पढ़ा जाता है।

समान रूप से कोने और / या किनारों को वितरित करें
यह स्थिति उपयोगी है यदि ग्राफ़ के गुण कम से कम कुछ संरचना को बाहर करने की अनुमति नहीं देते हैं। उदाहरण के लिए, यदि हमारे पास पूरा ग्राफ है - यह एक घने क्लस्टर है, तो इसे कम से कम कनेक्शनों की असमानता को देखने के लिए इसे एक ठोस स्थान में विलय करने की अनुमति देने के लिए तस्वीर में इसे सुलगाना बेहतर है।

स्टाइल क्या हैं?

मैं इन तीन प्रकार की स्टाइलिंग पर विचार करना महत्वपूर्ण मानता हूं, हालांकि बहुत सारे वर्गीकरण और प्रकार हैं। हालांकि, इन प्रकारों का ज्ञान विषय को नेविगेट करने के लिए पर्याप्त है।

• बल-निर्देशित और ऊर्जा-आधारित
• आयाम में कमी
• नोड सुविधाएँ

बल-निर्देशित और ऊर्जा-आधारित

ये विधियाँ शारीरिक शक्ति के अनुकरण का उपयोग करती हैं। चोटियों को आवेशित कणों के रूप में दर्शाया जाता है जो एक-दूसरे को और किनारों को फटकारते हैं - लोचदार तारों के रूप में जो आसन्न चोटियों को एक साथ खींचते हैं। फिर, एक स्थिर स्थिति स्थापित होने तक इस तरह की प्रणाली में कोने की आवाजाही नकली है। अन्य दृष्टिकोण इस तरह की प्रणाली की संभावित ऊर्जा का वर्णन करने की कोशिश करते हैं और ऊर्ध्वाधर की स्थिति पाते हैं जो न्यूनतम के अनुरूप होगा।

चित्र के रूप में एल्गोरिदम के इस परिवार के फायदे। आमतौर पर वास्तव में अच्छी स्टाइल प्राप्त की जाती है जो ग्राफ की टोपोलॉजी को दर्शाती है। कॉन्फ़िगर किए जाने की आवश्यकता वाले पैरामीटर के बीच में। ठीक है, ज़ाहिर है, कम्प्यूटेशनल जटिलता। प्रत्येक शीर्ष के लिए, आपको अन्य सभी शीर्षों से अभिनय करने वाले बलों की गणना करने की आवश्यकता है।

महत्वपूर्ण पारिवारिक एल्गोरिदम फोर्स एटलस, फ्रूचरमैन-रीइंगोल्ड, कामदा कवाई और ओपनऑर्ड हैं। अंतिम एल्गोरिथ्म ट्रिकी ऑप्टिमाइज़ेशन का उपयोग करता है, उदाहरण के लिए, गणना को गति देने के लिए लंबे किनारों को काटता है, और एक साइड इफेक्ट के रूप में, पास की चोटियों के अधिक घने क्लस्टर प्राप्त होते हैं।

आयाम में कमी

ग्राफ को आसन्न मैट्रिक्स द्वारा परिभाषित किया जा सकता है, जो कि वर्ग मैट्रिक्स NxN द्वारा होता है, जहां N, संख्याओं की संख्या है। यह आयाम एन के एक स्थान में एन वस्तुओं के रूप में व्याख्या की जा सकती है। यह प्रतिनिधित्व आयाम को कम करने के सार्वभौमिक तरीकों का उपयोग करने की अनुमति देता है, जैसे कि tSNE, UMAP, PCA, और इसी तरह। एक अन्य दृष्टिकोण किनारों के भार के आधार पर और स्थानीय टोपोलॉजी के ज्ञान के आधार पर कोने के बीच सैद्धांतिक दूरी की गणना पर आधारित है, और फिर छोटे आयामों के रिक्त स्थान में स्थानांतरित होने पर इन दूरी के बीच संबंध बनाए रखने की कोशिश कर रहा है।

फ़ीचर-आधारित लेआउट

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

बड़े ग्राफ विज़ुअलाइज़ेशन उपकरण

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

Graphviz

बिटकॉइन ब्लॉकचेन के लेनदेन और पते 2011 तक


सेटिंग्स को कॉन्फ़िगर करना मुश्किल हो सकता है

एक पुराना-स्कूल सीएलआई उपकरण जिसकी अपनी ग्राफ वर्णन भाषा है - डॉट। वास्तव में, यह किसी भी अवसर के लिए अलग स्टाइल के साथ एक पैकेज है। बड़े रेखांकन के लिए, एक sfdp टूल है - यह स्टैकिंग के फोर्स डायरेक्टेड क्लास के अंतर्गत आता है। कमांड लाइन से लॉन्च करने में इस टूल के फायदे और नुकसान। यह प्रतिलिपि प्रस्तुत करने योग्य और स्वचालन के लिए बहुत सुविधाजनक है, हालांकि, स्लाइडर्स के बिना और मध्यवर्ती परिणाम प्रदर्शित करने के लिए, पैरामीटर सेट करना बहुत दर्दनाक हो जाता है। हम पैरामीटर सेट करते हैं, शुरू करते हैं, प्रगति पट्टी के बिना प्रतीक्षा करते हैं, परिणाम देखते हैं, पैरामीटर बदलते हैं, पुनरारंभ करते हैं। Svg, png और अन्य चित्र प्रारूपों में लिखने में सक्षम।

Gephi

IMDB के साथ 173 हजार फिल्मों की सिफारिशें


कई मिलियन चोटियाँ पहले से ही बहुत कठिन हैं

शायद इसकी संपूर्णता में सबसे शक्तिशाली उपकरण। यह एक GUI एप्लिकेशन है जिसमें मूल स्टाइलिंग के साथ-साथ कई अन्य ग्राफ विश्लेषण उपकरण शामिल हैं। गेफेई समुदाय ने कई प्लगइन्स लिखे हैं, जैसे कि मेरा पसंदीदा मल्टीगैविटी फोर्स-एटलस 2 या एक इंटरैक्टिव वेब पेज पर स्टाइल निर्यात करने के लिए एक प्लगइन। इसके अलावा, मूल OpenOrd कार्यान्वयन Gephi में निहित है। गेफी के पास अपने गुणों के अनुसार कोने और किनारों को पेंट करने के लिए उपकरण हैं, कैप्शन, आकार और अन्य रेंडरिंग विकल्प हैं। वेक्टर सहित मुख्य छवि प्रारूपों के लिए एक निर्यात है।

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

igraph

लास्ट में म्यूजिक रिकमेंडेशन ग्राफ स्रोत यहाँ है ।

ग्राफ विश्लेषण के लिए इस सामान्य प्रयोजन पैकेज के लिए कोई श्रद्धांजलि नहीं दे सकता है। अपने समय के सबसे शानदार ग्राफ विज़ुअलाइज़ेशन में से एक igraph के लेखकों में से एक द्वारा बनाया गया था। उन्होंने इसके लिए अपनी DrL स्टाइल विकसित की। यह लास्ट बैंड की सिफारिशों का एक ग्राफ था। परिणाम अधिक है।

नुकसान में घृणित दस्तावेज शामिल हैं। कम से कम अजगर आपी को। स्रोत को तुरंत पढ़ना आसान है।

LargeViz

बिटकॉइन ब्लॉकचेन के सबसे बड़े समूहों में से कई दसियों लाख चोटियां (लेनदेन और पते)

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

Graphistry

एक सप्ताह में हैक करने योग्य पते, और उनके लेनदेन


स्पष्ट, लेकिन बहुत सीमित इंटरफ़ेस, उचित डिफ़ॉल्ट सेटिंग्स

इस सूची में एकमात्र वाणिज्यिक उपकरण। ग्राफिस्टिक एक ऐसी सेवा है जो आपके डेटा को लेती है और उसकी तरफ भारी गणना करती है। क्लाइंट सिर्फ ब्राउज़र में सुंदर तस्वीर को देखता है। वास्तव में, gephi उचित डिफ़ॉल्ट विकल्पों और अन्तरक्रियाशीलता से बेहतर नहीं है। यह केवल एक स्टाइल को लागू करता है: ForceAtlas के समान। अधिकतम कोने या किनारों के लिए 800 हजार की सीमा है।

ग्राफ एम्बेडिंग

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

Node2Vec

Node2Vec + UMAP

रेखांकन के लिए नियमित word2vec को अपनाना। शब्दों के अनुक्रम के बजाय, रेखांकन के क्रम को ग्राफ के यादृच्छिक ट्रैवर्सल के लिए लिया जाता है और शब्दों के बजाय word2vec पर भेजा जाता है। विधि केवल खाते के पड़ोस के बारे में जानकारी को ध्यान में रखती है। यह आमतौर पर पर्याप्त है।

कविता

VERSE + UMAP

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

ग्राफ का हल

ग्राफ कॉन्फोल्यूशन + ऑटोएन्कोडर

रेखांकन पर कनवल्शन ऑपरेशन को निर्धारित करने के कई तरीके हैं, लेकिन संक्षेप में यह ग्राफ पर जानकारी का "स्मीयरिंग" है, ताकि कोने अपने पड़ोसियों के संकेतों के बारे में जानकारी प्राप्त करें। आप इन विशेषताओं में स्थानीय टोपोलॉजी जानकारी जोड़ सकते हैं।

बोनस: ग्राफ़ कनवल्शन के बारे में थोड़ा और

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

ग्राफ़ और अन्य गैर-यूक्लिडियन डेटा पर दृढ़ संकल्प का एक विस्तृत विश्लेषण एक अलग लेख के योग्य विषय है। यहां मैं सबसे सरल बुनियादी दृष्टिकोण का वर्णन करूंगा, जिसे विशेष ग्राफ फ्रेमवर्क की आवश्यकता नहीं है और आसानी से स्केलेबल है। इसलिए, हम चाहते हैं कि ग्राफ़ के प्रत्येक शीर्ष के निशान पड़ोसी के संकेतों के बारे में जानकारी रखें।

हम यह कैसे करते हैं?

सबसे स्पष्ट तरीका केवल पड़ोसियों का औसत लेना है। यदि आप थोड़ा और सोचते हैं कि क्या होता है और क्या जानकारी खो देता है, तो आप वहां अन्य आँकड़े जोड़ सकते हैं, जैसे कि मानक विचलन, न्यूनतम, अधिकतम, और इसी तरह।

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

ग्राफ विश्लेषण में तालिका के ढांचे की शक्ति

हम इस निष्कर्ष पर पहुंचे हैं कि हमारे पास एक ग्राफ निर्दिष्ट करने वाली प्लेट है और हमें कुछ मात्राओं के लिए आंकड़े पढ़ने की आवश्यकता है। तालिकाओं और आँकड़े - यह सब पांडा में है, इसलिए इसमें निम्नलिखित कार्यान्वयन का एक उदाहरण होगा।

शुरू करने के लिए, हमें ग्राफ सेट करना है:

ara = np.arange(101).reshape(-1, 1) sample = np.vstack((np.hstack((ara[:-1], ara[1:])), # forward links np.hstack((ara[1:], ara[:-1])))) # backward links 

यह आंकड़ा के रूप में एक के बाद एक जुड़े 101 खांचों की एक श्रृंखला है।



फिर हम बेतरतीब ढंग से कोने के संकेत सेट करते हैं:

 feats = np.random.normal(size=(101, 10)) 

और हम इस सब से पांडा डेटाफ्रेम बनाएंगे:

 edges = pd.DataFrame(sample, columns=['source', 'target']) cols = ['col{}'.format(i) for i in range(10)] feats = pd.DataFrame(feats, columns=cols) feats['target'] = ara 

अब हम खुद को कनवल्शन फंक्शन सेट करते हैं:

 def make_conv(edges, feats, cols, by, on, size=1000000, agg_f='mean', prefix='mean_'): """ edges -- edgelist: pandas dataframe with two columns (arguments by and on) feats -- features dataframe with key column (argument on) and features columns (argument cols) by -- column in edges to be used as source nodes on -- column in edges to be used as neighbor nodes size -- number of unique source nodes to be used in one chunk agg_f -- can be interpreted as pooling function. Pandas has several optimised functions for basic statistics, that can be passed as string arg (see pandas docs), but you also can provide any function you like prefix -- prefix for new column names """ res_feats = [] # used to stack result chunks # get chunk of unique source nodes for chunk in tqdm(chunker(edges[by].unique(), size=size), total=(len(edges[by].unique()) // size) + 1): # for each chunk we get feature matrix for neighbours temp = edges[edges[by].isin(chunk)]\ .merge(feats, on=on, how='left') # convolve and pool tempgb = temp[cols + [by, on]]\ .groupby(by).agg({col: agg_f for col in cols}).reset_index() res_feats.append(tempgb.rename(columns={c: prefix + c for c in cols})) # concat results return pd.concat(res_feats, axis=0).reset_index(drop=True) 

यहाँ क्या हो रहा है

सबसे पहले, हम एक कोने का टुकड़ा चुनते हैं, जिसके लिए हम एक दृढ़ संकल्प करेंगे, उनके सभी किनारों को ले जाएंगे, इसे पड़ोसियों के संकेतों के साथ संक्षिप्त करेंगे और इसे अस्थायी डेटा फ़्रेम पर लिखेंगे। फिर हम सूत्रों के कोने द्वारा समूह बनाते हैं, और फ़ंक्शन agg_f का उपयोग करके एकत्र करते हैं, जो कि डिफ़ॉल्ट रूप से औसत है। वर्तमान टुकड़े के लिए परिणाम सूची में जोड़ें, और अंत में परिणामों को संक्षिप्त करें।


इस ग्राफ के लिए, यह इस तरह दिखेगा


हम फ़ंक्शन लागू करते हैं और परिणाम आकर्षित करते हैं:

 conv1 = make_conv(edges, feats, cols, 'source', 'target') plt.figure(figsize=(3, 8)) plt.imshow(np.hstack((feats[cols].values, conv1.values[:, 1:])), cmap='jet'); 

प्रारंभिक संकेत, फिर मूल और पहले कनवल्शन का परिणाम, फिर मूल और दो संकल्‍पों का परिणाम।


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

अगर आप थोड़ा और गणित चाहते हैं

यदि आपने पहले ग्राफ़ के दृढ़ संकल्पों के बारे में सुना है, तो सबसे अधिक संभावना यह है कि यह ग्राफ कन्वेंशन नेटवर्क (ग्राफ संवादी नेटवर्क - जीसीएन) के संदर्भ में था। कुछ के लिए, यहां बताई गई गोलियों के साथ चाल "कठिन नहीं" लग सकता है। वास्तव में, एक बहुत ही दिलचस्प लेख गहरी शिक्षा के बिना ग्राफ़ के संकल्पों के उपयोग के लिए समर्पित है: "ग्राफ़ को सरल बनाना नेटवर्क"। यह इस तरह की परिभाषा देता है $$$H ^ {(k)} \ leftarrow SH ^ {(k - 1)}$जहाँ $$$ज$सुविधाओं का एक मैट्रिक्स है, और $$$एस$ग्राफ का सामान्यीकृत लाप्लासियन है, जिसे इस तरह परिभाषित किया गया है: $$$S = \ tilde {D} ^ {- \ frac {1} {2}} \ tilde {A} \ tilde {D} ^ {\ frac {1} {2}}$यहां $$$\ tilde {A}$क्या पहचान मैट्रिक्स के साथ ग्राफ के आसन्न मैट्रिक्स है, और $$$\ tilde {D}$- विकर्ण में मैट्रिक्स, जिसमें ग्राफ के कोने की डिग्री दर्ज की जाती है। और यह सब स्काइप और सुपी का उपयोग करते हुए अजगर में कुछ पंक्तियों में लिखा गया है:

 S = sparse.csgraph.laplacian(adj, normed=True) feats_conv = S @ feats 

यहाँ, स्पार्स विरल मैट्रेसिस के साथ काम करने के लिए घबराहट के अंदर का मॉड्यूल है, adj आसन्न मैट्रिक्स है, और सजा से पहले और उसके बाद feats_conv संकेत हैं। यह दृष्टिकोण अधिक कठोर है, लेकिन बहुत खराब रूप से छोटा है। इसके अलावा, यदि आप इसके बारे में थोड़ा सोचते हैं कि क्या हो रहा है, तो यह वर्टेक्स में फ़ीचर के मूल्य और वर्टेक्स के पड़ोसियों में औसत के बीच अंतर के बराबर है, अर्थात, यह तालिकाओं के साथ पिछली योजना द्वारा पूरी तरह से हल किया जा सकता है, यदि आप एक ऑपरेशन जोड़ते हैं।

संदर्भ

ग्राफ विज़ुअलाइज़ेशन समीक्षाएं
leonidzhukov.net/hse/2018/sna/papers/gibson2013
arxiv.org/pdf/1710.04328.pdf

ग्राफ संवादी नेटवर्क को सरल बनाना
arxiv.org/pdf/1902.07153.pdf

Graphviz
graphviz.org

Gephi
gephi.org

igraph
igraph.org

LargeViz
arxiv.org/abs/1602.00370
github.com/lferry007/LargeVis

Graphistry
www.graphistry.com

Node2Vec
snap.stanford.edu/node2vec
github.com/xgfs/node2vec-c

कविता
tsitsul.in/publications/verse
github.com/xgfs/verse

पूर्ण पांडा पैकेज कोड के साथ नोटबुक
github.com/iggisv9t/graph-stuff/blob/master/Universal%20Convolver%20Example.ipynb

ग्राफ का हल
यहां ग्राफ़ कनवल्शन नेटवर्क पर एकत्रित कार्य किए गए हैं: github.com/thunlp/GNNPapers

एक तालिका में पूरे लेख का सार