2008-11-07 10 views
6

बड़े उत्पादन सर्वर के लिए बीजीएल का उपयोग कर बाहर कोई भी?बूस्ट ग्राफ लाइब्रेरी: क्या समुदाय पहचान के लिए बीजीएल में निर्मित एक साफ एल्गोरिदम है?

  • आपके नेटवर्क में कितने नोड शामिल हैं?
  • आप कैसे community detection
  • क्या बीजीएल के समुदायों का पता लगाने के लिए कोई शानदार तरीका है?
  • कभी-कभी दो समुदायों को एक या दो किनारों से एक साथ जोड़ा जा सकता है, लेकिन ये किनार विश्वसनीय नहीं हैं और दूर हो सकते हैं। कभी-कभी कोई किनार नहीं होते हैं।

क्या कोई इस समस्या को हल करने के तरीके पर संक्षेप में बात कर सकता है। कृपया मेरा दिमाग खोलें और मुझे प्रेरित करें।

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

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

उत्तर

6

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

समुदाय पहचान के लिए, बीजीएल में विशेष रूप से इसके लिए निर्मित कोई भी एल्गोरिदम नहीं है (लेकिन हो सकता है कि आप अपनी परियोजना के साथ समाप्त होने पर एक योगदान कर सकें)। कुछ एल्गोरिदम हैं जो एक समुदाय पहचान एल्गोरिदम बनाने में सहायक हो सकते हैं।max-flow/min-cut एल्गोरिदम आमतौर पर सामुदायिक पहचान में उपयोग किए जाते हैं (यदि दो नोड्स के बीच बहुत अधिक प्रवाह संभव है, तो यदि वे अधिक प्रवाह नहीं करते हैं, तो वे एक ही समुदाय में होने की संभावना है, तो मिन-कट का प्रतिनिधित्व होने की संभावना है समुदायों के बीच सड़कों)। bandwidth को कम करने के लिए ग्राफ़ के नोड्स को ऑर्डर करने के लिए हेरिस्टिक भी हैं। "समुदायों" बनाने वाले नोड्स इस तरह के आदेश में एक-दूसरे के करीब होने की संभावना है।

+0

हम कैसे जाते हैं इस पर निर्भर करते हुए, कुछ ऐसा हो सकता है जिसे हम बूस्ट की पेशकश कर सकें, लेकिन मुझे कोड से शर्म आती है! आपको लगता है कि समुदाय इसे तेज कर सकता है! – Setori

+0

ओह और उस बैंडविड्थ रेड्यूसर सुझाव के लिए बहुत बहुत धन्यवाद, आप संभवतः मुझे एक और परेशानी की समस्या को हल करने के लिए सही दिशा में इंगित किया। – Setori

+0

शानदार अंतर्दृष्टि डेविड – Setori

0

जहां तक ​​मुझे पता है कि बीजीएल में विशेष रूप से समुदाय पहचान के लिए कोई एल्गोरिदम नहीं है।

"द्वीप" से आपका मतलब डिस्कनेक्ट किया गया सबग्राफ है?

इसके अलावा, ग्राफ में 'दूरी' की कोई धारणा नहीं है।

यह 'सामाजिक दूरी' कुछ ऐसा है जिसे आप परिभाषित करने जा रहे हैं। एक बार ऐसा करने के बाद कि काम का एक बड़ा हिस्सा किया जाता है।

आपके द्वारा लिंक किए गए पृष्ठ पर कई विधियां सूचीबद्ध हैं, जिनमें से अधिकांश को केवल 'दूरी' मीट्रिक की तरह कुछ परिभाषित करने की आवश्यकता है, और फिर अपनी परिभाषाओं को एल्गोरिदम में प्लग करें।

@ डेविड Nehme

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

इसके अलावा, वह दो डिस्कनेक्ट किए गए ग्राफ के बीच की दूरी के बारे में बात कर रहा है। इसे मॉडल करने के लिए, आपको किनारे से अलग नोड्स के बीच दूरी के लिए बाहरी अवधारणा पेश करनी होगी।

+0

द्वीप == डिस्कनेक्ट किया गया सबग्राफ – Setori

+0

स्टबूटन, आप वजन के मुद्दे के बारे में सही हैं, यह मेरी गलती है कि मैंने वजन घटाने का उल्लेख किया है। बस उन्हें प्रकृति का वर्णन करना थोड़ा मुश्किल था, मैंने इसे स्वीकार किया कि लोगों को समझ में आएगा कि वजन कम था। – Setori

संबंधित मुद्दे