For a graph H, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions W in L p , p ≥ e ( H ) , denoted by t(H, W). One may then define corresponding functionals ‖ W ‖ H : = | t ( H , W ) | 1 / e ( H ) and ‖ W ‖ r ( H ) : = t ( H , | W | ) 1 / e ( H ) , and say that H is (semi-)norming if ‖ · ‖ H is a (semi-)norm and that H is weakly norming if ‖ · ‖ r ( H ) is a norm. We obtain two results that contribute to the theory of (weakly) norming graphs. Firstly, answering a question of Hatami, who estimated the modulus of convexity and smoothness of ‖ · ‖ H , we prove that ‖ · ‖ r ( H ) is neither uniformly convex nor uniformly smooth, provided that H is weakly norming. Secondly, we prove that every graph H without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of H when studying graph norms. In particular, we correct a negligence in the original statement of the aforementioned theorem by Hatami.
- Keywords
- Graph limits, Graph norms, Graphons,
- Publication type
- Journal Article MeSH
One of the major challenges in modern biology is the use of large omics datasets for the characterization of complex processes such as cell response to infection. These challenges are even bigger when analyses need to be performed for comparison of different species including model and non-model organisms. To address these challenges, the graph theory was applied to characterize the tick vector and human cell protein response to infection with Anaplasma phagocytophilum, the causative agent of human granulocytic anaplasmosis. A network of interacting proteins and cell processes clustered in biological pathways, and ranked with indexes representing the topology of the proteome was prepared. The results demonstrated that networks of functionally interacting proteins represented in both infected and uninfected cells can describe the complete set of host cell processes and metabolic pathways, providing a deeper view of the comparative host cell response to pathogen infection. The results demonstrated that changes in the tick proteome were driven by modifications in protein representation in response to A. phagocytophilum infection. Pathogen infection had a higher impact on tick than human proteome. Since most proteins were linked to several cell processes, the changes in protein representation affected simultaneously different biological pathways. The method allowed discerning cell processes that were affected by pathogen infection from those that remained unaffected. The results supported that human neutrophils but not tick cells limit pathogen infection through differential representation of ras-related proteins. This methodological approach could be applied to other host-pathogen models to identify host derived key proteins in response to infection that may be used to develop novel control strategies for arthropod-borne pathogens.
- Keywords
- Anaplasma phagocytophilum, graph theory, network, omics, ras-related proteins, tick,
- MeSH
- Anaplasma phagocytophilum growth & development MeSH
- Anaplasmosis pathology MeSH
- Biological Phenomena MeSH
- Cell Line MeSH
- Arthropod Vectors * MeSH
- Host-Pathogen Interactions * MeSH
- Ticks MeSH
- Humans MeSH
- Protein Interaction Maps MeSH
- Proteins analysis MeSH
- Proteome analysis MeSH
- Models, Theoretical * MeSH
- Animals MeSH
- Check Tag
- Humans MeSH
- Animals MeSH
- Publication type
- Journal Article MeSH
- Research Support, Non-U.S. Gov't MeSH
- Names of Substances
- Proteins MeSH
- Proteome MeSH
A probability measure μ on the subsets of the edge set of a graph G is a 1-independent probability measure (1-ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1-ipm μ , denote by G μ the associated random graph model. Let ℳ 1 , ⩾ p ( G ) denote the collection of 1-ipms μ on G for which each edge is included in G μ with probability at least p. For G = Z 2 , Balister and Bollobás asked for the value of the least p ⋆ such that for all p > p ⋆ and all μ ∈ ℳ 1 , ⩾ p ( G ) , G μ almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on p ⋆. We also determine the 1-independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs G we study f 1, G (p), the infimum over all μ ∈ ℳ 1 , ⩾ p ( G ) of the probability that G μ is connected. We determine f 1, G (p) exactly when G is a path, a complete graph and a cycle of length at most 5.
- Keywords
- extremal graph theory, local lemma, percolation, random graphs,
- Publication type
- Journal Article MeSH
We present a method based on graph theory for the evaluation of the inelastic propensity rules for molecules exhibiting complete destructive quantum interference in their elastic transmission. The method uses an extended adjacency matrix corresponding to the structural graph of the molecule for calculating Green's function between the sites with attached electrodes and consequently states the corresponding conditions the electron-vibration coupling matrix must meet for the observation of an inelastic signal between the terminals. The method can be fully automated and we provide a functional website running a code using Wolfram Mathematica, which returns a graphical depiction of destructive quantum interference configurations together with the associated inelastic propensity rules for a wide class of molecules.
- Publication type
- Journal Article MeSH
In recent years, there has been an increasing interest in the study of large-scale brain activity interaction structure from the perspective of complex networks, based on functional magnetic resonance imaging (fMRI) measurements. To assess the strength of interaction (functional connectivity, FC) between two brain regions, the linear (Pearson) correlation coefficient of the respective time series is most commonly used. Since a potential use of nonlinear FC measures has recently been discussed in this and other fields, the question arises whether particular nonlinear FC measures would be more informative for the graph analysis than linear ones. We present a comparison of network analysis results obtained from the brain connectivity graphs capturing either full (both linear and nonlinear) or only linear connectivity using 24 sessions of human resting-state fMRI. For each session, a matrix of full connectivity between 90 anatomical parcel time series is computed using mutual information. For comparison, connectivity matrices obtained for multivariate linear Gaussian surrogate data that preserve the correlations, but remove any nonlinearity are generated. Binarizing these matrices using multiple thresholds, we generate graphs corresponding to linear and full nonlinear interaction structures. The effect of neglecting nonlinearity is then assessed by comparing the values of a range of graph-theoretical measures evaluated for both types of graphs. Statistical comparisons suggest a potential effect of nonlinearity on the local measures-clustering coefficient and betweenness centrality. Nevertheless, subsequent quantitative comparison shows that the nonlinearity effect is practically negligible when compared to the intersubject variability of the graph measures. Further, on the group-average graph level, the nonlinearity effect is unnoticeable.
- MeSH
- Databases as Topic MeSH
- Adult MeSH
- Humans MeSH
- Magnetic Resonance Imaging MeSH
- Young Adult MeSH
- Models, Neurological * MeSH
- Brain physiology MeSH
- Nonlinear Dynamics * MeSH
- Nerve Net physiology MeSH
- Rest physiology MeSH
- Statistics as Topic MeSH
- Check Tag
- Adult MeSH
- Humans MeSH
- Young Adult MeSH
- Male MeSH
- Female MeSH
- Publication type
- Journal Article MeSH
- Research Support, Non-U.S. Gov't MeSH
In the first part Freud's clinical theories and models and the ego psychological theory were described from which ensues a general pattern of objective relations. The second part of the paper attempts a synthesis of the most important psychoanalytical theories, the creation of a uniform model of psychic functioning using an epigenetic pattern. The author analyzes in more detail developmental trends of these mental functions which are considered in psychoanalysis decisive for adaptation. The developmental trends are divided into stages which correlate with stages of the development of objective relations. The developmental stages and transformations of specific psychological functions are presented by means of rectangular coordinate graphs. In the conclusion an epigenetic pattern of the foreseen development of personality is presented, a hierarchical model of modes of personality organization.
- MeSH
- Humans MeSH
- Psychoanalytic Theory * MeSH
- Personality Development * MeSH
- Check Tag
- Humans MeSH
- Publication type
- English Abstract MeSH
- Journal Article MeSH
- MeSH
- Medical Informatics * MeSH
- Mathematics MeSH
- Publication type
- English Abstract MeSH
- Journal Article MeSH
Evolutionary game theory is a powerful method for modelling animal conflicts. The original evolutionary game models were used to explain specific biological features of interest, such as the existence of ritualised contests, and were necessarily simple models that ignored many properties of real populations, including the duration of events and spatial and related structural effects. Both of these areas have subsequently received much attention. Spatial and structural effects have been considered in evolutionary graph theory, and a significant body of literature has been built up to deal with situations where the population is not homogeneous. More recently a theory of time constraints has been developed to take account of the fact that different events can take different times, and that interaction times can explicitly depend upon selected strategies, which can, in turn, influence the distribution of different opponent types within the population. Here, for the first time, we build a model of time constraint games which explicitly considers a spatial population, by considering a population evolving on an underlying graph, using two graph dynamics, birth-death and death-birth. We consider one short time scale along which frequencies of pairs and singles change as individuals interact with their neighbours, and another, evolutionary time scale, along which frequencies of strategies change in the population. We show that for graphs with large degree, both dynamics reproduce recent results from well-mixed time constraint models, including two ESSs being common in Hawk-Dove and Prisoner's Dilemma games, but for low degree there can be marked differences. For birth-death processes the effect of the graph degree is small, whereas for death-birth dynamics there is a large effect. The general prediction for both Hawk-Dove and Prisoner's dilemma games is that as the graph degree decreases, i.e., as the number of neighbours decreases, mixed ESS do appear. In particular, for the Prisoner's dilemma game this means that cooperation is easier to establish in situations where individuals have low number of neighbours. We thus see that solutions depend non-trivially on the combination of graph degree, dynamics and game.
- Keywords
- Birth-death and death-birth updating, Evolutionary game theory, Games on regular graphs, Hawk-Dove game, Prisoner’s dilemma,
- MeSH
- Biological Evolution * MeSH
- Cooperative Behavior MeSH
- Game Theory * MeSH
- Animals MeSH
- Check Tag
- Animals MeSH
- Publication type
- Journal Article MeSH
- Research Support, Non-U.S. Gov't MeSH
- Keywords
- COMPUTERS *, MENTAL DISORDERS *, STATISTICS *,
- MeSH
- Biometry * MeSH
- Mental Disorders * MeSH
- Humans MeSH
- Computers * MeSH
- Statistics as Topic * MeSH
- Check Tag
- Humans MeSH
- Publication type
- Journal Article MeSH
Natural selection is usually studied between mutants that differ in reproductive rate, but are subject to the same population structure. Here we explore how natural selection acts on mutants that have the same reproductive rate, but different population structures. In our framework, population structure is given by a graph that specifies where offspring can disperse. The invading mutant disperses offspring on a different graph than the resident wild-type. We find that more densely connected dispersal graphs tend to increase the invader's fixation probability, but the exact relationship between structure and fixation probability is subtle. We present three main results. First, we prove that if both invader and resident are on complete dispersal graphs, then removing a single edge in the invader's dispersal graph reduces its fixation probability. Second, we show that for certain island models higher invader's connectivity increases its fixation probability, but the magnitude of the effect depends on the exact layout of the connections. Third, we show that for lattices the effect of different connectivity is comparable to that of different fitness: for large population size, the invader's fixation probability is either constant or exponentially small, depending on whether it is more or less connected than the resident.
