bipartite graph Dotaz Zobrazit nápovědu
Visualization analysis plays an important role in metagenomics research. Proper and clear visualization can help researchers get their first insights into data and by selecting different features, also revealing and highlighting hidden relationships and drawing conclusions. To prevent the resulting presentations from becoming chaotic, visualization techniques have to properly tackle the high dimensionality of microbiome data. Although a number of different methods based on dimensionality reduction, correlations, Venn diagrams, and network representations have already been published, there is still room for further improvement, especially in the techniques that allow visual comparison of several environments or developmental stages in one environment. In this article, we represent microbiome data by bipartite graphs, where one partition stands for taxa and the other stands for samples. We demonstrated that community detection is independent of taxonomical level. Moreover, focusing on higher taxonomical levels and the appropriate merging of samples greatly helps improving graph organization and makes our presentations clearer than other graph and network visualizations. Capturing labels in the vertices also brings the possibility of clearly comparing two or more microbial communities by showing their common and unique parts.
- Klíčová slova
- 16S rRNA, OTU table, bipartite graph, graph modularity, metagenomics, visualization analysis,
- Publikační typ
- časopisecké články MeSH
A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines ℓ 1 and ℓ 2 , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time O ( 9 k · n 9 ) , and also give a polynomial-time 9-approximation algorithm.
- Klíčová slova
- Comparability graphs, Graph modification problems, Partially ordered set, Permutation graphs,
- Publikační typ
- časopisecké články MeSH
We investigate adjacency matrices of bipartite graphs with a power-law degree distribution. Motivation for this study is twofold: first, vibrational states in granular matter and jammed sphere packings; second, graphs encoding social interaction, especially electronic commerce. We establish the position of the mobility edge and show that it strongly depends on the power in the degree distribution and on the ratio of the sizes of the two parts of the bipartite graph. At the jamming threshold, where the two parts have the same size, localization vanishes. We found that the multifractal spectrum is nontrivial in the delocalized phase, but still near the mobility edge. We also study an empirical bipartite graph, namely, the Amazon reviewer-item network. We found that in this specific graph the mobility edge disappears, and we draw a conclusion from this fact regarding earlier empirical studies of the Amazon network.
- Publikační typ
- časopisecké články MeSH
Municipal solid waste (MSW) is one of the issues associated with the growth of economic and urban population. The aim of this study is to develop an integrated design of waste management systems in support of a Circular Economy by P-graph (a bipartite graphical optimisation tool) as an effective decision support tool. The case study considers four MSW compositions based on different country income levels. Solving the P-graph model identifies the most suitable treatment approaches, considering the economic balance between the main operating cost, type, yield, quality of products, as well as the GHG emission (externality cost). The identification of near-optimal solutions by P-graph is useful in dealing with the trade-offs between conflicting objectives, e.g. local policy and practical implementation, that are difficult to monetise. For a lower-income country, the optimal solution includes a combination of at source separation, recycling, incineration (heat, electricity), anaerobic digestion (biofuel, digestate) and the landfill. It avoids an estimated 411 kg CO2eq/t of processed MSW and achieves a potential profit of 42 €/t of processed MSW. The optimisation generally favours mechanical biological treatment as the country income level rises, which affects the composition of the MSW. The relative prices of biofuel, electricity and heat (>20%) cause a significant impact on the highest-ranking treatment structure and overall profit. This study shows that the developed framework by P-graph is an effective tool for MSW systems planning. For future study, localised data inputs can be fed into the proposed framework for a customised solution and economic feasibility assessment.
- Klíčová slova
- Circular Economy, GHG emission, P-graph, Waste to resources,
- Publikační typ
- časopisecké články MeSH
The aim of this short note is to draw attention to a method by which the partition function and marginal probabilities for a certain class of random fields on complete graphs can be computed in polynomial time. This class includes Ising models with homogeneous pairwise potentials but arbitrary (inhomogeneous) unary potentials. Similarly, the partition function and marginal probabilities can be computed in polynomial time for random fields on complete bipartite graphs, provided they have homogeneous pairwise potentials. We expect that these tractable classes of large-scale random fields can be very useful for the evaluation of approximation algorithms by providing exact error estimates.
- Publikační typ
- časopisecké články MeSH
- práce podpořená grantem MeSH
Social networks are a battlefield for political propaganda. Protected by the anonymity of the internet, political actors use computational propaganda to influence the masses. Their methods include the use of synchronized or individual bots, multiple accounts operated by one social media management tool, or different manipulations of search engines and social network algorithms, all aiming to promote their ideology. While computational propaganda influences modern society, it is hard to measure or detect it. Furthermore, with the recent exponential growth in large language models (L.L.M), and the growing concerns about information overload, which makes the alternative truth spheres more noisy than ever before, the complexity and magnitude of computational propaganda is also expected to increase, making their detection even harder. Propaganda in social networks is disguised as legitimate news sent from authentic users. It smartly blended real users with fake accounts. We seek here to detect efforts to manipulate the spread of information in social networks, by one of the fundamental macro-scale properties of rhetoric-repetitiveness. We use 16 data sets of a total size of 13 GB, 10 related to political topics and 6 related to non-political ones (large-scale disasters), each ranging from tens of thousands to a few million of tweets. We compare them and identify statistical and network properties that distinguish between these two types of information cascades. These features are based on both the repetition distribution of hashtags and the mentions of users, as well as the network structure. Together, they enable us to distinguish (p - value = 0.0001) between the two different classes of information cascades. In addition to constructing a bipartite graph connecting words and tweets to each cascade, we develop a quantitative measure and show how it can be used to distinguish between political and non-political discussions. Our method is indifferent to the cascade's country of origin, language, or cultural background since it is only based on the statistical properties of repetitiveness and the word appearance in tweets bipartite network structures.
- MeSH
- algoritmy MeSH
- lidé MeSH
- politika * MeSH
- propaganda MeSH
- šíření informací * metody MeSH
- sociální média * MeSH
- sociální sítě * MeSH
- Check Tag
- lidé MeSH
- Publikační typ
- časopisecké články MeSH
Pathogens significantly influence natural and agricultural ecosystems, playing a crucial role in the regulation of species populations and maintaining biodiversity. Entomopathogenic fungi (EF), particularly within the Hypocreales order, exemplify understudied pathogens that infect insects and other arthropods globally. Despite their ecological importance, comprehensive data on EF host specificity and geographical distribution are lacking. To address this, we present EntomoFun 1.0, an open-access database centralizing global records of EF-insect associations in Hypocreales. This database includes 1,791 records detailing EF species, insect host taxa, countries of occurrence, life stages of hosts, and information sources. EntomoFun 1.0 is constructed based on 600 literature sources, as well as herbarium specimens of the Royal Botanical Gardens, Kew. This database is intended to test hypotheses, identify knowledge gaps, and stimulate future research. Contents of the EntomoFun 1.0 database are visualized with a global map, taxonomic chart, bipartite community network, and graphs.
Micro (micro-) axial tomography is a challenging technique in microscopy which improves quantitative imaging especially in cytogenetic applications by means of defined sample rotation under the microscope objective. The advantage of micro-axial tomography is an effective improvement of the precision of distance measurements between point-like objects. Under certain circumstances, the effective (3D) resolution can be improved by optimized acquisition depending on subsequent, multi-perspective image recording of the same objects followed by reconstruction methods. This requires, however, a very precise alignment of the tilted views. We present a novel feature-based image alignment method with a precision better than the full width at half maximum of the point spread function. The features are the positions (centres of gravity) of all fluorescent objects observed in the images (e.g. cell nuclei, fluorescent signals inside cell nuclei, fluorescent beads, etc.). Thus, real alignment precision depends on the localization precision of these objects. The method automatically determines the corresponding objects in subsequently tilted perspectives using a weighted bipartite graph. The optimum transformation function is computed in a least squares manner based on the coordinates of the centres of gravity of the matched objects. The theoretically feasible precision of the method was calculated using computer-generated data and confirmed by tests on real image series obtained from data sets of 200 nm fluorescent nano-particles. The advantages of the proposed algorithm are its speed and accuracy, which means that if enough objects are included, the real alignment precision is better than the axial localization precision of a single object. The alignment precision can be assessed directly from the algorithm's output. Thus, the method can be applied not only for image alignment and object matching in tilted view series in order to reconstruct (3D) images, but also to validate the experimental performance (e.g. mechanical precision of the tilting). In practice, the key application of the method is an improvement of the effective spatial (3D) resolution, because the well-known spatial anisotropy in light microscopy can be overcome. This allows more precise distance measurements between point-like objects.
