रुकें और देखें

इन्फ्लुएंस मैक्सिमाइजेशन (IM), जो एक छोटे सेट के मुख्य उपयोगकर्ताओं की तलाश करता है जो प्रभाव को नेटवर्क में व्यापक रूप से फैलाते हैं, कई क्षेत्रों में एक मुख्य समस्या है। इसका उपयोग वायरल मार्केटिंग, महामारी नियंत्रण, और जटिल प्रणालियों के भीतर कैस्केडिंग विफलताओं का आकलन करने में होता है। विशाल प्रयास के बावजूद, फेसबुक, ट्विटर और वर्ल्ड वाइड वेब जैसे अरब-स्तरीय नेटवर्क में IM को संतोषजनक रूप से हल नहीं किया गया है। यहां तक कि TIM+ और IMM जैसे अत्याधुनिक तरीकों को भी उन नेटवर्क पर दिनों लग सकते हैं। इस पेपर में, हम IM आधारित वायरल मार्केटिंग समस्याओं के लिए SSA और D-SSA, दो नवीन सैंपलिंग ढांचे का प्रस्ताव करते हैं। SSA और D-SSA SIGMOD'15 की सबसे अच्छी विधि, IMM की तुलना में 1200 गुना तक तेज हैं, जबकि समान (1-1/e-ε) अनुमानों की गारंटी प्रदान करते हैं। हमारे ढाचों के अंतर्गत एक अभिनव रुकें और देखें रणनीति है जिसमें वे समाधान की गुणवत्ता पर पर्याप्त सांख्यिकीय प्रमाण है या नहीं, यह सत्यापित करने के लिए गुणात्मक चेकपॉइंट पर रुकते हैं। थियॉरेटिकली, हम साबित करते हैं कि SSA और D-SSA पहले अनुमापक एल्गोरिदम हैं जो (असिम्प्टोटिकली) न्यूनतम संख्या में नमूनों का उपयोग करते हैं, IM के लिए निर्धारित सख्त थियॉरेटिकल थ्रेशोल्ड्स को पूरा करते हैं। SSA और D-SSA की पूर्ण श्रेष्ठता IM और एक अन्य विषय-सचेत वायरल मार्केटिंग समस्या, जिसे TVM कहा जाता है, के लिए वास्तविक नेटवर्क डेटा पर व्यापक प्रयोगों के माध्यम से पुष्टि की गई है।