वृद्धिशील के-कोर एल्गोरिदम

Question

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

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

संपादित करें:

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

एक कशेरुक जोड़ना शिखर की कोरनेस पर मनमाने ढंग से दूर हो सकता है, लेकिन शायद यह सबसे बुरी स्थिति व्यवहार पर बहुत अधिक ध्यान केंद्रित कर रहा है।

Answer 1

मुझे ऐसा लगता है कि ग्राफ के स्थानीय अन्वेषण, "वैश्विक" पुनरावृत्ति छंटाई के बजाय के आधार पर एक वृद्धिशील कश्मीर कोर गणना के लिए एक एल्गोरिथ्म, क्रम में देखने के लिए एक वृद्धिशील पाश का पता लगाने की आवश्यकता होगी कौन सा किनारों के-कोर में एक कशेरुक में प्रवेश करने में योगदान दे सकता है, जो एक कठिन समस्या है।

मुझे लगता है कि आप जो भी कर सकते हैं, वह प्रत्येक पास पर के-कोर एल्गोरिदम को दोबारा शुरू करना है, केवल पहले से ही के-कोर में मौजूद चरम को हटाकर और नक्शा वर्टेक्स में शुरू करना,> "k -कोर आसन्न शिखर "आसन्न शिखर की संख्या जो पहले से ही के-कोर में हैं।

Answer 2

त्वरित विचार: आप इतिहास को एल सूची में सहेज सकते हैं, यानी, उस ऑर्डर को सहेज लें जिसमें नोड्स को हटाया गया था। जब भी आप कोई नया नोड बनाते हैं, तो एल में पहले नोड डब्ल्यू से शुरू होता है जो v के समीप होता है। फिर रैखिक क्रम में एल से शेष नोड्स के माध्यम से जाएं। (और नोड वी को भी जांचें और संभवतः इसे एल में जोड़ें।

Answer 3

यह एक कठिन समस्या है, लेकिन निश्चित रूप से एनपी-हार्ड नहीं है। जहां तक ​​मुझे पता है, के-कोर के किसी भी संख्या के साथ बढ़ते अद्यतन पर अकादमिक में कोई सामान्य समाधान नहीं है। लेकिन निम्नलिखित दो कागजात निश्चित रूप से योग्य पढ़ रहे हैं:

[1] त्रिकोण के विश्लेषण और विज़ुअलाइजिंग को निकालने के लिए- नेटवर्क के भीतर कोर आकृतियां। http://www.cse.ohio-state.edu/~zhangya/ICDE12_conf_full_179.pdf

[2] के-कोर अपघटन के लिए स्ट्रीमिंग एल्गोरिदम। http://www.cse.ohio-state.edu/~sariyuce/file/Publications_files/VLDB13.pdf

वे डेटा प्रबंधन क्षेत्र में प्रमुख सम्मेलनों में दिखाई दिए हैं, इसलिए पद्धति विश्वसनीय होना चाहिए।