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

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

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

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

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

बल

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

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

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

विधि

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

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

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

लाभ

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

उच्च गुणवत्ता वाले परिणाम

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

लचीलापन

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

सहज

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

सरलता

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

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

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

कठोर सैद्धांतिक आधार

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

हानि

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

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

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

निकृष्ट स्थानीय न्यूनतम

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

इतिहास

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

आसन्न शीर्षों पर आकर्षक बलों और सभी शीर्षों पर प्रतिकारक बलों के संयोजन का प्रयोग सर्वप्रथम किसके द्वारा किया गया था? ईड्स (1984); इस प्रकार के बल-निर्देशित लेआउट पर अतिरिक्त अग्रणी कार्य किसके द्वारा किया गया था? फ्रूचरमैन & रींगोल्ड (1991). शीर्षों के सभी युग्मों के मध्य केवल स्प्रिंग बलों का उपयोग करने का विचार, शीर्षों की ग्राफ-सैद्धांतिक दूरी के समान आदर्श स्प्रिंग लंबाई के साथ, से है कमादा & कवाई (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