{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:42:35Z","timestamp":1760211755249,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,7,29]],"date-time":"2016-07-29T00:00:00Z","timestamp":1469750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the problem of estimating the measure of subsets in very large networks. A prime tool for this purpose is the Markov Chain Monte Carlo (MCMC) algorithm. This algorithm, while extremely useful in many cases, still often suffers from the drawback of very slow convergence. We show that in a special, but important case, it is possible to obtain significantly better bounds on the convergence rate. This special case is when the huge state space can be aggregated into a smaller number of clusters, in which the states behave approximately the same way (but their behavior still may not be identical). A Markov chain with this structure is called quasi-lumpable. This property allows the aggregation of states (nodes) into clusters. Our main contribution is a rigorously proved bound on the rate at which the aggregated state distribution approaches its limit in quasi-lumpable Markov chains. We also demonstrate numerically that in certain cases this can indeed lead to a significantly accelerated way of estimating the measure of subsets. The result can be a useful tool in the analysis of complex networks, whenever they have a clustering that aggregates nodes with similar (but not necessarily identical) behavior.<\/jats:p>","DOI":"10.3390\/a9030050","type":"journal-article","created":{"date-parts":[[2016,7,29]],"date-time":"2016-07-29T10:40:24Z","timestamp":1469788824000},"page":"50","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms"],"prefix":"10.3390","volume":"9","author":[{"given":"Ahmad","family":"Askarian","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75081, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9079-2915","authenticated-orcid":false,"given":"Rupei","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75081, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Farag\u00f3","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75081, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,7,29]]},"reference":[{"key":"ref_1","first-page":"4","article-title":"The Best of the 20th Century: Editors Name Top 10 Algorithms","volume":"33","author":"Cipra","year":"2000","journal-title":"SIAM News"},{"key":"ref_2","unstructured":"Farag\u00f3, A. (2006, January 26\u201329). Speeeding Up Markov Chain Monte Carlo Algorithm. Proceedings of the International Conference on Foundations of Computer Science (FCS\u201906), Las Vegas, NV, USA."},{"key":"ref_3","unstructured":"Farag\u00f3, A. (2006, January 21\u201322). On the Convergence Rate of Quasi Lumpable Markov Chains. Proceedings of the 3rd European Performance Engineering Workshop (EPEW\u201906), Budapest, Hungary."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1214\/aoap\/1177005872","article-title":"Loss Networks","volume":"1","author":"Kelly","year":"1991","journal-title":"Ann. Appl. Prob."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(94)90293-3","article-title":"Computational Complexity of Loss Networks","volume":"125","author":"Louth","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sinclair, A. (1993). Algorithms for Random Generation and Counting, Birkh\u00e4user.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"ref_7","unstructured":"Kemeny, J.G., and Snell, J.L. (1960). Finite Markov Chains, Van Nostrand Reinhold."},{"key":"ref_8","unstructured":"Lee, C.P.-C., Golub, G.H., and Zenios, S.A. (2003). A Fast Two-Stage Algorithm for Computing PageRank and Its Extensions, Scientific Computation and Computational Mathematics, Stanford University. Technical Report SCCM-2003-15."},{"key":"ref_9","first-page":"937","article-title":"PageRank Problem, Survey And Future, Research Directions","volume":"5","author":"Sargolzaei","year":"2010","journal-title":"Int. Math. Forum"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1137\/S0895479895294277","article-title":"Quasi Lumpability, Lower Bounding Coupling Matrices, and Nearly Completely Decomposable Markov Chains","volume":"18","author":"Dayar","year":"1997","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-5316(94)90015-9","article-title":"Bounds for Quasi-Lumpable Markov Chains","volume":"20","author":"Franceschinis","year":"1994","journal-title":"Perform. Eval."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kijima, M. (1997). Markov Processes for Stochastic Modeling, Chapman & Hall.","DOI":"10.1007\/978-1-4899-3132-0"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hartfiel, D.J. (1998). Markov Set-Chains, Springer-Verlag. Lecture Notes in Mathematics 1695.","DOI":"10.1007\/BFb0094586"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0024-3795(93)90261-L","article-title":"Results on Limiting Sets of Markov Set-Chains","volume":"195","author":"Hartfiel","year":"1993","journal-title":"Linear Algebra Appl."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Mazumdar, R.R. (2013). Performance Modeling, Stochastic Networks, and Statistical Multiplexing, Morgan & Claypool.","DOI":"10.1007\/978-3-031-79260-1"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ross, K.W. (1995). Multiservice Loss Models for Broadband Telecommunication Networks, Springer.","DOI":"10.1007\/978-1-4471-2126-8"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/50\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:27:22Z","timestamp":1760210842000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,29]]},"references-count":16,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["a9030050"],"URL":"https:\/\/doi.org\/10.3390\/a9030050","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,7,29]]}}}