{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T19:18:25Z","timestamp":1780773505549,"version":"3.54.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T00:00:00Z","timestamp":1728086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T00:00:00Z","timestamp":1728086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP210100227"],"award-info":[{"award-number":["DP210100227"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","award":["PGC2018-099402-B-I00"],"award-info":[{"award-number":["PGC2018-099402-B-I00"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011941","name":"Gobierno del Principado de Asturias","doi-asserted-by":"publisher","award":["BP21048"],"award-info":[{"award-number":["BP21048"]}],"id":[{"id":"10.13039\/100011941","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Random generation of fuzzy measures plays a pivotal role in large-scale decision-making and optimization. Random walks ensure uniform generation and adequate coverage. The M\u00f6bius representation of set functions is a valuable tool for establishing the sparse structure of fuzzy measures, with its non-negativity closely linked to monotonicity and convexity\/supermodularity checking. We propose three efficient methods for monotonicity verification and convexity\/supermodularity verification applicable to random walks in M\u00f6bius representations, specifically tailored for universal sets larger than ten inputs and <jats:italic>k<\/jats:italic>-order fuzzy measures. We first present the baseline methods by directly inspecting monotonicity and convexity constraints. Building on the observation that the majority of initially generated values exhibit non-negativity, we intentionally track negative M\u00f6bius values to enhance the computational performance of these baseline approaches. Further, we introduce the more agile methods that employ insertion and merge sorting techniques for both monotonicity and convexity checks in random walks that involve small perturbations of fuzzy measures. To address sparsity in large-scale scenarios, we focus on two major types of measures: <jats:italic>k<\/jats:italic>-additive and <jats:italic>k<\/jats:italic>-interactive measures, demonstrating their effectiveness through theoretical analysis and experimental results.<\/jats:p>","DOI":"10.1007\/s40314-024-02951-9","type":"journal-article","created":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T08:01:47Z","timestamp":1728115307000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient random walks for generating random fuzzy measures in M\u00f6bius representation in large universe"],"prefix":"10.1007","volume":"43","author":[{"given":"Gleb","family":"Beliakov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan","family":"Baz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian-Zhang","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,10,5]]},"reference":[{"key":"2951_CR1","unstructured":"Beliakov G (2021) Rfmtool package, version 4, https:\/\/personal-sites.deakin.edu.au\/~gleb\/fmtools.html. https:\/\/CRAN.R-project.org\/package=Rfmtool"},{"key":"2951_CR2","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.ins.2020.08.113","volume":"546","author":"G Beliakov","year":"2021","unstructured":"Beliakov G (2021) On the derivatives of set functions in matrix representation. Inf Sci 546:469\u2013480","journal-title":"Inf Sci"},{"key":"2951_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/j.ejor.2021.11.004","volume":"301","author":"G Beliakov","year":"2021","unstructured":"Beliakov G (2021) Knapsack problems with dependencies through non-additive measures and Choquet integral. Eur J Oper Res 301:277\u2013286","journal-title":"Eur J Oper Res"},{"key":"2951_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1109\/TFUZZ.2020.3036699","volume":"30","author":"G Beliakov","year":"2022","unstructured":"Beliakov G (2022) On random generation of supermodular capacities. IEEE Trans Fuzzy Syst 30:293\u2013296","journal-title":"IEEE Trans Fuzzy Syst"},{"key":"2951_CR5","doi-asserted-by":"publisher","first-page":"2849","DOI":"10.1002\/int.22609","volume":"37","author":"G Beliakov","year":"2021","unstructured":"Beliakov G, James S (2021) Choquet integral based measures of economic welfare and species diversity. Int J Intell Syst 37:2849\u20132867","journal-title":"Int J Intell Syst"},{"key":"2951_CR6","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.ins.2019.04.042","volume":"494","author":"G Beliakov","year":"2019","unstructured":"Beliakov G, Wu J-Z (2019) Learning fuzzy measures from data: simplifications and optimisation strategies. Inf Sci 494:100\u2013113","journal-title":"Inf Sci"},{"key":"2951_CR7","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.ins.2021.07.017","volume":"577","author":"G Beliakov","year":"2021","unstructured":"Beliakov G, Wu J-Z (2021) Random generation of capacities and its application in comprehensive decision aiding. Inf Sci 577:424\u2013435","journal-title":"Inf Sci"},{"key":"2951_CR8","doi-asserted-by":"publisher","first-page":"1159","DOI":"10.1109\/TFUZZ.2023.3318631","volume":"32","author":"G Beliakov","year":"2024","unstructured":"Beliakov G, Wu J-Z (2024) Discrete Choquet integral optimisation with positive and negative interactions. IEEE Trans Fuzzy Syst 32:1159\u20131166","journal-title":"IEEE Trans Fuzzy Syst"},{"issue":"7","key":"2951_CR9","doi-asserted-by":"publisher","first-page":"4205","DOI":"10.1109\/TFUZZ.2024.3384954","volume":"32","author":"G Beliakov","year":"2024","unstructured":"Beliakov G, Wu J-Z (2024) An efficient algorithm for sampling fuzzy measures. IEEE Trans Fuzzy Syst 32(7):4205\u20134208","journal-title":"IEEE Trans Fuzzy Syst"},{"issue":"3","key":"2951_CR10","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1109\/TFUZZ.2011.2123899","volume":"19","author":"G Beliakov","year":"2011","unstructured":"Beliakov G, James S, Li G (2011) Learning Choquet-integral-based metrics for semisupervised clustering. IEEE Trans Fuzzy Syst 19(3):562\u2013574","journal-title":"IEEE Trans Fuzzy Syst"},{"issue":"4","key":"2951_CR11","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/02331934.2013.836645","volume":"64","author":"G Beliakov","year":"2015","unstructured":"Beliakov G, Li G, Liu S (2015) Parallel bucket sorting on graphics processing units based on convex optimization. Optimization 64(4):1033\u20131055","journal-title":"Optimization"},{"key":"2951_CR12","volume-title":"Discrete fuzzy measures: computational aspects","author":"G Beliakov","year":"2019","unstructured":"Beliakov G, James S, Wu J-Z (2019) Discrete fuzzy measures: computational aspects. Springer, Berlin, Heidelberg"},{"issue":"9","key":"2951_CR13","doi-asserted-by":"publisher","first-page":"3979","DOI":"10.1109\/TFUZZ.2021.3135972","volume":"30","author":"G Beliakov","year":"2022","unstructured":"Beliakov G, Cao T, Mak-Hau V (2022) Aggregation of interacting criteria in land combat vehicle selection by using fuzzy measures. IEEE Trans Fuzzy Syst 30(9):3979\u20133989. https:\/\/doi.org\/10.1109\/TFUZZ.2021.3135972","journal-title":"IEEE Trans Fuzzy Syst"},{"key":"2951_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2024.102295","volume":"106","author":"G Beliakov","year":"2024","unstructured":"Beliakov G, Wu J-Z, Ding W (2024) Representation, optimization and generation of fuzzy measures. Inf Fusion 106:102295","journal-title":"Inf Fusion"},{"key":"2951_CR15","doi-asserted-by":"publisher","unstructured":"Beliakov G, James S, Wu J-Z (2024) Efficient monotonicity and convexity checks for randomly sampled fuzzy measures. IEEE Trans Fuzzy Syst. https:\/\/doi.org\/10.1109\/TFUZZ.2024.3462737","DOI":"10.1109\/TFUZZ.2024.3462737"},{"issue":"3","key":"2951_CR16","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0165-4896(89)90056-5","volume":"17","author":"A Chateauneuf","year":"1989","unstructured":"Chateauneuf A, Jaffray J-Y (1989) Some characterizations of lower probabilities and other monotone capacities through the use of M\u00f6bius inversion. Math Soc Sci 17(3):263\u2013283","journal-title":"Math Soc Sci"},{"key":"2951_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.5802\/aif.53","volume":"5","author":"G Choquet","year":"1954","unstructured":"Choquet G (1954) Theory of capacities. Annales de l\u2019institut Fourier 5:131\u2013295","journal-title":"Annales de l\u2019institut Fourier"},{"issue":"10","key":"2951_CR18","doi-asserted-by":"publisher","first-page":"3046","DOI":"10.1016\/j.cor.2005.02.034","volume":"33","author":"EF Combarro","year":"2006","unstructured":"Combarro EF, Miranda P (2006) Identification of fuzzy measures from sample data with genetic algorithms. Comput Oper Res 33(10):3046\u20133066","journal-title":"Comput Oper Res"},{"key":"2951_CR19","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.ins.2019.05.079","volume":"501","author":"EF Combarro","year":"2019","unstructured":"Combarro EF, Saracho JH, D\u00edaz I (2019) Minimals plus: an improved algorithm for the random generation of linear extensions of partially ordered sets. Inf Sci 501:50\u201367","journal-title":"Inf Sci"},{"key":"2951_CR20","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01589108","volume":"45","author":"G Gallo","year":"1989","unstructured":"Gallo G, Simeone B (1989) On the supermodular knapsack problem. Math Program 45:295\u2013309","journal-title":"Math Program"},{"issue":"6","key":"2951_CR21","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0167-8655(96)00020-7","volume":"17","author":"M Grabisch","year":"1996","unstructured":"Grabisch M (1996) The representation of importance and interaction of features by fuzzy measures. Pattern Recogn Lett 17(6):567\u2013575","journal-title":"Pattern Recogn Lett"},{"issue":"2","key":"2951_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0165-0114(97)00168-1","volume":"92","author":"M Grabisch","year":"1997","unstructured":"Grabisch M (1997) k-order additive discrete fuzzy measures and their representation. Fuzzy Sets Syst 92(2):167\u2013189","journal-title":"Fuzzy Sets Syst"},{"key":"2951_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30690-2","volume-title":"Set functions. Games and capacities in decision making","author":"M Grabisch","year":"2016","unstructured":"Grabisch M (2016) Set functions. Games and capacities in decision making. Springer, Berlin, New York"},{"issue":"2","key":"2951_CR24","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1016\/j.ejor.2007.02.025","volume":"186","author":"M Grabisch","year":"2008","unstructured":"Grabisch M, Kojadinovic I, Meyer P (2008) A review of methods for capacity identification in Choquet integral based multi-attribute utility theory: applications of the Kappalab R package. Eur J Oper Res 186(2):766\u2013785","journal-title":"Eur J Oper Res"},{"key":"2951_CR25","doi-asserted-by":"crossref","unstructured":"Grabisch M, Labreuche C, Sun P (2023) An approximation algorithm for random generation of capacities. Order, 1\u201326","DOI":"10.1007\/s11083-023-09630-0"},{"key":"2951_CR26","doi-asserted-by":"publisher","first-page":"2864","DOI":"10.1109\/TFUZZ.2019.2945243","volume":"28","author":"P Miranda","year":"2020","unstructured":"Miranda P, Garc\u00eda-Segador P (2020) Combinatorial structure of the polytope of 2-additive measures. IEEE Trans Fuzzy Syst 28:2864\u20132874","journal-title":"IEEE Trans Fuzzy Syst"},{"key":"2951_CR27","volume-title":"Fair division and collective welfare","author":"H Moulin","year":"2004","unstructured":"Moulin H (2004) Fair division and collective welfare. MIT Press, Cambridge"},{"key":"2951_CR28","volume-title":"Game Theory","author":"G Owen","year":"1982","unstructured":"Owen G (1982) Game Theory. Academic Press, London"},{"key":"2951_CR29","unstructured":"Peters T (2002) Timsort algorithm https:\/\/svn.python.org\/projects\/python\/trunk\/Objects\/listsort.txt"},{"key":"2951_CR30","doi-asserted-by":"publisher","DOI":"10.1002\/9781118799635","volume-title":"An introduction to probability and statistics","author":"VK Rohatgi","year":"2015","unstructured":"Rohatgi VK, Saleh AME (2015) An introduction to probability and statistics. John Wiley & Sons, New York"},{"key":"2951_CR31","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1016\/j.jpdc.2008.05.012","volume":"68","author":"E Sintorn","year":"2008","unstructured":"Sintorn E, Assarson U (2008) Fast parallel GPU-sorting using a hybrid algorithm. J Parallel Distrib Comput 68:1381\u20131388","journal-title":"J Parallel Distrib Comput"},{"key":"2951_CR32","volume-title":"Generalized measure theory","author":"Z Wang","year":"2010","unstructured":"Wang Z, Klir GJ (2010) Generalized measure theory. Springer, New York"},{"key":"2951_CR33","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1016\/j.ins.2018.08.007","volume":"467","author":"J-Z Wu","year":"2018","unstructured":"Wu J-Z, Beliakov G (2018) Nonadditivity index and capacity identification method in the context of multicriteria decision making. Inf Sci 467:398\u2013406","journal-title":"Inf Sci"},{"key":"2951_CR34","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.ins.2019.04.025","volume":"492","author":"J-Z Wu","year":"2019","unstructured":"Wu J-Z, Beliakov G (2019) Nonmodularity index for capacity identifying with multiple decision criteria. Inf Sci 492:164\u2013180","journal-title":"Inf Sci"},{"issue":"3","key":"2951_CR35","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1002\/int.22209","volume":"35","author":"J-Z Wu","year":"2020","unstructured":"Wu J-Z, Beliakov G (2020) Marginal contribution representation of capacity based multicriteria decision making. Int J Intell Syst 35(3):373\u2013400","journal-title":"Int J Intell Syst"},{"issue":"6","key":"2951_CR36","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1109\/TFUZZ.2015.2403851","volume":"23","author":"J-Z Wu","year":"2015","unstructured":"Wu J-Z, Yang S, Zhang Q, Ding S (2015) 2-additive capacity identification methods from multicriteria correlation preference information. IEEE Trans Fuzzy Syst 23(6):2094\u20132106","journal-title":"IEEE Trans Fuzzy Syst"},{"key":"2951_CR37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.120080","volume":"659","author":"J-Z Wu","year":"2024","unstructured":"Wu J-Z, Beliakov G, James S, Gagolewski M (2024) Random generation of linearly constrained fuzzy measures and domain coverage performance evaluation. Inf Sci 659:120080","journal-title":"Inf Sci"},{"key":"2951_CR38","doi-asserted-by":"publisher","first-page":"185543","DOI":"10.1109\/ACCESS.2019.2960539","volume":"7","author":"R-J Xi","year":"2019","unstructured":"Xi R-J, Wu Z-J, Beliakov G (2019) Matrix representation of capacity-based multicriteria decision analysis. IEEE Access 7:185543\u2013185553","journal-title":"IEEE Access"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-024-02951-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-024-02951-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-024-02951-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T09:04:57Z","timestamp":1730106297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-024-02951-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,5]]},"references-count":38,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["2951"],"URL":"https:\/\/doi.org\/10.1007\/s40314-024-02951-9","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"value":"2238-3603","type":"print"},{"value":"1807-0302","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,5]]},"assertion":[{"value":"11 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 October 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no Conflict of interest in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"430"}}