बल-निर्देशित ग्राफ़ आरेखण

बल-निर्देशित ग्राफ़ ड्राइंग एल्गोरिदम का उपयोग करके सामाजिक नेटवर्क विज़ुअलाइज़ेशन

बल-निर्देशित लेआउट का उपयोग करके विकी पर पृष्ठों के बीच लिंक का विज़ुअलाइज़ेशन

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

जबकि ग्राफ़ बनाना एक कठिन समस्या हो सकती है, बल-निर्देशित एल्गोरिदम, भौतिक सिमुलेशन होने के कारण, आमतौर पर ग्राफ़ सिद्धांत जैसे कि समतलीय ग्राफ के बारे में किसी विशेष ज्ञान की आवश्यकता नहीं होती है।

बल

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

एक वैकल्पिक मॉडल प्रत्येक जोड़ी नोड्स के लिए स्प्रिंग-जैसे बल पर विचार करता है $(i,j)$ जहां आदर्श लंबाई है $\delta _{ij}$ प्रत्येक स्प्रिंग का मान एक अलग प्रतिकारक बल का उपयोग किए बिना, नोड्स i और j के बीच ग्राफ-सैद्धांतिक दूरी के समानुपाती होता है। यूक्लिडियन दूरी और नोड्स के बीच आदर्श दूरी के बीच अंतर (आमतौर पर वर्ग अंतर) को कम करना एक मीट्रिक बहुआयामी स्केलिंग समस्या के बराबर है।

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

तरीके

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

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

ऐसे तंत्रों को नियोजित करना भी संभव है जो भौतिक सिमुलेशन के बजाय या उसके संयोजन के साथ ऊर्जा मिनिमा के लिए अधिक सीधे खोज करते हैं। ऐसे तंत्र, जो सामान्य वैश्विक अनुकूलन विधियों के उदाहरण हैं, में तैयार किए हुयी धातु पे पानी चढाने की कला और आनुवंशिक एल्गोरिदम शामिल हैं।

फायदे

बल-निर्देशित एल्गोरिदम के सबसे महत्वपूर्ण लाभों में से निम्नलिखित हैं:

अच्छी गुणवत्ता वाले परिणाम

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

लचीलापन

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

सहज ज्ञान युक्त

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

सरलता

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

अन्तरक्रियाशीलता

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

मजबूत सैद्धांतिक आधार

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

नुकसान

बल-निर्देशित एल्गोरिदम के मुख्य नुकसानों में निम्नलिखित शामिल हैं:

उच्च समय जटिलता

विशिष्ट बल-निर्देशित एल्गोरिदम को आम तौर पर घन समय में चलने वाला माना जाता है ($O(n^{3})$), कहाँ $n$ इनपुट ग्राफ़ के नोड्स की संख्या है। ऐसा इसलिए है क्योंकि पुनरावृत्तियों की संख्या रैखिक होने का अनुमान है ($O(n)$), और प्रत्येक पुनरावृत्ति में, नोड्स के सभी जोड़े का दौरा करने और उनकी पारस्परिक प्रतिकारक शक्तियों की गणना करने की आवश्यकता होती है। यह भौतिकी में एन-बॉडी समस्या से संबंधित है। हालाँकि, चूँकि प्रतिकारक शक्तियाँ स्थानीय प्रकृति की होती हैं, इसलिए ग्राफ को इस तरह विभाजित किया जा सकता है कि केवल पड़ोसी शीर्षों पर ही विचार किया जाए। बड़े ग्राफ़ के लेआउट को निर्धारित करने के लिए एल्गोरिदम द्वारा उपयोग की जाने वाली सामान्य तकनीकों में उच्च-आयामी एम्बेडिंग शामिल है, मल्टी-लेयर ड्राइंग और एन-बॉडी सिमुलेशन से संबंधित अन्य विधियां। उदाहरण के लिए, बार्न्स-हट सिमुलेशन-आधारित विधि FADE चलने के समय को रैखिक अंकीय बनाने में सुधार कर सकते हैं, या $n\log(n)$ प्रति पुनरावृत्ति. एक मोटे मार्गदर्शक के रूप में, कुछ ही सेकंड में एक मानक के साथ अधिकतम 1,000 नोड्स खींचने की उम्मीद की जा सकती है $n^{2}$ प्रति पुनरावृत्ति तकनीक, और 100,000 के साथ $n\log(n)$ प्रति पुनरावृत्ति तकनीक.बल-निर्देशित एल्गोरिदम, जब ग्राफ़ क्लस्टरिंग दृष्टिकोण के साथ संयुक्त होते हैं, तो लाखों नोड्स के ग्राफ़ खींच सकते हैं।

ख़राब स्थानीय न्यूनतम

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

इतिहास

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

आसन्न शीर्षों पर आकर्षक बलों और सभी शीर्षों पर प्रतिकारक बलों के संयोजन का प्रयोग सबसे पहले किसके द्वारा किया गया था? Eades (1984); इस प्रकार के बल-निर्देशित लेआउट पर अतिरिक्त अग्रणी कार्य किसके द्वारा किया गया था? Fruchterman & Reingold (1991). शीर्षों के सभी युग्मों के बीच केवल स्प्रिंग बलों का उपयोग करने का विचार, शीर्षों की ग्राफ-सैद्धांतिक दूरी के बराबर आदर्श स्प्रिंग लंबाई के साथ, से है Kamada & Kawai (1989).

यह भी देखें

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

अग्रिम पठन

• di Battista, Giuseppe; Peter Eades; Roberto Tamassia; Ioannis G. Tollis (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4
• Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Drawing graphs: methods and models, Lecture Notes in Computer Science 2025, vol. 2025, Springer, doi:10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID 1808286

बाहरी संबंध

• Book chapter on Force-Directed Drawing Algorithms by Stephen G. Kobourov
• Daniel Tunkelang's dissertation on force-directed graph layout