Fast and exact search for the partition with minimal information loss
Open accessThe DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Abstract
In analysis of multi-component complex systems, such as neural systems, identifying groups of units that share similar functionality will aid understanding of the underlying structures of the system. To find such a grouping, it is useful to evaluate to what extent the units of the system are separable. Separability or inseparability can be evaluated by quantifying how much information would be lost if the system were partitioned into subsystems, and the interactions between the subsystems were hypothetically removed. A system of two independent subsystems are completely separable without any loss of information while a system of strongly interacted subsystems cannot be separated without a large loss of information. Among all the possible partitions of a system, the partition that minimizes the loss of information, called the Minimum Information Partition (MIP), can be considered as the optimal partition for characterizing the underlying structures of the system. Although the MIP would reveal novel characteristics of the neural system, an exhaustive search for the MIP is numerically intractable due to the combinatorial explosion of possible partitions. Here, we propose a computationally efficient search to precisely identify the MIP among all possible partitions by exploiting the submodularity of the measure of information loss, when the measure of information loss is submodular. Submodularity is a mathematical property of set functions which is analogous to convexity in continuous functions. Mutual information is one such submodular information loss function, and is a natural choice for measuring the degree of statistical dependence between paired sets of random variables. By using mutual information as a loss function, we show that the search for MIP can be performed in a practical order of computational time for a reasonably large system (N = 100 ∼ 1000). We also demonstrate that MIP search allows for the detection of underlying global structures in a network of nonlinear oscillators.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An information integration theory of consciousness
Tononi, G. (2004) · BMC Neuroscience · doi:10.1186/1471-2202-5-42 · Cited by 1,958 · cited 6×
“The concept of the partition with minimal information loss originated from Integrated Information Theory (IIT) [9–11] and the partition with minimal information loss is called “Minimum Information Partition (MIP)”.”
InfluentialFrom the phenomenology to the mechanisms of consciousness: integrated information theory 3.0
Oizumi, M., Albantakis, L., & Tononi, G. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003588 · Cited by 1,128
Self-citationIntegrated information in discrete dynamical systems: motivation and theoretical framework
Balduzzi, D., & Tononi, G. (2008) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000091 · Cited by 419
Practical Measures of Integrated Information for Time-Series Data
Barrett, A. B., & Seth, A. K. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1001052 · Cited by 225
Measuring Integrated Information from the Decoding Perspective
Oizumi, M., Amari, S.-I., Yanagawa, T., Fujii, N., & Tsuchiya, N. (2016) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004654 · Cited by 184
Self-citationImproved measures of integrated information
Tegmark, M. (2016) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1005123 · Cited by 128 · cited 1×
“The specific role of this authoris articulated in the ‘author contributions’ section.”
Cited by
Measuring integrated information: comparison of candidate measures in theory and simulation
Mediano, P., Seth, A., & Barrett, A. (2018) · Entropy · doi:10.3390/e21010017 · Cited by 145
“ka and Oizumi make use of the submodularity of mutual information to perform ecient optimisation and nd the bipartition across which there is the least instantaneous mutual information of the system [21]. Presently, however, their method is valid only for instantaneous mutual information and is therefore not applicabl…”
MethodA measure centrality index for systematic empirical comparison of consciousness theories
Chis-Ciure, R., Melloni, L., & Northoff, G. (2024) · Neuroscience & Biobehavioral Reviews · doi:10.1016/j.neubiorev.2024.105670 · Cited by 22
“…et al., 2022; Rosas et al., 2020) Simplification/generalization procedures: approximate factorizations (Tegmark, 2016), Queraynne ’ s algorithm (Hidaka and Oizumi, 2018; Kitazono et al., 2018), graph clustering (Toker and Sommer, 2019), shared transitions in Process Algebras (Bolognesi, 2019),…”
MethodAn implementation of integrated information theory in resting-state fMRI
Nemirovsky, I. E., Popiel, N. J. M., Rudas, J., Caius, M., Naci, L., Schiff, N. D., Owen, A. M., & Soddu, A. (2023) · Communications Biology · doi:10.1038/s42003-023-05063-y · Cited by 15
Integrated information as a measure of cognitive processes in coupled genetic repressilators
Abrego, L., & Zaikin, A. (2019) · Entropy · doi:10.3390/e21040382 · Cited by 5
“Finally, for the integrated information measures were computed using the ’Practical PHI toolbox’ and we apply the Queyranne algorithm [13,14,48,49] for the MIB search.”
Method
Metadata
- Authors
- Hidaka, S., & Oizumi, M.
- Venue
- PLOS ONE
- Publisher
- Public Library of Science (PLoS)
- Published
- 2018-09-11
- Volume
- 13
- Issue
- 9
- Pages
- e0201126
- ISSN
- 1932-6203 (ISSN-L)
- OpenAlex
- W2742811494
- Cited by
- 32
- References
- 6
- FWCI
- 1.81
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Fast and exact search for the partition with minimal information loss. https://app.cochat.ai/papers/10.1371/journal.pone.0201126
- The paper
- Hidaka, S., & Oizumi, M. (2018). Fast and exact search for the partition with minimal information loss. PLOS ONE. https://doi.org/10.1371/journal.pone.0201126
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.