{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T12:52:27Z","timestamp":1779281547036,"version":"3.51.4"},"reference-count":45,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T00:00:00Z","timestamp":1520294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The ability to integrate information in the brain is considered to be an essential property for cognition and consciousness. Integrated Information Theory (IIT) hypothesizes that the amount of integrated information (   \u03a6   ) in the brain is related to the level of consciousness. IIT proposes that, to quantify information integration in a system as a whole, integrated information should be measured across the partition of the system at which information loss caused by partitioning is minimized, called the Minimum Information Partition (MIP). The computational cost for exhaustively searching for the MIP grows exponentially with system size, making it difficult to apply IIT to real neural data. It has been previously shown that, if a measure of    \u03a6    satisfies a mathematical property, submodularity, the MIP can be found in a polynomial order by an optimization algorithm. However, although the first version of    \u03a6    is submodular, the later versions are not. In this study, we empirically explore to what extent the algorithm can be applied to the non-submodular measures of    \u03a6    by evaluating the accuracy of the algorithm in simulated data and real neural data. We find that the algorithm identifies the MIP in a nearly perfect manner even for the non-submodular measures. Our results show that the algorithm allows us to measure    \u03a6    in large systems within a practical amount of time.<\/jats:p>","DOI":"10.3390\/e20030173","type":"journal-article","created":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T12:16:27Z","timestamp":1520338587000},"page":"173","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":46,"title":["Efficient Algorithms for Searching the Minimum Information Partition in Integrated Information Theory"],"prefix":"10.3390","volume":"20","author":[{"given":"Jun","family":"Kitazono","sequence":"first","affiliation":[{"name":"Araya, Inc., Toranomon 15 Mori Building, 2-8-10 Toranomon, Minato-ku, Tokyo 105-0001, Japan"},{"name":"Graduate School of Engineering, Kobe University, 1-1 Rokkodai-cho, Nada-ku, Kobe-shi, Hyogo 657-8501, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryota","family":"Kanai","sequence":"additional","affiliation":[{"name":"Araya, Inc., Toranomon 15 Mori Building, 2-8-10 Toranomon, Minato-ku, Tokyo 105-0001, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masafumi","family":"Oizumi","sequence":"additional","affiliation":[{"name":"Araya, Inc., Toranomon 15 Mori Building, 2-8-10 Toranomon, Minato-ku, Tokyo 105-0001, Japan"},{"name":"RIKEN Brain Science Institute, 2-1 Hirosawa Wako City, Saitama 351-0198, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,3,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"5033","DOI":"10.1073\/pnas.91.11.5033","article-title":"A measure for brain complexity: Relating functional segregation and integration in the nervous system","volume":"91","author":"Tononi","year":"1994","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Tononi, G. (2004). An information integration theory of consciousness. BMC Neurosci., 5.","DOI":"10.1186\/1471-2202-5-42"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.2307\/25470707","article-title":"Consciousness as integrated information: A provisional manifesto","volume":"215","author":"Tononi","year":"2008","journal-title":"Biol. Bull."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Oizumi, M., Albantakis, L., and Tononi, G. (2014). From the phenomenology to the mechanisms of consciousness: Integrated information theory 3.0. PLoS Comput. Biol., 10.","DOI":"10.1371\/journal.pcbi.1003588"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2228","DOI":"10.1126\/science.1117256","article-title":"Breakdown of cortical effective connectivity during sleep","volume":"309","author":"Massimini","year":"2005","journal-title":"Science"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"198ra105","DOI":"10.1126\/scitranslmed.3006294","article-title":"A theoretically based index of consciousness independent of sensory processing and behavior","volume":"5","author":"Casali","year":"2013","journal-title":"Sci. Transl. Med."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.concog.2008.10.005","article-title":"Propofol induction reduces the capacity for neural information integration: Implications for the mechanism of consciousness and general anesthesia","volume":"18","author":"Lee","year":"2009","journal-title":"Conscious. Cogn."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.3389\/fnhum.2012.00317","article-title":"Multivariate autoregressive models with exogenous inputs for intracerebral responses to direct electrical stimulation of the human brain","volume":"6","author":"Chang","year":"2012","journal-title":"Front. Hum. Neurosci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Boly, M., Sasai, S., Gosseries, O., Oizumi, M., Casali, A., Massimini, M., and Tononi, G. (2015). Stimulus set meaningfulness and neurophysiological differentiation: A functional magnetic resonance imaging study. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0125337"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1523\/ENEURO.0085-17.2017","article-title":"Conscious Perception as Integrated Information Patterns in Human Electrocorticography","volume":"4","author":"Haun","year":"2017","journal-title":"eNeuro"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Balduzzi, D., and Tononi, G. (2008). Integrated information in discrete dynamical systems: Motivation and theoretical framework. PLoS Comput. Biol., 4.","DOI":"10.1371\/journal.pcbi.1000091"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"14817","DOI":"10.1073\/pnas.1603583113","article-title":"Unified framework for information integration based on information geometry","volume":"113","author":"Oizumi","year":"2016","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Hidaka, S., and Oizumi, M. (arXiv, 2017). Fast and exact search for the partition with minimal information loss, arXiv.","DOI":"10.1371\/journal.pone.0201126"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01585863","article-title":"Minimizing symmetric submodular functions","volume":"82","author":"Queyranne","year":"1998","journal-title":"Math. Program."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"041907","DOI":"10.1103\/PhysRevE.81.041907","article-title":"Multivariate Granger causality and generalized variance","volume":"81","author":"Barrett","year":"2010","journal-title":"Phys. Rev. E"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Oizumi, M., Amari, S., Yanagawa, T., Fujii, N., and Tsuchiya, N. (2016). Measuring integrated information from the decoding perspective. PLoS Comput. Biol., 12.","DOI":"10.1371\/journal.pcbi.1004654"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Tegmark, M. (2016). Improved measures of integrated information. PLoS Comput. Biol., 12.","DOI":"10.1371\/journal.pcbi.1005123"},{"key":"ref_18","unstructured":"Ay, N. (2001). Information geometry on complexity and stochastic interaction. MIP MIS Preprint 95, Available online: http:\/\/www.mis.mpg.de\/publications\/preprints\/2001\/prepr2001-95.html."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2432","DOI":"10.3390\/e17042432","article-title":"Information geometry on complexity and stochastic interaction","volume":"17","author":"Ay","year":"2015","journal-title":"Entropy"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Amari, S., Tsuchiya, N., and Oizumi, M. (arXiv, 2017). Geometry of information integration, arXiv.","DOI":"10.1007\/978-3-319-97798-0_1"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2607","DOI":"10.1103\/PhysRevLett.57.2607","article-title":"Replica Monte Carlo simulation of spin-glasses","volume":"57","author":"Swendsen","year":"1986","journal-title":"Phys. Rev. Lett."},{"key":"ref_22","unstructured":"Geyer, C.J. (1991, January 21\u201324). Markov chain Monte Carlo maximum likelihood. Proceedings of the 23rd Symposium on the Interface, Seattle, WA, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1604","DOI":"10.1143\/JPSJ.65.1604","article-title":"Exchange Monte Carlo method and application to spin glass simulations","volume":"65","author":"Hukushima","year":"1996","journal-title":"J. Phys. Soc. Jpn."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3910","DOI":"10.1039\/b509983h","article-title":"Parallel tempering: Theory, applications, and new perspectives","volume":"7","author":"Earl","year":"2005","journal-title":"Phys. Chem. Chem. Phys."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Burnham, K.P., and Anderson, D.R. (2003). Model Selection and Multimodel Inference: A Practical Information-Theoretic Approach, Springer.","DOI":"10.1007\/b97636"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1147\/rd.41.0066","article-title":"Information theoretical analysis of multivariate correlation","volume":"4","author":"Watanabe","year":"1960","journal-title":"IBM J. Res. Dev."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Studen\u00fd, M., and Vejnarov\u00e1, J. (1999). The Multiinformation Function as a Tool For Measuring Stochastic Dependence, MIT Press.","DOI":"10.1007\/978-94-011-5014-9_10"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pearl, J. (2009). Causality, Cambridge University Press.","DOI":"10.1017\/CBO9780511803161"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","article-title":"Submodular function minimization","volume":"112","author":"Iwata","year":"2008","journal-title":"Math. Program."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1093\/biomet\/20A.1-2.32","article-title":"The generalised product moment distribution in samples from a normal multivariate population","volume":"20A","author":"Wishart","year":"1928","journal-title":"Biometrika"},{"key":"ref_31","unstructured":"Bishop, C.M. (2006). Pattern Recognition and Machine Learning, Springer."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1142\/S0129183198000443","article-title":"Number of magic squares from parallel tempering Monte Carlo","volume":"9","author":"Pinn","year":"1998","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0010-4655(02)00207-2","article-title":"Extended ensemble Monte Carlo approach to hardly relaxing problems","volume":"147","author":"Hukushima","year":"2002","journal-title":"Computer Phys. Commun."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"25","DOI":"10.2197\/ipsjtrans.8.25","article-title":"An Exhaustive Search and Stability of Sparse Estimation for Feature Selection Problem","volume":"8","author":"Nagata","year":"2015","journal-title":"IPSJ Online Trans."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Nagasaka, Y., Shimoda, K., and Fujii, N. (2011). Multidimensional recording (MDR) and data sharing: an ecological open research and educational platform for neuroscience. PLoS ONE, 6.","DOI":"10.1371\/journal.pone.0022561"},{"key":"ref_36","unstructured":"Toker, D., and Sommer, F. (arXiv, 2017). Information Integration in Large Brain Networks, arXiv."},{"key":"ref_37","unstructured":"Kitazono, J., and Oizumi, M. (2018, March 06). phi_toolbox.zip, version 6; Figshare. Available online: https:\/\/figshare.com\/articles\/phi_toolbox_zip\/3203326\/6."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"066120","DOI":"10.1103\/PhysRevE.70.066120","article-title":"Clustering analysis of the ground-state structure of the vertex-cover problem","volume":"70","author":"Barthel","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1142\/S0129183109013893","article-title":"Parallel tempering for the traveling salesman problem","volume":"20","author":"Wang","year":"2009","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"024111","DOI":"10.1063\/1.1831273","article-title":"Optimal allocation of replicas in parallel tempering simulations","volume":"122","author":"Rathore","year":"2005","journal-title":"J. Chem. Phys."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0009-2614(99)01123-9","article-title":"Replica-exchange molecular dynamics method for protein folding","volume":"314","author":"Sugita","year":"1999","journal-title":"Chem. Phys. Lett."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"6911","DOI":"10.1063\/1.1507776","article-title":"On the acceptance probability of replica-exchange Monte Carlo trials","volume":"117","author":"Kofke","year":"2002","journal-title":"J. Chem. Phys."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"244111","DOI":"10.1063\/1.3603964","article-title":"Comparison of two adaptive temperature-based replica exchange methods applied to a sharp phase transition of protein unfolding-folding","volume":"134","author":"Lee","year":"2011","journal-title":"J. Chem. Phys."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1214\/ss\/1177011136","article-title":"Inference from iterative simulation using multiple sequences","volume":"7","author":"Gelman","year":"1992","journal-title":"Stat. Sci."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1080\/10618600.1998.10474787","article-title":"General methods for monitoring convergence of iterative simulations","volume":"7","author":"Brooks","year":"1998","journal-title":"J. Comput. Graph. Stat."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/3\/173\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:57:44Z","timestamp":1760194664000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/3\/173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,6]]},"references-count":45,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,3]]}},"alternative-id":["e20030173"],"URL":"https:\/\/doi.org\/10.3390\/e20030173","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,6]]}}}