{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:48:53Z","timestamp":1762868933540,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T00:00:00Z","timestamp":1663718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Henry and Emma Meyer Chair in Molecular Genetics"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Extraction of subsets of highly connected nodes (\u201ccommunities\u201d or modules) is a standard step in the analysis of complex social and biological networks. We here consider the problem of finding a relatively small set of nodes in two labeled weighted graphs that is highly connected in both. While many scoring functions and algorithms tackle the problem, the typically high computational cost of permutation testing required to establish the p-value for the observed pattern presents a major practical obstacle. To address this problem, we here extend the recently proposed CTD (\u201cConnect the Dots\u201d) approach to establish information-theoretic upper bounds on the p-values and lower bounds on the size and connectedness of communities that are detectable. This is an innovation on the applicability of CTD, broadening its use to pairs of graphs.<\/jats:p>","DOI":"10.3390\/e24101329","type":"journal-article","created":{"date-parts":[[2022,9,21]],"date-time":"2022-09-21T21:22:23Z","timestamp":1663795343000},"page":"1329","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Information-Theoretic Bound on p-Values for Detecting Communities Shared between Weighted Labeled Graphs"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8570-053X","authenticated-orcid":false,"given":"Predrag","family":"Obradovic","sequence":"first","affiliation":[{"name":"School of Electrical Engineering, University of Belgrade, 11000 Belgrade, Serbia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9843-6261","authenticated-orcid":false,"given":"Vladimir","family":"Kova\u010devi\u0107","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering, University of Belgrade, 11000 Belgrade, Serbia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0875-8337","authenticated-orcid":false,"given":"Xiqi","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Molecular and Human Genetics, Baylor College of Medicine, Houston, TX 77030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5482-2825","authenticated-orcid":false,"given":"Aleksandar","family":"Milosavljevic","sequence":"additional","affiliation":[{"name":"Department of Molecular and Human Genetics, Baylor College of Medicine, Houston, TX 77030, USA"},{"name":"Quantitative and Computational Biosciences Program, Baylor College of Medicine, Houston, TX 77030, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Phys. Rep."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chintalapudi, S.R., and Prasad, M.H.M.K. (2017, January 22\u201323). Network Entropy Based Overlapping Community Detection in Social Networks. Proceedings of the Second International Conference on Internet of Things, Data and Cloud Computing, ICC \u201917, Cambridge, UK.","DOI":"10.1145\/3018896.3025161"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Cruz, J.D., Bothorel, C., and Poulet, F. (2011, January 19\u201321). Entropy based community detection in augmented social networks. Proceedings of the 2011 International Conference on Computational Aspects of Social Networks (CASoN), Salamanca, Spain.","DOI":"10.1109\/CASON.2011.6085937"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Thistlethwaite, L.R., Petrosyan, V., Li, X., Miller, M.J., Elsea, S.H., and Milosavljevic, A. (2021). CTD: An information-theoretic algorithm to interpret sets of metabolomic and transcriptomic perturbations in the context of graphical models. PLoS Comput. Biol., 17.","DOI":"10.1371\/journal.pcbi.1009551"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6556","DOI":"10.1038\/s41598-022-10415-5","article-title":"Clinical diagnosis of metabolic disorders using untargeted metabolomic profiling and disease-specific networks learned from profiling data","volume":"12","author":"Thistlethwaite","year":"2022","journal-title":"Sci. Rep."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Milosavljevic, S., Glinton, K.E., Li, X., Medeiros, C., Gillespie, P., Seavitt, J.R., Graham, B.H., and Elsea, S.H. (2022). Untargeted Metabolomics of Slc13a5 Deficiency Reveal Critical Liver\u2013Brain Axis for Lipid Homeostasis. Metabolites, 12.","DOI":"10.3390\/metabo12040351"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2812","DOI":"10.1021\/ci400326p","article-title":"ReactionMap: An efficient atom-mapping algorithm for chemical reactions","volume":"53","author":"Fooshee","year":"2013","journal-title":"J. Chem. Inf. Model."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"i47","DOI":"10.1093\/bioinformatics\/bti1007","article-title":"Protein function prediction via graph kernels","volume":"21","author":"Borgwardt","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_9","unstructured":"Kraft, L.G. (1949). A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses. [Ph.D. Thesis, Massachusetts Institute of Technology]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1109\/TIT.1956.1056818","article-title":"Two inequalities implied by unique decipherability","volume":"2","author":"McMillan","year":"1956","journal-title":"IRE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bioinformatics\/9.4.407","article-title":"Discovering simple DNA sequences by the algorithmic significance method","volume":"9","author":"Jurka","year":"1993","journal-title":"Bioinformatics"},{"key":"ref_12","first-page":"290","article-title":"On Random Graphs I","volume":"6","year":"1959","journal-title":"Publ. Math. Debr."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Belda, J., Vergara, L., Safont, G., Salazar, A., and Parcheta, Z. (2019). A new surrogating algorithm by the complex graph Fourier transform (CGFT). Entropy, 21.","DOI":"10.3390\/e21080759"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hagberg, A., Swart, P., and S Chult, D. (2008). Exploring Network Structure, Dynamics, and Function Using NetworkX, Technical Report.","DOI":"10.25080\/TCWV9851"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Bastian, M., Heymann, S., and Jacomy, M. (2009, January 17\u201320). Gephi: An open source software for exploring and manipulating networks. Proceedings of the International AAAI Conference on Web and Social Media, San Jose, CA, USA.","DOI":"10.1609\/icwsm.v3i1.13937"},{"key":"ref_16","first-page":"278","article-title":"Portable workflow and tool descriptions with the CWL (Common Workflow Language)","volume":"1","author":"Amstutz","year":"2015","journal-title":"F1000Research"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"e3","DOI":"10.1158\/0008-5472.CAN-17-0387","article-title":"The Cancer Genomics Cloud: Collaborative, reproducible, and democratized\u2014A new paradigm in large-scale computational research","volume":"77","author":"Lau","year":"2017","journal-title":"Cancer Res."},{"key":"ref_18","first-page":"2","article-title":"Docker: Lightweight linux containers for consistent development and deployment","volume":"2014","author":"Merkel","year":"2014","journal-title":"Linux J."},{"key":"ref_19","unstructured":"Petrosyan, V., Dobrolecki, L.E., Thistlethwaite, L., Lewis, A.N., Sallas, C., Srinivasan, R.R., Lei, J.T., Kovacevic, V., Obradovic, P., and Ellis, M.J. Identifying Biomarkers of Differential Chemotherapy Response in Patient Derived Xenografts of Triple-Negative Breast Cancer with a CTD\/WGCNA Approach, In review."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A Formal Basis for the Heuristic Determination of Minimum Cost Paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1329\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:36:55Z","timestamp":1760143015000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1329"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,21]]},"references-count":20,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["e24101329"],"URL":"https:\/\/doi.org\/10.3390\/e24101329","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,9,21]]}}}