Search

Magnolia kwangsiensis, a dioecious tree native to China, is recognized not only for its status as an at-risk species but also for its potential in therapeutic applications courtesy of its bioactive compounds. However, the genetic underpinnings of its leaf development and compound biosynthesis are not well documented. Our study aims to bridge this knowledge gap through comparative transcriptomics, analyzing gene expression through different leaf maturation stages. We studied the transcriptome of M. kwangsiensis leaves by applying RNA sequencing at juvenile, tender, and mature phases. We identified differentially expressed genes (DEGs) to explore transcriptional changes accompanying the developmental trajectory. Our analysis delineates the transcriptional landscape of over 20,000 genes with over 6000 DEGs highlighting significant transcriptional shifts throughout leaf maturation. Mature leaves demonstrated upregulation in pathways related to photosynthesis, cell wall formation, and polysaccharide production, affirming their structural integrity and specialized metabolic functions. Our GO and KEGG enrichment analyses underpin these findings. Furthermore, we unveiled coordinated gene activity correlating development with synthesizing therapeutically relevant polysaccharides. We identified four novel glycosyltransferases potentially pivotal in this synergistic mechanism. Our study uncovers the complementary evolutionary forces that concurrently sculpt structural and chemical defenses. These genetic mechanisms calibrate leaf tissue resilience and biochemical efficacy.

An edge-colored graph G is called rainbow if every edge of G receives a different color. Given any host graph G, the anti-Ramsey number of t edge-disjoint rainbow spanning trees in G, denoted by r(G,t), is defined as the maximum number of colors in an edge-coloring of G containing no t edge-disjoint rainbow spanning trees. For any vertex partition P, let E(P,G) be the set of non-crossing edges in G with respect to P. In this paper, we determine r(G,t) for all host graphs G: r(G,t)=|E(G)| if there exists a partition P0 with |E(G)|-|E(P0,G)|

Abstract Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data.

Abstract Empirical networks exhibit significant heterogeneity in node connections, resulting in a few vertices playing critical roles in various scenarios, including decision-making, viral marketing, and population immunization. Thus, identifying key vertices is a fundamental research problem in Network Science. In this paper, we introduce vertex entanglement (VE), an entanglement-based metric capable of quantifying the perturbations caused by individual vertices on spectral entropy, residing at the intersection of quantum information and network science. Our analytical analysis reveals that VE is closely related to network robustness and information transmission ability. As an application, VE offers an approach to the challenging problem of optimal network dismantling, and empirical experiments demonstrate its superiority over state-of-the-art algorithms. Furthermore, VE also contributes to the diagnosis of autism spectrum disorder (ASD), with significant distinctions in hub disruption indices based on VE between ASD and typical controls, promising a diagnostic role for VE in ASD assessment.

Diverse higher-order structures, foundational for supporting a network’s “meta-functions”, play a vital role in structure, functionality, and the emergence of complex dynamics. Nevertheless, the problem of dismantling them has been consistently overlooked. In this paper, we introduce the concept of dismantling higher-order structures, with the objective of disrupting not only network connectivity but also eradicating all higher-order structures in each branch, thereby ensuring thorough functional paralysis. Given the diversity and unknown specifics of higher-order structures, identifying and targeting them individually is not practical or even feasible. Fortunately, their close association with k-cores arises from their internal high connectivity. Thus, we transform higher-order structure measurement into measurements on k-cores with corresponding orders. Furthermore, we propose the Belief Propagation-guided Higher-order Dismantling (BPHD) algorithm, minimizing dismantling costs while achieving maximal disruption to connectivity and higher-order structures, ultimately converting the network into a forest. BPHD exhibits the explosive vulnerability of network higher-order structures, counterintuitively showcasing decreasing dismantling costs with increasing structural complexity. Our findings offer a novel approach for dismantling malignant networks, emphasizing the substantial challenges inherent in safeguarding against such malicious attacks.

An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 82 (2016), pp. 75-89] conjectured that for any fixed t, r(n, t) = (n 2 2) + t whenever n geq 2t + 2 geq 6. In this paper, we prove this conjecture. We also determine r(n, t) when n = 2t+1. Together with previous results, this gives the anti-Ramsey number of t edge-disjoint rainbow spanning trees for all values of n and t. [ABSTRACT FROM AUTHOR]

Synchronization is a widespread emergent feature of complex systems. Here, the authors investigate the optimization of synchronization in phase oscillators with higher-order interactions, and find that optimized networks are more homogeneous in the nodes’ degree for undirected interactions, and for directed interactions they are generally structurally asymmetric, but can be symmetric, which differs from the pairwise case.

Null models are crucial tools for investigating network topological structures. However, research on null models for higher-order networks is still relatively scarce. In this study, we introduce an innovative method to construct null models for hypergraphs, namely the hyperedge swapping-based method. By preserving certain network properties while altering others, we generate six hyper-null models with various orders and analyze their interrelationships. To validate our approach, we first employ hypergraph entropy to assess the randomness of these null models across four datasets. Furthermore, we examine the differences in important statistical properties between the various null models and the original networks. Lastly, we investigate the impact of hypergraph randomness on network dynamics using the proposed hyper-null models, focusing on dismantling and epidemic contagion. The findings show that our proposed hyper-null models are applicable to various scenarios. By introducing a comprehensive framework for generating and analyzing hyper-null models, this research opens up avenues for further exploration of the intricacies of network structures and their real-world implications.

Characterising the structure of real-world complex networks is of crucial importance to understand the emerging dynamics taking place on top of them. In this work the authors investigate the cycle organization of synthetic and real systems, and use such information to define a centrality measure that is more informative than traditional indexes to the end of understanding network dismantling, synchronization, and spreading processes

For any r ≥ 2 and k ≥ 3, the r-color size-Ramsey number R(G,r) of a k-uniform hypergraph G is the smallest integer m such that there exists a k-uniform hypergraph H on m edges such that any coloring of the edges of H with r colors yields a monochromatic copy of G. Let Pn,k-1 (k) denote the k-uniform tight path on n vertices. Dudek et al. [J. Graph Theory, 86 (2017), pp. 104-121] showed that the size-Ramsey number of tight paths R(Pn,k-1 (k), 2) = O(nk-1-α(logn)1+α) where α = (k-2)/2k-1 +1. In this paper, we improve their bound by showing that R(Pn,k-1(k), r) = O(rk(nlogn)k/2) for all k ≥ 3 and r ≥ 2. [ABSTRACT FROM AUTHOR]

The ability to predict the size of information cascades in online social networks is crucial for various applications, including decision-making and viral marketing. However, traditional methods either rely on complicated time-varying features that are challenging to extract from multilingual and cross-platform content, or on network structures and properties that are often difficult to obtain. To address these issues, we conducted empirical research using data from two well-known social networking platforms, WeChat and Weibo. Our findings suggest that the information-cascading process is best described as an activate–decay dynamic process. Building on these insights, we developed an activate–decay (AD)-based algorithm that can accurately predict the long-term popularity of online content based solely on its early repost amount. We tested our algorithm using data from WeChat and Weibo, demonstrating that we could fit the evolution trend of content propagation and predict the longer-term dynamics of message forwarding from earlier data. We also discovered a close correlation between the peak forwarding amount of information and the total amount of dissemination. Finding the peak of the amount of information dissemination can significantly improve the prediction accuracy of our model. Our method also outperformed existing baseline methods for predicting the popularity of information.

Identifying potential mechanisms behind opinion formation is key to curb the spread of misinformation and fake news. Here, the authors propose a model of opinion formation on a network of relations of trust and distrust between subjects, and show that opinion instability increases with the complexity and size of the system, proposing a candidate mechanism for how trust towards deceptive sources develops.

The 2021 Nobel Prize in Physics recognized the fundamental role of complex systems in the natural sciences. In order to celebrate this milestone, this editorial presents the point of view of the editorial board of JPhys Complexity on the achievements, challenges, and future prospects of the field. To distinguish the voice and the opinion of each editor, this editorial consists of a series of editor perspectives and reflections on few selected themes. A comprehensive and multi-faceted view of the field of complexity science emerges. We hope and trust that this open discussion will be of inspiration for future research on complex systems.

Predicting network dynamics based on data, a problem with broad applications, has been studied extensively in the past, but most existing approaches assume that the complete set of historical data from the whole network is available. This requirement presents a great challenge in applications, especially for large, distributed networks in the real world, where data collection is accomplished by many clients in a parallel fashion. Often, each client only has the time series data from a partial set of nodes, and the client has access to only partial time stamps of the whole set of time series data and the partial structure of the network. Due to privacy concerns or license-related issues, the data collected by different clients cannot be shared. Accurately predicting the network dynamics while protecting the privacy of different parties is a critical problem in modern times. Here, we propose a solution based on federated graph neural networks (FGNNs) that enables the training of a global dynamic model for all parties without data sharing. We validate the working of our FGNN framework through two types of simulations to predict a variety of network dynamics (four discrete and three continuous dynamics). As a significant real-world application, we demonstrate successful prediction of state-wise influenza spreading in the USA. Our FGNN scheme represents a general framework to predict diverse network dynamics through collaborative fusing of the data from different parties without disclosing their privacy.

Let Δ (G) be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number X(G) = Δ (G) + 1 are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number Xf(G) is at least Δ (G). These graphs are complete graphs, odd cycles, C²8 C5 ⊠ K2, and graphs whose clique number ω(G) equals the maximum degree Δ (G). Among the two sporadic graphs, the graph C²8 is the square graph of cycle C8, while the other graph C5 ⊠ K2 is the strong product of C5 and K2. In fact, we prove a stronger result: If a connected graph G with δ (G) ≥ 4 is not one of the graphs listed above, then we have Xf(G)≤ Δ(G) -- 2/67. [ABSTRACT FROM AUTHOR]

The routing number rt(G) of a connected graph G is the minimum integer r so that every permutation of vertices can be routed in r steps by swapping the ends of disjoint edges. In this paper, we study the routing numbers of cycles, complete bipartite graphs, and hypercubes. We prove that rt(Cn) = n - 1 (for n ≥ 3) and for Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. We also prove n + 1 ≤ rt(Qn) ≤ 2n - 2 for n ≥ 3. The lower bound rt(Qn) > ≥ + 1 was previously conjectured by Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 513-530]. A variation, called fractional routing number, is also considered in this paper. [ABSTRACT FROM AUTHOR]

Sorting permutations by transpositions is an important and difficult problem in genome rearrangements. The transposition diameter TD (n) is the maximum transposition distance among all pairs of permutations in Sn. It was previously conjectured [H. Ericksson et al., Discrete Math., 241 (2001), pp. 289-300] that TD (n) ≤ Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. This conjecture was disproved by Elias and Hartman [IEEE/ACM Trans. Comput. Biol. Bioinform.. 3 (2006), 369-379] by showing TD (n) ≥ Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. In this paper we improved the lower bound to TD (n) ≥ 17/33n + 1/33 via computation. [ABSTRACT FROM AUTHOR]

Let F ⊂ 2[n] be a family of subsets of {1, 2, … , n}. For any poset H, we say F is H-free if F does not contain any subposet isomorphic to H. Katona and others have investigated the behaviour of La(n,H), which denotes the maximum size of H-free families F ⊂ 2[n]. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets H, for which La(n,H) can be determined asymptotically as n→∞ for various posets H, including two-end-forks, up-down trees, and cycles C4k on two levels. [ABSTRACT FROM AUTHOR]

We first answer a question of de Caen [Extremal Problems for Finite Sets, J'anos Bolyai Math. Soc., Budapest, 1994, pp. 187–197]: given r ⩾ 3, if G is an r – uniform hypergraph on n vertices such that every r + 1 vertices span 1 or r + 1 edges, then G = K r n –1 or K r n–1, assuming that n > (p – 1)r, where p is the smallest prime factor of r – 1. We then show that the Tur'an density π(Kr r+1) = 1 – 1/r – (1 – 1/rp–1)(r – 1)2/(2rp(r+p p–1+ r+1 2 )), for all even r = 4, improving a well–known bound 1 – 1 r of de Caen [Ars Combin., 16 (1983), pp. 5–10] and Sidorenko [Vestnik Moskov. Univ. Ser. I Mat. Mekh., 76 (1982), pp. 3–6]. [ABSTRACT FROM AUTHOR]

We first answer a question of de Caen [Extremal Problems for Finite Sets, J'anos Bolyai Math. Soc., Budapest, 1994, pp. 187–197]: given r ⩾ 3, if G is an r – uniform hypergraph on n vertices such that every r + 1 vertices span 1 or r + 1 edges, then G = K r n –1 or K r n–1, assuming that n > (p – 1)r, where p is the smallest prime factor of r – 1. We then show that the Tur'an density π(Kr r+1) = 1 – 1/r – (1 – 1/rp–1)(r – 1)2/(2rp(r+p p–1+ r+1 2 )), for all even r = 4, improving a well–known bound 1 – 1 r of de Caen [Ars Combin., 16 (1983), pp. 5–10] and Sidorenko [Vestnik Moskov. Univ. Ser. I Mat. Mekh., 76 (1982), pp. 3–6]. [ABSTRACT FROM AUTHOR]

Abstract  It has been noted that many realistic graphs have a power law degree distribution and exhibit the small-world phenomenon. We present drawing methods influenced by recent developments in the modeling of such graphs. Our main approach is to partition the edge set of a graph into "local" edges and "global" edges and to use a standard drawing method that allows us to give added importance to local edges. We show that our drawing method works well for graphs that contain underlying geometric graphs augmented with random edges, and we demonstrate the method on a few examples. We define edges to be local or global depending on the size of the maximum short flow between the edge's endpoints. Here, a short flow, or alternatively an ℓ-short flow, is one composed of paths whose length is at most some constant ℓ. We present fast approximation algorithms for the maximum short flow problem and for testing whether a short flow of a certain size exists between given vertices. Using these algorithms, we give an algorithm for computing approximate local subgraphs of a given graph. The drawing algorithm we present can be applied to general graphs, but it is particularly well suited for small-world networks with power law degree distribution. [ABSTRACT FROM AUTHOR]

We consider the random graph model G(w) for a given expected degree sequence w = (w1, w2,…, wn). If the expected average degree is strictly greater than 1, then almost surely the giant component in G of G(w) has volume (i.e., sum of weights of vertices in the giant component) equal to λ0Vol(G) + O(√n log3.5 n), where λ0 is the unique nonzero root of the equation n∑i=1wie-wiλ = (1- λ) n∑i=1wi, and where Vol(G) = ∑iwi. [ABSTRACT FROM AUTHOR]

In the study of the spectra of power-law graphs, there are basically two competing approaches. One is to prove analogues of Wigner's semicircle law, whereas the other predicts that the eigenvalues follow a power-law distribution. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power-law graph follow the semicircle law, whereas the spectrum of the adjacency matrix of a power-law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. Of interest are a number of (new) values for the exponent β, where phase transitions for eigenvalue distributions occur. The spectrum distributions have direct implications to numerous graph algorithms such as, for example, randomized algorithms that involve rapidly mixing Markov chains. [ABSTRACT FROM AUTHOR]

Random graph theory is used to examine the "small-world phenomenon"; any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees the average distance is almost surely of order log n/log &dtilde;, where &dtilde; is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1/k[sup &beta] for some fixed exponent β. For the case of β > 3, we prove that the average distance of the power law graphs is almost surely of order log n/log &dtilde;. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, which we call the core, having n[sup c/log log n] vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core. [ABSTRACT FROM AUTHOR]

The vital nodes are the ones that play an important role in the organization of network structure or the dynamical behaviors of networked systems. Previous studies usually applied the node centralities to quantify the importance of nodes. Realizing that the percolation clusters are dominated by local connections in the subcritical phase and by global connections in the supercritical phase, in this paper we propose a new method to identify the vital nodes via a competitive percolation process that is based on an Achlioptas process. Compared with the existing node centrality indices, the new method performs overall better in identifying the vital nodes that maintain network connectivity and facilitate network synchronization when considering different network structure characteristics, such as link density, degree distribution, assortativity, and clustering. We also find that our method is more tolerant of noisy data and missing data. More importantly, compared with the unique ranking list of nodes given by most centrality methods, the randomness of the percolation process expands the possibility space of the optimal solutions, which is of great significance in practical applications.

Identifying influential nodes in networks is important for the understanding of their structure and function, but there are several so far unrelated measures to assess this. Here, the authors unfold relations among knows criteria and construct a family of indices that interpolate between degree and coreness.

The ongoing rapid development of the e-commercial and interest-base websites makes it more pressing to evaluate objects’ accurate quality before recommendation. The objects’ quality is often calculated based on their historical information, such as selected records or rating scores. Usually high quality products obtain higher average ratings than low quality products regardless of rating biases or errors. However, many empirical cases demonstrate that consumers may be misled by rating scores added by unreliable users or deliberate tampering. In this case, users’ reputation, that is, the ability to rate trustily and precisely, makes a big difference during the evaluation process. Thus, one of the main challenges in designing reputation systems is eliminating the effects of users’ rating bias. To give an objective evaluation of each user’s reputation and uncover an object’s intrinsic quality, we propose an iterative balance (IB) method to correct users’ rating biases. Experiments on two datasets show that the IB method is a highly self-consistent and robust algorithm and it can accurately quantify movies’ actual quality and users’ stability of rating. Compared with existing methods, the IB method has higher ability to find the “dark horses,” that is, not so popular yet good movies, in the Academy Awards.

Real networks typically studied in various research fields—ecology and economic complexity, for example—often exhibit a nested topology, which means that the neighborhoods of high-degree nodes tend to include the neighborhoods of low-degree nodes. Focusing on nested networks, we study the problem of link prediction in complex networks, which aims at identifying likely candidates for missing links. We find that a new method that takes network nestedness into account outperforms well-established link-prediction methods not only when the input networks are sufficiently nested, but also for networks where the nested structure is imperfect. Our study paves the way to search for optimal methods for link prediction in nested networks, which might be beneficial for World Trade and ecological network analysis.

Participation in social groups are important but the collective behaviors of human as a group are difficult to analyze due to the difficulties to quantify ordinary social relation, group membership, and to collect a comprehensive dataset. Such difficulties can be circumvented by analyzing online social networks.In this paper, we analyze a comprehensive dataset released from Tencent QQ, an instant messenger with the highest market share in China. Specifically, we analyze three derivative networks involving groups and their members-the hypergraph of groups, the network of groups and the user network-to reveal social interactions at microscopic and mesoscopic level.Our results uncover interesting behaviors on the growth of user groups, the interactions between groups, and their relationship with member age and gender. These findings lead to insights which are difficult to obtain in social networks based on personal contacts.

Social networks constitute a new platform for information propagation, but its success is crucially dependent on the choice of spreaders who initiate the spreading of information. In this paper, we remove edges in a network at random and the network segments into isolated clusters. The most important nodes in each cluster then form a set of influential spreaders, such that news propagating from them would lead to extensive coverage and minimal redundancy. The method utilizes the similarities between the segmented networks before percolation and the coverage of information propagation in each social cluster to obtain a set of distributed and coordinated spreaders. Our tests of implementing the susceptible-infected-recovered model on Facebook and Enron email networks show that this method outperforms conventional centrality-based methods in terms of spreadability and coverage redundancy. The suggested way of identifying influential spreaders thus sheds light on a new paradigm of information propagation in social networks.

Uncovering factors underlying the network formation is a long-standing challenge for data mining and network analysis. In particular, the microscopic organizing principles of directed networks are less understood than those of undirected networks. This article proposes a hypothesis named potential theory, which assumes that every directed link corresponds to a decrease of a unit potential and subgraphs with definable potential values for all nodes are preferred. Combining the potential theory with the clustering and homophily mechanisms, it is deduced that the Bi-fan structure consisting of 4 nodes and 4 directed links is the most favored local structure in directed networks. Our hypothesis receives strongly positive supports from extensive experiments on 15 directed networks drawn from disparate fields, as indicated by the most accurate and robust performance of Bi-fan predictor within the link prediction framework. In summary, our main contribution is twofold: (i) We propose a new mechanism for the local organization of directed networks; (ii) We design the corresponding link prediction algorithm, which can not only testify our hypothesis, but also find out direct applications in missing link prediction and friendship recommendation.

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node's neighbors but do not directly make use of the interactions among it's neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors' influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about [Formula: see text] nodes, more than 15 times faster than PageRank.