💻 computer science

What Makes Majority Illusion Easy to Detect?

यह शोध पत्र सामाजिक नेटवर्क में "बहुमत भ्रम" (majority illusion) का पता लगाने की गणनात्मक जटिलता की जांच करता है, जिसमें यह विश्लेषण किया गया है कि विभिन्न संरचनात्मक गुण उस नेटवर्क विन्यास के निर्धारण की सुगमता को कैसे प्रभावित करते है जहाँ एजेंटों का एक महत्वपूर्ण अंश गलती से अल्पसंख्यक राय को प्रभावी समझने लगता है।

मूल लेखक: Šimon Schierreich, Ildikó Schlotter

प्रकाशित 2026-06-04

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Šimon Schierreich, Ildikó Schlotter

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक सोशल नेटवर्क की कल्पना एक विशाल पार्टी के रूप में करें जहाँ हर कोई या तो नीले (Blue) रंग की शर्ट पहने हुए है या लाल (Red) रंग की। इस शोध पत्र में, लेखक एक अजीब मनोवैज्ञानिक गड़बड़ी का अध्ययन कर रहे हैं जिसे "मेजोरिटी इल्यूजन" (बहुमत का भ्रम) कहा जाता है।

यहाँ गड़बड़ी यह है: भले ही पार्टी में 60% लोग नीले रंग की शर्ट पहने हों, फिर भी एक विशिष्ट व्यक्ति अपने आस-पास के दोस्तों के घेरे को देख सकता है और देख सकता है कि उनमें से अधिकांश लाल रंग पहने हुए हैं। क्योंकि मनुष्य यह सोचने की प्रवृत्ति रखते हैं कि "मेरे दोस्त दुनिया का प्रतिनिधित्व करते हैं," वह व्यक्ति गलती से यह मान लेता है कि लाल रंग प्रमुख रंग है। यदि पर्याप्त लोगों का ऐसा गलत विचार हो जाता है, तो पूरी पार्टी के निर्णय लेने की प्रक्रिया बिगड़ जाती है।

यह शोध पत्र एक बहुत ही विशिष्ट प्रश्न पूछता है: एक कंप्यूटर के लिए यह पता लगाना कितना कठिन है कि क्या ऐसा कोई पार्टी लेआउट मौजूद है जहाँ यह भ्रम होता है?

लेखक पार्टी के लेआउट को एक मानचित्र (ग्राफ) के रूप में देखते हैं और उन "नियमों" को खोजने का प्रयास करते हैं जो इस पहेली को हल करना आसान या असंभव बनाते हैं। यहाँ उनके निष्कर्षों का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. "सुपर-कनेक्टर" नियम (वर्टेक्स इंटीग्रिटी)

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

2. "ट्री" बनाम "फॉरेस्ट" नियम (फीडबैक एज सेट)

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

3. "स्टार" और "पाथ" का जाल

अवधारणा:

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

4. "क्लब" नियम (डिस्टेंस टू क्लीक्स)

अवधारणा: कल्पना करें कि पार्टी कई घनिष्ठ क्लबों (cliques) से बनी है जहाँ क्लब का हर सदस्य दूसरे को जानता है।
निष्कर्ष:

यदि इन पूर्ण क्लबों को पाने के लिए आपको कुछ लोगों को हटाना पड़ता है, तो यह "कठिन" है (हालाँकि असंभव नहीं है, जैसे-जैसे पार्टी बढ़ती है यह धीमा होता जाता है)।
यदि इन पूर्ण क्लबों को पाने के लिए आपको कुछ मित्रताओं (edges) को हटाना पड़ता है, तो समस्या फिर से आसान हो जाती है।
उपमा:
लोगों को हटाना: यदि आपको क्लबों को ठीक करने के लिए लोगों को बाहर निकालना पड़ता है, तो आप समूहों की संरचना को इस तरह बदल रहे हैं कि बहुत सारे वेरिएबल्स (variables) पैदा हो जाते हैं।
मित्रताओं को हटाना: यदि आपको क्लबों को पूर्ण बनाने के लिए बस कुछ संबंधों को काटना है, तो कंप्यूटर इसे आसानी से संभाल सकता है। यह फर्नीचर को फेंकने के बजाय कुछ वस्तुओं (edges) को इधर-उधर करके एक अस्त-व्यस्त कमरे को ठीक करने जैसा है।

बड़ी तस्वीर: क्या इसे आसान बनाता है?

लेखक निष्कर्ष निकालते हैं कि कंप्यूटर के लिए इस "मेजोरिटी इल्यूजन" का आसानी से पता लगाने के लिए, सोशल नेटवर्क को आमतौर पर तीन श्रेणियों में से एक में आना चाहिए:

यह लगभग एक पेड़ है (आपको केवल कुछ पुल काटने की आवश्यकता है)।
यह छोटे, स्वतंत्र द्वीपों से बना है (आप कुछ "सुपर-कनेक्टर्स" को हटाकर छोटे समूहों को छोड़ सकते हैं)।
यह लगतः पूर्ण क्लबों का एक संग्रह है (आपको क्लबों को पूर्ण बनाने के लिए केवल कुछ मित्रताएँ काटनी होंगी)।

यदि नेटवर्क किसी अन्य तरीके से अस्त-व्यस्त है (जैसे, संरचना को ठीक करने के लिए लोगों को हटाने की आवश्यकता है, या जटिल लूप हैं), तो कंप्यूटर एक दीवार से टकरा जाता है और समस्या "कंप्यूटेशनल रूप से कठिन" (intractable) हो जाती है—जिसका अर्थ है कि एक बड़े पार्टी के लिए इसे हल करने में ब्रह्मांड की आयु से भी अधिक समय लगेगा।

संक्षेप में: यह शोध पत्र इस बात का सटीक मानचित्र तैयार करता है कि कौन से सोशल नेटवर्क के आकार हमें जल्दी से यह पहचानने की अनुमति देते हैं कि लोग अपने दोस्तों द्वारा धोखे में हैं, और कौन से आकार इसे गणितीय रूप से असंभव बना देते हैं।

तकनीकी सारांश: मेजॉरिटी इल्यूजन (Majority Illusion) का पता लगाना आसान क्यों है?

समस्या की परिभाषा

यह शोध पत्र सामाजिक नेटवर्क में मेजॉरिटी इल्यूजन (Majority Illusion) का पता लगाने की कम्प्यूटेशनल जटिलता की जांच करता है। औपचारिक रूप से, एक सामाजिक नेटवर्क को एक अनडिरेक्टेड ग्राफ $G = (N, E)$ के रूप में मॉडल किया गया है जहाँ वर्टिस (vertices) एजेंटों का प्रतिनिधित्व करते हैं और एडजेस (edges) सामाजिक संबंधों का प्रतिनिधित्व करते हैं। एजेंटों को एक बाइनरी लेबल (जैसे, "लाल" या "नीला") दिया जाता है। एक एजेंट मेजॉरिटी इल्यूजन के अंतर्गत तब होता है जब वह अपने स्थानीय पड़ोस (local neighborhood) में अल्पसंख्यक लेबल (minority label) को प्रभावी (dominant) के रूप में देखता है।

केंद्रीय निर्णय समस्या $q$ -मेजॉरिटी इल्यूजन समस्या है: दिए गए ग्राफ $G$ और एक परिमेय $q \in [0, 1]$ के लिए, क्या एजेंटों का एक ऐसा बाइनरी लेबलिंग मौजूद है जिससे वैश्विक बहुमत एक विशिष्ट लेबल (मान लीजिए नीला) हो, फिर भी कम से कम $q$ -हिस्से के एजेंटों के पास अल्पसंख्यक लेबल (लाल) के पड़ोसियों का सख्त बहुमत (strict majority) हो?

ग्रैंडी एट अल. (2025) के पिछले कार्य ने स्थापित किया कि यह समस्या सामान्य रूप से, यहाँ तक कि प्रतिबंधित ग्राफ वर्गों जैसे कि बाइपार्टाइट ग्राफ, प्लेनर ग्राफ, या अधिकतम डिग्री 6 वाले ग्राफ के लिए भी NP-कम्प्लीट है। हालांकि उन्होंने वर्टेक्स कवर नंबर और नेबरहुड डाइवर्सिटी जैसे मापदंडों के लिए फिक्स्ड-पैरामीटर ट्रैक्टेबल (FPT) एल्गोरिदम प्रदान किए, और दिखाया कि यह समस्या ट्रीविड्थ (treewidth) के लिए XP में है, लेकिन वे इस खुले प्रश्न को छोड़ गए कि कौन से संरचनात्मक प्रतिबंध समस्या को कुशलतापूर्वक समाधान योग्य (FPT) बनाम अग्राह्य (intractable) बनाते हैं।

कार्यप्रणाली (Methodology)

लेखक $q$ -मेजॉरिटी इल्यूजन समस्या की सुलभता का विश्लेषण करने के लिए पैरामीटराइज्ड कॉम्प्लेक्सिटी (parameterized complexity) के ढांचे का उपयोग करते हैं। वे विभिन्न संरचनात्मक ग्राफ मापदंडों के संबंध में समस्या का व्यवस्थित अध्ययन करते हैं, जिनमें शामिल हैं:

वर्टेक्स इंटीग्रिटी ($vi(G)$): उस न्यूनतम आकार के वर्टेक्स सेट का आकार जिसे हटाने से घटक (components) सीमित आकार के रह जाते हैं।
फीडबैक एज सेट ($fes(G) $) और फीडबैक वर्टेक्स सेट ($ fvs(G)$): ग्राफ को अचक्रीय (acyclic) बनाने के लिए हटाने के लिए आवश्यक न्यूनतम एडजेस या वर्टेक्स।
ग्राफ वर्गों से दूरी (Distance to Graph Classes): विशिष्ट वर्गों जैसे कि डिसजॉइंट स्टार्स, डिसजॉइंट पाथ्स और क्लस्टर ग्राफ (क्लीक के डिसजॉइंट यूनियन) के लिए वर्टेक्स या एज दूरी को मापने वाले पैरामीटर।
ट्रीडेप्थ ($td(G) $) और ट्रीविड्थ ($ tw(G)$): मानक संरचनात्मक पैरामीटर।

कार्यप्रणाली में दो प्राथमिक एल्गोरिदम तकनीकें शामिल हैं:

N-फोल्ड इंटीजर लीनियर प्रोग्रामिंग (ILP): वर्टेक्स इंटीग्रिटी जैसे मापदंडों के लिए FPT परिणामों को सिद्ध करने के लिए उपयोग किया जाता है। समस्या को एक N-फोल्ड IP के रूप में तैयार किया जाता है जहाँ बाधाओं (constraints) को वैश्विक बाधाओं (वैश्विक बहुमत और भ्रमित एजेंटों की कुल संख्या सुनिश्चित करना) और स्थानीय बाधाओं (विशिष्ट घटकों के लिए स्थानीय नेबरहुड स्थितियाँ सुनिश्चित करना) में विभाजित किया जाता है।
डायनेमिक प्रोग्रामिंग (DP): पेड़ जैसी संरचनाओं (पेड़, पथ) और ऐसी संरचनाओं के करीब के ग्राफों के लिए उपयोग किया जाता है। पेड़ों के लिए, लेखक एक संबंधित "मैक्स लिस्ट मेजॉरिटी इल्यूजन" समस्या के लिए एक बहुपद-समय (polynomial-time) एल्गोरिदम डिजाइन करते हैं, जो फीडबैक एज सेट पर आधारित FPT एल्गोरिदम के लिए एक सब-रूटीन के रूप में कार्य करता है।

कठिनाई (hardness) परिणामों के लिए, लेखक ज्ञात W[1]-हार्ड समस्याओं, विशेष रूप से मल्टीडायमेंशनल सबसेट सम (और इसके हाफसेट वेरिएंट) और कैपैसिटेटेड वर्टेक्स कवर से पैरामीटराइज्ड रिडक्शन प्रदान करते हैं।

मुख्य योगदान और परिणाम

1. फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी (FPT)

यह शोध पत्र कई नए पैरामीटराइजेशन के लिए FPT एल्गोरिदम स्थापित करता है:

**वर्टेक्स इंटीग्रिटी ($vi(G) $):** लेखक सिद्ध करते हैं कि वर्टेक्स इंटीग्रिटी द्वारा पैरामीटराइज होने पर$ q$-मेजॉरिटी इल्यूजन FPT में है। एल्गोरिदम "सेपरेटर" सेट $M$ की लेबलिंग का अनुमान लगाता है और शेष छोटे घटकों तक इस लेबलिंग को विस्तारित करने के लिए N-फोल्ड ILP का उपयोग करता है। यह परिणाम वर्टेक्स कवर नंबर ($vc(G) $) के लिए भी एक बेहतर रनिंग टाइम देता है, जो जटिलता को दोहरी घातीय ($ 2^{2^{O(vc)}} $) से घटाकर एकल घातीय ($ 2^{O(vc^2 \log vc)}$) कर देता है।
फीडबैक एज सेट ($fes(G)$): फीडबैक एज सेट संख्या द्वारा पैरामीटराइज होने पर समस्या FPT में दिखाई गई है। दृष्टिकोण फीडबैक एडजेस से जुड़े वर्टेक्स की लेबलिंग का अनुमान लगाने, ग्राफ को "गैजेट्स" (पेंडेंट लीव्स) के साथ एक पेड़ में बदलने और पेड़ों पर बहुपद-समय डायनेमिक प्रोग्रामिंग एल्गोरिदम का उपयोग करके परिणामी इंस्टेंस को हल करने में शामिल है।
क्लस्टर एज डिलीशन नंबर ($cdn(G)$): उन ग्राफों के लिए जो कुछ सीमित एडजेस को हटाने के बाद क्लीक के डिसजॉइंट यूनियन बन जाते हैं, समस्या FPT में है। एल्गोरिदम हटाए गए एडजेस के एंडपॉइंट्स की लेबलिंग का अनुमान लगाता है और क्लीक के ऊपर डायनेमिक प्रोग्रामिंग का उपयोग करता है, यह लाभ उठाते हुए कि एक क्लीक के भीतर एजेंटों की स्थिति केवल लाल एजेंटों की संख्या और निश्चित बाहरी कनेक्शनों पर निर्भर करती है।

2. W[1]-हार्डनेस और अग्राह्यता (Intractability)

यह शोध पत्र मजबूत नकारात्मक परिणाम प्रदान करता है, यह दिखाते हुए कि समस्या सरल संरचनाओं के "करीब" होने के बावजूद भी कठिन बनी रहती है:

डिसजॉइंट स्टार्स की दूरी ($dds(G)$): डिसजॉइंट स्टार्स के वर्टेक्स डिस्टेंस द्वारा पैरामीटराइज होने पर समस्या W[1]-हार्ड है। यह मल्टीडायमेंशनल हाफसेट सम से रिडक्शन के माध्यम से सिद्ध किया गया है।
डिसजॉइंट पाथ्स की दूरी ($ddp(G)$): इसी तरह, डिसजॉइंट पाथ्स के वर्टेक्स डिस्टेंस द्वारा पैरामीटराइज होने पर भी यह W[1]-हार्ड है।
ट्रीडेप्थ ($td(G)$): ट्रीडेप्थ द्वारा पैरामीटराइज होने पर समस्या W[1]-हार्ड है। यह ग्रैंडी एट अल. (2025) के एक महत्वपूर्ण खुले प्रश्न को हल करता है, जो यह संकेत देता है कि ट्रीविड्थ (जो ट्रीडेप्थ द्वारा सीमित है) के लिए FPT एल्गोरिदम मानक जटिलता धारणाओं के तहत असंभावित है।
क्लस्टर ग्राफ की दूरी ($dcg(G)$): क्लस्टर ग्राफ के वर्टेक्स डिस्टेंस द्वारा पैरामीटराइज होने पर समस्या XP में है लेकिन W[1]-हार्ड है। यह क्लस्टर ग्राफ के एज डिस्टेंस ($cdn(G)$) के लिए FPT परिणाम के विपरीत है।

3. विशिष्ट वर्गों पर बहुपद-समय समाधान क्षमता

लेखक उन ग्राफों के लिए एक लीनियर-टाइम एल्गोरिदम प्रदान करते हैं जो डिसजॉइंट पाथ्स के यूनियन हैं। वे केवल एजेंटों की संख्या के आधार पर एक पथ (path) में मेजॉरिटी इल्यूजन के तहत अधिकतम एजेंटों के लिए एक क्लोज्ड-फॉर्म एक्सप्रेशन प्राप्त करते हैं, जो यह दर्शाता है कि पथ और डिसजॉइंट पाथ्स पर समस्या आसानी से हल करने योग्य है।

महत्व और निष्कर्ष

इस शोध पत्र का प्राथमिक योगदान मेजॉरिटी इल्यूजन डिटेक्शन समस्या के कम्प्यूटेशनल कॉम्प्लेक्सिटी लैंडस्केप का एक व्यापक "मानचित्र" बनाना है। यह स्पष्ट करता है कि कौन सी विशिष्ट संरचनात्मक विशेषताएं कुशल पहचान को सक्षम बनाती हैं।

लेखक निष्कर्ष निकालते हैं कि समस्या के समाधान योग्य (FPT) होने के लिए, सामाजिक नेटवर्क को तीन में से एक शर्त को पूरा करना चाहिए:

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

परिणाम एक तीव्र द्वंद्व (dichotomy) को उजागर करते हैं: जबकि एक सरल संरचना तक पहुँचने के लिए कुछ कम एडजेस को हटाना अक्सर FPT एल्गोरिदम की ओर ले जाता है, उसी संरचना तक पहुँचने के लिए कुछ कम वर्टेक्स को हटाना अक्सर W[1]-हार्डनेस की ओर ले जाता है। यह शोध पत्र ट्विन-कवर नंबर (twin-cover number) के लिए समस्या की जटिलता को खुला छोड़ता है, यह नोट करते हुए कि यह क्लस्टर ग्राफ के वर्टेक्स डिस्टेंस (XP) और क्लस्टर ग्राफ के एज डिस्टेंस (FPT) के बीच स्थित है, और यह सवाल उठाता है कि क्या अतिरिक्त ट्विन संरचना FPT एल्गोरिदम की अनुमति देती है।