Inferring pattern generators on networks. (English) Zbl 1527.62047
Summary: Given a pattern on a network, i.e. a subset of nodes, can we assess, whether they are randomly distributed on the network or have been generated in a systematic fashion following the network architecture? This question is at the core of network-based data analyses across a range of disciplines – from incidents of infection in social networks to sets of differentially expressed genes in biological networks. Here we introduce generic ‘pattern generators’ based on an Eden growth model. We assess the capacity of different pattern measures like connectivity, edge density or various average distances, to infer the parameters of the generator from the observed patterns. Some measures perform consistently better than others in inferring the underlying pattern generator, while the best performing measures depend on the global topology of the underlying network. Moreover, we show that pattern generator inference remains possible in case of limited visibility of the patterns.
MSC:
| 62H99 | Multivariate analysis |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
Keywords:
patterns; network clusters; teleportation random walks; Eden model; parametric inference; mutual informationSoftware:
STRINGReferences:
| [1] | Stauffer, D.; Aharony, A., Introduction to Percolation Theory (2018), CRC press |
| [2] | Stauffer, D.; Sahimi, M., Diffusion in scale-free networks with annealed disorder, Phys. Rev. E, 72, 4, Article 046128 pp. (2005) |
| [3] | Rybak, M.; Kułakowski, K., Competing contact processes on homogeneous networks with tunable clusterization, Internat. J. Modern Phys. C, 24, 03, Article 1350012 pp. (2013) |
| [4] | Pandey, R.; Stauffer, D.; Margolina, A.; Zabolitzky, J., Diffusion on random systems above, below, and at their percolation threshold in two and three dimensions, J. Stat. Phys., 34, 3-4, 427-450 (1984) · Zbl 0589.60097 |
| [5] | Stauffer, D.; Aharony, A.; Mandelbrot, B., Self-similarity and covered neighborhoods of fractals: A random walk test, Physica A, 196, 1, 1-5 (1993) · Zbl 0808.60037 |
| [6] | Erdős, P.; Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., 5, 1, 17-60 (1960) · Zbl 0103.16301 |
| [7] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ’small-world’ networks, Nature, 393, 6684 (1998), 440-2 · Zbl 1368.05139 |
| [8] | Barabasi, A.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509 (1999) · Zbl 1226.05223 |
| [9] | Freche, P.; Stauffer, D.; Stanley, H., Surface structure and anisotropy of Eden clusters, J. Phys. A: Math. Gen., 18, 18, L1163 (1985) |
| [10] | Lambiotte, R.; Rosvall, M., Ranking and clustering of nodes in networks with smart teleportation, Phys. Rev. E, 85, 5, Article 056107 pp. (2012) |
| [11] | Stauffer, D., Monte Carlo study of biased diffusion at the percolation threshold, J. Phys. A: Math. Gen., 18, 10, 1827 (1985) |
| [12] | Stauffer, D.; Schulze, C.; Heermann, D. W., Superdiffusion in a model for diffusion in a molecularly crowded environment, J. Biol. Phys., 33, 4, 305 (2007) |
| [13] | Hütt, M.-T., Understanding genetic variation – the value of Systems Biology, Br. J. Clin. Pharm., 77, 4, 597-605 (2014) |
| [14] | Szklarczyk, D.; Gable, A. L.; Lyon, D.; Junge, A.; Wyder, S.; Huerta-Cepas, J.; Simonovic, M.; Doncheva, N. T.; Morris, J. H.; Bork, P., STRING v11: protein-protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets, Nucleic Acids Res., 47, D1, D607-D613 (2019) |
| [15] | Oughtred, R.; Stark, C.; Breitkreutz, B.-J.; Rust, J.; Boucher, L.; Chang, C.; Kolas, N.; O’Donnell, L.; Leung, G.; McAdam, R., The BioGRID interaction database: 2019 update, Nucleic Acids Res., 47, D1, D529-D541 (2019) |
| [16] | Thiele, I.; Swainston, N.; Fleming, R. M.; Hoppe, A.; Sahoo, S.; Aurich, M. K.; Haraldsdottir, H.; Mo, M. L.; Rolfsson, O.; Stobbe, M. D., A community-driven global reconstruction of human metabolism, Nature Biotechnol., 31, 5, 419-425 (2013) |
| [17] | Brunk, E.; Sahoo, S.; Zielinski, D. C.; Altunkaya, A.; Dräger, A.; Mih, N.; Gatto, F.; Nilsson, A.; Gonzalez, G. A.P.; Aurich, M. K., Recon3D enables a three-dimensional view of gene variation in human metabolism, Nature Biotechnol., 36, 3, 272 (2018) |
| [18] | Licata, L.; Lo Surdo, P.; Iannuccelli, M.; Palma, A.; Micarelli, E.; Perfetto, L.; Peluso, D.; Calderone, A.; Castagnoli, L.; Cesareni, G., SIGNOR 2.0, the SIGnaling network open resource 2.0: 2019 update, Nucleic Acids Res., 48, D1, D504-D510 (2020) |
| [19] | J. Menche, A. Sharma, M. Kitsak, S.D. Ghiassian, M. Vidal, J. Loscalzo, A.-L. Barabási, Uncovering disease-disease relationships through the incomplete interactome, Science 347 (6224). |
| [20] | Huang, J. K.; Carlin, D. E.; Yu, M. K.; Zhang, W.; Kreisberg, J. F.; Tamayo, P.; Ideker, T., Systematic evaluation of molecular networks for discovery of disease genes, Cell Syst., 6, 4, 484-495 (2018) |
| [21] | Cowen, L.; Ideker, T.; Raphael, B. J.; Sharan, R., Network propagation: a universal amplifier of genetic associations, Nature Rev. Genet., 18, 9, 551 (2017) |
| [22] | Sonnenschein, N.; Geertz, M.; Muskhelishvili, G.; Hütt, M.-T., Analog regulation of metabolic demand, BMC Syst. Biol., 5, 1, 40 (2011) |
| [23] | Sonnenschein, N.; Dzib, J. F.G.; Lesne, A.; Eilebrecht, S.; Boulkroun, S.; Zennaro, M.-C.; Benecke, A.; Hütt, M.-T., A network perspective on metabolic inconsistency, BMC Syst. Biol., 6, 1, 41 (2012) |
| [24] | Knecht, C.; Fretter, C.; Rosenstiel, P.; Krawczak, M.; Hütt, M.-T., Distinct metabolic network states manifest in the gene expression profiles of pediatric inflammatory bowel disease patients and controls, Sci. Rep., 6, 32584 (2016) |
| [25] | Brockmann, D.; Helbing, D., The hidden geometry of complex, network-driven contagion phenomena, Science, 342, 6164, 1337-1342 (2013) |
| [26] | Messé, A.; Hütt, M.-T.; König, P.; Hilgetag, C. C., A closer look at the apparent correlation of structural and functional connectivity in excitable neural networks, Sci. Rep., 5, 7870 (2015) |
| [27] | Messé, A.; Hütt, M.-T.; Hilgetag, C. C., Toward a theory of coactivation patterns in excitable neural networks, PLoS Comput. Biol., 14, 4, Article e1006084 pp. (2018) |
| [28] | Turnbull, L.; Hütt, M.-T.; Ioannides, A. A.; Kininmonth, S.; Poeppl, R.; Tockner, K.; Bracken, L. J.; Keesstra, S.; Liu, L.; Masselink, R., Connectivity and complex systems: learning from a multi-disciplinary perspective, Appl. Netw. Sci., 3, 1, 11 (2018) |
| [29] | Stauffer, D., Monte Carlo study of density profile, radius, and perimeter for percolation clusters and lattice animals, Phys. Rev. Lett., 41, 20, 1333 (1978) |
| [30] | Nyczka, P.; Hütt, M.-T., Generative network model of transcriptome patterns in disease cohorts with tunable signal strength, Phys. Rev. Res., 2, Article 033130 pp. (2020) |
| [31] | Kraskov, A.; Stögbauer, H.; Grassberger, P., Estimating mutual information, Phys. Rev. E, 69, 6, Article 066138 pp. (2004) |
| [32] | Sanz, J.; Cozzo, E.; Borge-Holthoefer, J.; Moreno, Y., Topological effects of data incompleteness of gene regulatory networks, BMC Syst. Biol., 6, 1, 110 (2012) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
