प्लांटेड क्लिक: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
ग्राफ़ में एक क्लिक शीर्षों का एक उपसमूह होता है, जो सभी एक-दूसरे से सटे होते हैं। एक प्लांटेड क्लिक एक चयनित उपसमुच्चय के सभी जोड़े के बीच किनारों को जोड़कर दूसरे ग्राफ से बनाया गया एक क्लिक है। | ग्राफ़ में एक क्लिक शीर्षों का एक उपसमूह होता है, जो सभी एक-दूसरे से सटे होते हैं। एक प्लांटेड क्लिक एक चयनित उपसमुच्चय के सभी जोड़े के बीच किनारों को जोड़कर दूसरे ग्राफ से बनाया गया एक क्लिक है। | ||
प्लांटेड क्लिक समस्या को | प्लांटेड क्लिक समस्या को ग्राफ़ पर [[यादृच्छिक वितरण]] पर [[निर्णय समस्या]] के रूप में औपचारिक रूप दिया जा सकता है, जिसे दो संख्याओं, {{mvar|n}} (शीर्षों की संख्या), और {{mvar|k}} (क्लिक का आकार) द्वारा पैरामीटर किया जाता है। इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:<ref name="ab">{{citation|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref> | ||
इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:<ref name="ab">{{citation|title=Computational Complexity: A Modern Approach|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|publisher=Cambridge University Press|year=2009|isbn=9780521424264|pages=362–363|url=https://books.google.com/books?id=8Wjqvsoo48MC&pg=PA362}}.</ref> | #शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके {{mvar|n}} शीर्षों पर एक एर्दो-रेनी यादृच्छिक ग्राफ़ बनाएं कि क्या प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ उस जोड़े को जोड़ने वाला एक किनारा सम्मिलित किया जाए। | ||
# | |||
#प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ। | #प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ। | ||
# | #यदि {{mvar|n}} शीर्ष है तो यादृच्छिक रूप से {{mvar|k}} का एक उपसमुच्चय चुनें और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा (यदि कोई पहले से उपस्थित नहीं है) जोड़ें। | ||
समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से | समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से एक में कम से कम {{mvar|k}} शीर्षों का एक समूह है। | ||
=== ऊपरी और निचली सीमाएं === | === ऊपरी और निचली सीमाएं === | ||
वहाँ एक फ़ंक्शन | वहाँ एक फ़ंक्शन <math>f(n) \sim 2 \log_2 n</math> उपस्थित है जैसे कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, {{mvar|n}}-वर्टेक्स यादृच्छिक ग्राफ में सबसे बड़े क्लिक का आकार या तो <math>f(n)</math> या <math>f(n)+1</math>+1 है,<ref>{{Cite journal |last1=Bollobas |first1=B. |last2=Erdös |first2=P. |date=November 1976 |title=यादृच्छिक ग्राफ़ में क्लिक्स|url=https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/cliques-in-random-graphs/27321102B82EDEEF362556BE714FACD9 |journal=Mathematical Proceedings of the Cambridge Philosophical Society |language=en |volume=80 |issue=3 |pages=419–427 |doi=10.1017/S0305004100053056 |s2cid=16619643 |issn=1469-8064}}</ref> और कुछ स्थिरांक <math>c</math> उपस्थित है जैसे कि आकार के क्लिक्स की अपेक्षित संख्या <math>\geq f(n) -c</math> अनंत में परिवर्तित हो जाता है। परिणामस्वरूप, किसी को अपेक्षा करनी चाहिए कि <math>\sim 2 \log_2 n</math> आकार के एक समूह के रोपण का उच्च संभावना के साथ पता नहीं लगाया जा सकता है। | ||
[[केंद्रीय सीमा प्रमेय]] के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य <math>\frac n2</math> और मानक विचलन <math>\frac \sqrt{n} 2</math> के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाता हैं। परिणामस्वरूप, जब <math>k</math> <math>\sqrt n</math> के क्रम पर होता है यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन उत्पन्न करता हैं। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी {{mvar|k}} इन दो मानों के बीच है,<ref name="ab" /> | |||
<nowiki>:</nowiki><math>2\log_2 n \ll k \ll \sqrt n.</math> | |||
| Line 93: | Line 95: | ||
#सभी सेटों के माध्यम से लूप करें {{mvar|S}} का <math>\min(k,3\log_2 n)</math> शिखर. | #सभी सेटों के माध्यम से लूप करें {{mvar|S}} का <math>\min(k,3\log_2 n)</math> शिखर. | ||
#प्रत्येक विकल्प के लिए {{mvar|S}}, परीक्षण करें कि क्या {{mvar|S}} एक गुट है. यदि यह है, और <math>|S| = k</math>, वापस करना {{mvar|S}}. अन्यथा, सेट ढूंढें {{mvar|T}} उन शीर्षों का जो सभी शीर्षों से सटे हुए हैं {{mvar|S}}. अगर <math>|T|\ge k</math>, वापस करना {{mvar|T}}. | #प्रत्येक विकल्प के लिए {{mvar|S}}, परीक्षण करें कि क्या {{mvar|S}} एक गुट है. यदि यह है, और <math>|S| = k</math>, वापस करना {{mvar|S}}. अन्यथा, सेट ढूंढें {{mvar|T}} उन शीर्षों का जो सभी शीर्षों से सटे हुए हैं {{mvar|S}}. अगर <math>|T|\ge k</math>, वापस करना {{mvar|T}}. | ||
इस एल्गोरिथ्म का चलने का समय अर्धबहुपद है, क्योंकि अर्धबहुपद के कई विकल्प हैं {{mvar|S}} लूप ओवर करना। यह विधि एक सेट को आज़माने की गारंटी है {{mvar|S}} वह रोपित गुट का एक उपसमुच्चय है; उच्च संभावना के साथ, सेट {{mvar|T}} में केवल लगाए गए गुट के अन्य सदस्य | इस एल्गोरिथ्म का चलने का समय अर्धबहुपद है, क्योंकि अर्धबहुपद के कई विकल्प हैं {{mvar|S}} लूप ओवर करना। यह विधि एक सेट को आज़माने की गारंटी है {{mvar|S}} वह रोपित गुट का एक उपसमुच्चय है; उच्च संभावना के साथ, सेट {{mvar|T}} में केवल लगाए गए गुट के अन्य सदस्य सम्मिलित होंगे। | ||
==कठोरता धारणा के रूप में== | ==कठोरता धारणा के रूप में== | ||
Revision as of 10:32, 4 July 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, एक अप्रत्यक्ष ग्राफ़ में एक प्लांटेड क्लिक या छिपा हुआ क्लिक एक अन्य ग्राफ़ से बना एक क्लिक (ग्राफ़ सिद्धांत) होता है जो शीर्षों के एक उपसमूह का चयन करके और उपसमुच्चय में शीर्षों की प्रत्येक जोड़ी के बीच किनारों को जोड़कर बनता है। प्लांटेड क्लिक समस्या, प्लांटेड क्लिक वाले ग्राफ़ से यादृच्छिक ग्राफ़ को अलग करने की एल्गोरिथम समस्या है। यह गुट समस्या का एक रूप है; इसे अर्ध-बहुपद समय में समाधान किया जा सकता है किन्तु अनुमान लगाया गया है कि क्लिक आकार के मध्यवर्ती मानों के लिए यह बहुपद समय में समाधान करने योग्य नहीं है। यह अनुमान कि कोई बहुपद समय समाधान उपस्थित नहीं है, प्लांटेड क्लिक अनुमान कहलाता है; इसका उपयोग कम्प्यूटेशनल कठोरता धारणा के रूप में किया गया है।
परिभाषा
ग्राफ़ में एक क्लिक शीर्षों का एक उपसमूह होता है, जो सभी एक-दूसरे से सटे होते हैं। एक प्लांटेड क्लिक एक चयनित उपसमुच्चय के सभी जोड़े के बीच किनारों को जोड़कर दूसरे ग्राफ से बनाया गया एक क्लिक है।
प्लांटेड क्लिक समस्या को ग्राफ़ पर यादृच्छिक वितरण पर निर्णय समस्या के रूप में औपचारिक रूप दिया जा सकता है, जिसे दो संख्याओं, n (शीर्षों की संख्या), और k (क्लिक का आकार) द्वारा पैरामीटर किया जाता है। इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:[1]
- शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके n शीर्षों पर एक एर्दो-रेनी यादृच्छिक ग्राफ़ बनाएं कि क्या प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ उस जोड़े को जोड़ने वाला एक किनारा सम्मिलित किया जाए।
- प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ।
- यदि n शीर्ष है तो यादृच्छिक रूप से k का एक उपसमुच्चय चुनें और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा (यदि कोई पहले से उपस्थित नहीं है) जोड़ें।
समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से एक में कम से कम k शीर्षों का एक समूह है।
ऊपरी और निचली सीमाएं
वहाँ एक फ़ंक्शन उपस्थित है जैसे कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, n-वर्टेक्स यादृच्छिक ग्राफ में सबसे बड़े क्लिक का आकार या तो या +1 है,[2] और कुछ स्थिरांक उपस्थित है जैसे कि आकार के क्लिक्स की अपेक्षित संख्या अनंत में परिवर्तित हो जाता है। परिणामस्वरूप, किसी को अपेक्षा करनी चाहिए कि आकार के एक समूह के रोपण का उच्च संभावना के साथ पता नहीं लगाया जा सकता है।
केंद्रीय सीमा प्रमेय के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य और मानक विचलन के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाता हैं। परिणामस्वरूप, जब के क्रम पर होता है यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन उत्पन्न करता हैं। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी k इन दो मानों के बीच है,[1]
:
एल्गोरिदम
बड़े गुट
पैरामीटर के पर्याप्त बड़े मानों के लिए k, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) हल किया जा सकता है।[1]
Kučera (1995) देखता है कि, कब तो लगभग निश्चित रूप से लगाए गए समूह के सभी शीर्षों में समूह के बाहर के सभी शीर्षों की तुलना में उच्च डिग्री होती है, जिससे समूह को ढूंढना बहुत आसान हो जाता है। वह प्लांटेड क्लिक उदाहरण उत्पन्न करने के लिए यादृच्छिक प्रक्रिया में संशोधन का वर्णन करता है, जो बड़े मानों के लिए भी शीर्ष डिग्री को अधिक समान बनाता हैk, किन्तु दिखाता है कि इस संशोधन के बावजूद लगाए गए क्लिक को अभी भी जल्दी से पाया जा सकता है।[3]
Alon, Krivelevich & Sudakov (1998) के लिए सिद्ध करें एक रोपित गुट को निम्नलिखित विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
- आसन्न मैट्रिक्स के eigenvector की गणना उसके दूसरे उच्चतम eigenvalue के अनुरूप करें।
- का चयन करें k शीर्ष जिनके निर्देशांक इस आइजनवेक्टर में सबसे बड़े निरपेक्ष मान हैं।
- शीर्षों का वह सेट लौटाएं जो चयनित शीर्षों के कम से कम 3/4 से सटे हों।
वे बताते हैं कि इस तकनीक को कैसे संशोधित किया जाए ताकि यह कभी भी काम करती रहे k कम से कम शीर्षों की संख्या के वर्गमूल के कुछ गुणज के समानुपाती होता है।[4] अर्धनिश्चित प्रोग्रामिंग का उपयोग करके बड़े लगाए गए क्लिक्स भी पाए जा सकते हैं।[5] बेतरतीब ढंग से नमूनाकरण शीर्षों पर आधारित एक संयोजन तकनीक उसी सीमा को प्राप्त कर सकती है k और रैखिक समय में चलता है।[6]
अर्धबहुपद समय
पसंद की परवाह किए बिना, प्लांटेड क्लिक समस्या को हल करना भी संभव है k, अर्ध-बहुपद समय में।[7] क्योंकि यादृच्छिक ग्राफ़ में सबसे बड़े समूह का आकार आम तौर पर निकट होता है 2 log2 n,[8] आकार का एक रोपा हुआ समूह k (यदि यह उपस्थित है) निम्न विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:
- सभी सेटों के माध्यम से लूप करें S का शिखर.
- प्रत्येक विकल्प के लिए S, परीक्षण करें कि क्या S एक गुट है. यदि यह है, और , वापस करना S. अन्यथा, सेट ढूंढें T उन शीर्षों का जो सभी शीर्षों से सटे हुए हैं S. अगर , वापस करना T.
इस एल्गोरिथ्म का चलने का समय अर्धबहुपद है, क्योंकि अर्धबहुपद के कई विकल्प हैं S लूप ओवर करना। यह विधि एक सेट को आज़माने की गारंटी है S वह रोपित गुट का एक उपसमुच्चय है; उच्च संभावना के साथ, सेट T में केवल लगाए गए गुट के अन्य सदस्य सम्मिलित होंगे।
कठोरता धारणा के रूप में
प्लांटेड क्लिक अनुमान यह अनुमान है कि कोई बहुपद समय एल्गोरिथ्म नहीं है जो प्लांटेड क्लिक प्रक्रिया द्वारा उत्पादित इनपुट ग्राफ़ के रूप में लेता है और प्लांटेड क्लिक्स वाले लोगों को उन लोगों से अलग करता है जिनके पास यादृच्छिक मौके की तुलना में काफी बेहतर संभावना के साथ प्लांटेड क्लिक्स नहीं हैं।[9]
Hazan & Krauthgamer (2011) ने इस धारणा का उपयोग किया कि प्लांटेड क्लिक्स को ढूंढना एक कम्प्यूटेशनल कठोरता धारणा के रूप में कठिन है, यह साबित करने के लिए कि यदि ऐसा है, तो दो-खिलाड़ियों के खेल में सर्वोत्तम नैश संतुलन का अनुमान लगाना भी कठिन है।[7]संपत्ति परीक्षण के-स्वतंत्र हैशिंग की कठिनाई को दिखाने के लिए प्लांटेड क्लिक अनुमान का उपयोग कठोरता धारणा के रूप में भी किया गया है |k-यादृच्छिक वितरण की स्वतंत्रता,[10] सामाजिक नेटवर्क में क्लस्टर ढूँढना,[11] और यंत्र अधिगम ।[12]
संदर्भ
- ↑ 1.0 1.1 1.2 Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, pp. 362–363, ISBN 9780521424264.
- ↑ Bollobas, B.; Erdös, P. (November 1976). "यादृच्छिक ग्राफ़ में क्लिक्स". Mathematical Proceedings of the Cambridge Philosophical Society (in English). 80 (3): 419–427. doi:10.1017/S0305004100053056. ISSN 1469-8064. S2CID 16619643.
- ↑ Kučera, Luděk (1995), "Expected complexity of graph partitioning problems", Discrete Applied Mathematics, 57 (2–3): 193–212, doi:10.1016/0166-218X(94)00103-K, hdl:11858/00-001M-0000-0014-B73F-2, MR 1327775.
- ↑ Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, CiteSeerX 10.1.1.24.6419, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.3.CO;2-K, MR 1662795
- ↑ Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
- ↑ Dekel, Yael; Gurel-Gurevich, Ori; Peres, Yuval (2014), "Finding hidden cliques in linear time with high probability", Combinatorics, Probability and Computing, 23 (1): 29–49, arXiv:1010.2997, doi:10.1017/S096354831300045X, MR 3197965, S2CID 14356678.
- ↑ 7.0 7.1 Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?", SIAM Journal on Computing, 40 (1): 79–91, CiteSeerX 10.1.1.511.4422, doi:10.1137/090766991, MR 2765712.
- ↑ Grimmett, G. R.; McDiarmid, C. J. H. (1975), "On colouring random graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 77 (2): 313–324, Bibcode:1975MPCPS..77..313G, doi:10.1017/S0305004100051124, MR 0369129, S2CID 3421302.
- ↑ Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri (2015), ETH hardness for densest-k-subgraph with perfect completeness, arXiv:1504.08352, Bibcode:2015arXiv150408352B.
- ↑ Alon, Noga; Andoni, Alexandr; Kaufman, Tali; Matulef, Kevin; Rubinfeld, Ronitt; Xie, Ning (2007), "Testing k-wise and almost k-wise independence", STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 496–505, doi:10.1145/1250790.1250863, ISBN 9781595936318, MR 2402475, S2CID 5050980.
- ↑ Balcan, Maria-Florina; Borgs, Christian; Braverman, Mark; Chayes, Jennifer; Teng, Shang-Hua (2013), "Finding Endogenously Formed Communities", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13), SIAM, pp. 767–783, ISBN 978-1-611972-51-1.
- ↑ Berthet, Quentin; Rigollet, Philippe (2013), "Complexity theoretic lower bounds for sparse principal component detection", Conference on Learning Theory, Journal of Machine Learning Research, 30: 1046–1066.
