{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T19:24:39Z","timestamp":1769714679412,"version":"3.49.0"},"reference-count":29,"publisher":"SAGE Publications","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IFS"],"published-print":{"date-parts":[[2023,12,2]]},"abstract":"<jats:p>The survey propagation algorithm is the most effective information propagation algorithm for solving the 3-SAT problem. It can effectively solve the satisfiability problem when it converges. However, when the factor graph structure is complex, the algorithm often does not converge and the solution fails. In order to give a theoretical explanation to this phenomenon and to analyze the convergence of the survey propagation algorithm effectively, a connected treewidth model of the propositional formula was constructed by using the connected tree decomposition method, and the connected treewidth of the factor graph was calculated. The relationship between the connected treewidth and the convergence of the survey propagation algorithm is established, and the convergence judgment condition of the survey propagation algorithm based on the connected tree width is given. Through experimental analysis, the results show that the method is effective, which is of great significance for analyzing the convergence analysis of other information propagation algorithms.<\/jats:p>","DOI":"10.3233\/jifs-223779","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T11:17:39Z","timestamp":1687259859000},"page":"9239-9252","source":"Crossref","is-referenced-by-count":0,"title":["Convergence analysis of a survey propagation algorithm1"],"prefix":"10.1177","volume":"45","author":[{"given":"Zhixin","family":"Xie","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"}]},{"given":"Xiaofeng","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"},{"name":"Key Laboratory of lmage and Graphics Intelligent Processing, State Ethnic Affairs Commission, Northern University for Nationalities, Yinchuan, China"}]},{"given":"Lan","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"}]},{"given":"Lichao","family":"Pang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"}]},{"given":"Xingyu","family":"Zhao","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"}]},{"given":"Yi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northern University for Nationalities, Yinchuan, China"}]}],"member":"179","reference":[{"key":"10.3233\/JIFS-223779_ref1","first-page":"13","article-title":"Constraint satisfaction: An emerging paradigm[M]\/\/Foundations of Artificial Intelligence","volume":"2","author":"Freuder","year":"2006","journal-title":"Elsevier"},{"issue":"4","key":"10.3233\/JIFS-223779_ref2","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/rsa.20104","article-title":"The probabilistic analysis of a greedy satisfiability algorithm[J]","volume":"28","author":"Kaporis","year":"2006","journal-title":"Random Structures & Algorithms"},{"issue":"30\u201332","key":"10.3233\/JIFS-223779_ref3","doi-asserted-by":"crossref","first-page":"2920","DOI":"10.1016\/j.tcs.2009.02.020","article-title":"On the satisfiability threshold of formulas with three literals per clause[J]","volume":"410","author":"D\u00edaz","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/JIFS-223779_ref4","doi-asserted-by":"crossref","unstructured":"Moskewicz M.W. , Madigan C.F. , Zhao Y. et al. Chaff: Engineering an efficient SAT solver[C]\/\/Proceedings of the 38th annual Design Automation Conference, (2001), 530\u2013535.","DOI":"10.1145\/378239.379017"},{"key":"10.3233\/JIFS-223779_ref5","first-page":"17","article-title":"Comparing beliefs, surveys, and random walks[J]","author":"Aurell","year":"2004","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"10.3233\/JIFS-223779_ref6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/ncomms12996","article-title":"The backtracking survey propagation algorithm for solving random K-SAT problems[J]","volume":"7","author":"Marino","year":"2016","journal-title":"Nature Communications"},{"issue":"4","key":"10.3233\/JIFS-223779_ref7","doi-asserted-by":"crossref","first-page":"17\u2013es","DOI":"10.1145\/1255443.1255445","article-title":"A new look at survey propagation and its generalizations[J]","volume":"54","author":"Maneva","year":"2007","journal-title":"Journal of the ACM (JACM)"},{"issue":"04","key":"10.3233\/JIFS-223779_ref8","first-page":"227","article-title":"Ant Colony Algorithm Combined with Survey Propagation for Satisfiability Problem[J]","volume":"39","author":"Fu","year":"2012","journal-title":"Computer Science"},{"issue":"3","key":"10.3233\/JIFS-223779_ref9","doi-asserted-by":"crossref","first-page":"036107","DOI":"10.1103\/PhysRevE.70.036107","article-title":"Minimizing energybelow the glass thresholds[J]","volume":"70","author":"Battaglia","year":"2004","journal-title":"Physical Review E"},{"key":"10.3233\/JIFS-223779_ref10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.2808","article-title":"Lee, Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem[J]","volume":"36","author":"Chieu","year":"2009","journal-title":"Jair Org"},{"key":"10.3233\/JIFS-223779_ref11","doi-asserted-by":"crossref","unstructured":"Marino R. , Learning from Survey Propagation: a Neural Network for MAX-E-3-SAT[J], Machine Learning: Science and Technology 2021.","DOI":"10.1088\/2632-2153\/ac0496"},{"issue":"7","key":"10.3233\/JIFS-223779_ref12","doi-asserted-by":"crossref","first-page":"2125","DOI":"10.1016\/j.automatica.2013.03.002","article-title":"Event based agreement protocols for multi-agent networks [J]","volume":"49","author":"Meng","year":"2013","journal-title":"Automatica"},{"issue":"05","key":"10.3233\/JIFS-223779_ref13","first-page":"849","article-title":"Survey propagation algorithm for SAT and its performance dominated by step length[J]","volume":"2005","author":"Shao","year":"2005","journal-title":"Chinese Journal of Computers"},{"issue":"12","key":"10.3233\/JIFS-223779_ref14","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1360\/N112016-00248","article-title":"Sufficient conditions for convergence of the survey propagation algorithm[J]","volume":"47","author":"Wang","year":"2017","journal-title":"Scientia Sinica Informationis"},{"issue":"05","key":"10.3233\/JIFS-223779_ref15","first-page":"1432","article-title":"Convergence analysis of survey propagation algorithm based on K-dimensional structure entropy [J]","volume":"39","author":"Liang","year":"2022","journal-title":"Application Research of Computers"},{"issue":"1","key":"10.3233\/JIFS-223779_ref16","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","article-title":"A sufficient condition for backtrack-free search","volume":"29","author":"Freuder","year":"1982","journal-title":"J. ACM"},{"key":"10.3233\/JIFS-223779_ref17","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","article-title":"Minors, Obstructions to tree-decomposition[J]","volume":"52","author":"Robertson","year":"1991","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"10.3233\/JIFS-223779_ref18","unstructured":"Chen H. , Quantified constraint satisfaction and bounded treewidth[C]\/\/ECAI , 16 (2004), 161."},{"issue":"4","key":"10.3233\/JIFS-223779_ref19","doi-asserted-by":"crossref","first-page":"042130","DOI":"10.1103\/PhysRevE.87.042130","article-title":"Balanced k-satisfiability and biased random k-satisfiability on trees[J]","volume":"87","author":"Krishnamurthy","year":"2013","journal-title":"Physical Review E"},{"issue":"05","key":"10.3233\/JIFS-223779_ref20","first-page":"51","article-title":"Algorithm of Graph and Its Application[J]","volume":"47","author":"Lei","year":"2020","journal-title":"Computer Science"},{"key":"10.3233\/JIFS-223779_ref21","doi-asserted-by":"crossref","unstructured":"J\u00e9gou P. , Ndiaye S.N. and Terrioux C. , Computing and exploiting tree-decompositions for solving constraint networks[C]\/\/International Conference on Principles and Practice of Constraint Programming, Springer, Berlin, Heidelberg (2005), 777\u2013781.","DOI":"10.1007\/11564751_63"},{"key":"10.3233\/JIFS-223779_ref22","unstructured":"J\u00e9gou P. and Terrioux C. , Bag-Connected Tree-Width: A New Parameter for Graph Decomposition[C]\/\/ISAIM, 2014."},{"key":"10.3233\/JIFS-223779_ref23","doi-asserted-by":"crossref","unstructured":"J\u00e9gou P. and Terrioux C. , Tree-decompositions with connected clusters for solving constraint networks[C]\/\/International Conference on Principles and Practice of Constraint Programming. Springer, Cham (2014), 407\u2013423.","DOI":"10.1007\/978-3-319-10428-7_31"},{"issue":"6","key":"10.3233\/JIFS-223779_ref24","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth[J]","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10.3233\/JIFS-223779_ref25","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree[J]","volume":"8","author":"Stefan","year":"1987","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"issue":"1","key":"10.3233\/JIFS-223779_ref26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1162\/089976600300015880","article-title":"Correctness of local probability propagation in graphical models with loops[J]","volume":"12","author":"Weiss","year":"2000","journal-title":"Neural Computation"},{"issue":"2","key":"10.3233\/JIFS-223779_ref27","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/s00493-016-3516-5","article-title":"Connected tree-width[J]","volume":"38","author":"Diestel","year":"2018","journal-title":"Combinatorica"},{"key":"10.3233\/JIFS-223779_ref28","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.dam.2021.02.039","article-title":"A polynomial time algorithm to compute the connected treewidth of a series\u2013 parallel graph[J]","volume":"312","author":"Mescoff","year":"2022","journal-title":"Discrete Applied Mathematics"},{"key":"10.3233\/JIFS-223779_ref29","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","article-title":"Survey propagation: an algorithm for satisfiability,","volume":"27","author":"Braunstein","year":"2005","journal-title":"Random Structures Algorithms"}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JIFS-223779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T08:53:36Z","timestamp":1769676816000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JIFS-223779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,2]]},"references-count":29,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/jifs-223779","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,2]]}}}