बड़े पैमाने पर सामाजिक नेटवर्क में प्रचलित वायरल मार्केटिंग के लिए स्केलेबल प्रभाव अधिकतमकरण

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