Designing threshold networks with given structural and dynamical properties

Abundance, Betweenness Centrality, Hydrophobicity, and Isoelectric Points Are Relevant Factors in the Processing of Parental Proteins of the HLA Class II Ligandome

Adaptive cellular and humoral immune responses to infectious agents require previous recognition of pathogenic peptides bound to human leukocyte antigen (HLA) class II molecules exposed on the surface of the professional antigen-presenting cells. Knowledge of how these peptide ligands are generated is essential to understand the basis for CD4⁺ T-cell-mediated immunity and tolerance. In this study, a high-throughput mass spectrometry analysis was used to identify more than 16,000 cell peptides bound to several HLA-DR and -DP class II molecules isolated from large amounts of uninfected and virus-infected human cells (ProteomeXchange accession: PXD028006). The analysis of the 1808 parental proteins containing HLA class II ligands revealed that these cell proteins were more acidic, abundant, and highly connected but less hydrophilic than non-parental proteomes. Therefore, the percentage of acidic residues was increased and hydroxyl and polar residues were decreased in the parental proteins for the HLA class II ligandomes versus the non-parental proteomes. This definition of the properties shared by parental proteins that constitute the source of the HLA class II ligandomes can serve as the basis for the development of bioinformatics tools to predict proteins that are most likely recognized by the immune system through the CD4⁺ helper T lymphocytes in both autoimmunity and infection.

Metrics for regulated biochemical pathway systems

MOTIVATION

The assessment of graphs through crisp numerical metrics has long been a hallmark of biological network analysis. However, typical graph metrics ignore regulatory signals that are crucially important for optimal pathway operation, for instance, in biochemical or metabolic studies. Here we introduce adjusted metrics that are applicable to both static networks and dynamic systems.

RESULTS

The metrics permit quantitative characterizations of the importance of regulation in biochemical pathway systems, including systems designed for applications in synthetic biology or metabolic engineering. They may also become criteria for effective model reduction.

AVAILABILITY AND IMPLEMENTATION

The source code is available at https://gitlab.com/tienbien44/metrics-bsa.

Intergroup networks as random threshold graphs

Similar-minded people tend to form social groups. Due to pluralistic homophily as well as a sort of heterophily, people also participate in a wide variety of groups. Thus, these groups generally overlap with each other; an overlap between two groups can be characterized by the number of common members. These common members can play a crucial role in the transmission of information between the groups. As a step towards understanding the information dissemination, we perceive the system as a pruned intergroup network and show that it maps to a very basic graph theoretic concept known as a threshold graph. We analyze several structural properties of this network such as degree distribution, largest component size, edge density, and local clustering coefficient. We compare the theoretical predictions with the results obtained from several online social networks (LiveJournal, Flickr, YouTube) and find a good match.

Network evolution based on centrality

We study the evolution of networks when the creation and decay of links are based on the position of nodes in the network measured by their centrality. We show that the same network dynamics arise under various centrality measures, and solve analytically the network evolution. During the complete evolution, the network is characterized by nestedness: the neighborhood of a node is contained in the neighborhood of the nodes with larger degree. We find a discontinuous transition in the network density between hierarchical and homogeneous networks, depending on the rate of link decay. We also show that this evolution mechanism leads to double power-law degree distributions, with interrelated exponents.

Approximating spectral impact of structural perturbations in large networks

Determining the effect of structural perturbations on the eigenvalue spectra of networks is an important problem because the spectra characterize not only their topological structures, but also their dynamical behavior, such as synchronization and cascading processes on networks. Here we develop a theory for estimating the change of the largest eigenvalue of the adjacency matrix or the extreme eigenvalues of the graph Laplacian when small but arbitrary set of links are added or removed from the network. We demonstrate the effectiveness of our approximation schemes using both real and artificial networks, showing in particular that we can accurately obtain the spectral ranking of small subgraphs. We also propose a local iterative scheme which computes the relative ranking of a subgraph using only the connectivity information of its neighbors within a few links. Our results may not only contribute to our theoretical understanding of dynamical processes on networks, but also lead to practical applications in ranking subgraphs of real complex networks.

Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence

In general, the power-law degree distribution has profound influence on various dynamical processes defined on scale-free networks. In this paper, we will show that power-law degree distribution alone does not suffice to characterize the behavior of trapping problems on scale-free networks, which is an integral major theme of interest for random walks in the presence of an immobile perfect absorber. In order to achieve this goal, we study random walks on a family of one-parameter (denoted by q) scale-free networks with identical degree sequence for the full range of parameter q, in which a trap is located at a fixed site. We obtain analytically or numerically the mean first-passage time (MFPT) for the trapping issue. In the limit of large network order (number of nodes), for the whole class of networks, the MFPT increases asymptotically as a power-law function of network order with the exponent obviously different for different parameter q, which suggests that power-law degree distribution itself is not sufficient to characterize the scaling behavior of MFPT for random walks at least trapping problem, performed on scale-free networks.

Rewiring networks for synchronization

We study the synchronization of identical oscillators diffusively coupled through a network and examine how adding, removing, and moving single edges affects the ability of the network to synchronize. We present algorithms which use methods based on node degrees and based on spectral properties of the network Laplacian for choosing edges that most impact synchronization. We show that rewiring based on the network Laplacian eigenvectors is more effective at enabling synchronization than methods based on node degree for many standard network models. We find an algebraic relationship between the eigenstructure before and after adding an edge and describe an efficient algorithm for computing Laplacian eigenvalues and eigenvectors that uses the network or its complement depending on which is more sparse.

Sequence nets

We study a class of networks generated by sequences of letters taken from a finite alphabet consisting of m letters (corresponding to m types of nodes) and a fixed set of connectivity rules. Recently, it was shown how a binary alphabet might generate threshold nets in a similar fashion [A. Hagberg, Phys. Rev. E 74, 056116 (2006)]. Just like threshold nets, sequence nets in general possess a modular structure reminiscent of everyday-life nets and are easy to handle analytically (i.e., calculate degree distribution, shortest paths, betweenness centrality, etc.). Exploiting symmetry, we make a full classification of two- and three-letter sequence nets, discovering two classes of two-letter sequence nets. These sequence nets retain many of the desirable analytical properties of threshold nets while yielding richer possibilities for the modeling of everyday-life complex networks more faithfully.

Threshold Graph Limits and Random Threshold Graphs

We study the limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples for the emerging theory of graph limits.