Cycles and clustering in bipartite networks

Hyperedge overlap drives explosive transitions in systems with higher-order interactions

Recent studies have shown that novel collective behaviors emerge in complex systems due to the presence of higher-order interactions. However, how the collective behavior of a system is influenced by the microscopic organization of its higher-order interactions is not fully understood. In this work, we introduce a way to quantify the overlap among the hyperedges of a higher-order network, and we show that real-world systems exhibit different levels of intra-order hyperedge overlap. We then study two types of dynamical processes on higher-order networks, namely complex contagion and synchronization, finding that intra-order hyperedge overlap plays a universal role in determining the collective behavior in a variety of systems. Our results demonstrate that the presence of higher-order interactions alone does not guarantee abrupt transitions. Rather, explosivity and bistability require a microscopic organization of the structure with a low value of intra-order hyperedge overlap.

Node features of chromosome structure networks and their connections to genome annotation

The 3D conformations of chromosomes can encode biological significance, and the implications of such structures have been increasingly appreciated recently. Certain chromosome structural features, such as A/B compartmentalization, are frequently extracted from Hi-C pairwise genome contact information (physical association between different regions of the genome) and compared with linear annotations of the genome, such as histone modifications and lamina association. We investigate how additional properties of chromosome structure can be deduced using an abstract graph representation of the contact heatmap, and describe specific network properties that can have a strong connection with some of these biological annotations. We constructed chromosome structure networks (CSNs) from bulk Hi-C data and calculated a set of site-resolved (node-based) network properties. These properties are useful for characterizing certain aspects of chromosomal structure. We examined the ability of network properties to differentiate several scenarios, such as haploid vs diploid cells, partially inverted nuclei vs conventional architecture, depletion of chromosome architectural proteins, and structural changes during cell development. We also examined the connection between network properties and a series of other linear annotations, such as histone modifications and chromatin states including poised promoter and enhancer labels. We found that semi-local network properties exhibit greater capability in characterizing genome annotations compared to diffusive or ultra-local node features. For example, the local square clustering coefficient can be a strong classifier of lamina-associated domains. We demonstrated that network properties can be useful for highlighting large-scale chromosome structure differences that emerge in different biological situations.

Reaction Networks Resemble Low-Dimensional Regular Lattices

The computational exploration, manipulation, and design of complex chemical reactions face fundamental challenges related to the high-dimensional nature of potential energy surfaces (PESs) that govern reactivity. Accurately modeling complex reactions is crucial for understanding the chemical processes involved in, for example, organocatalysis, autocatalytic cycles, and one-pot molecular assembly. Our prior research demonstrated that discretizing PESs using heuristics based on bond breaking and bond formation produces a reaction network representation with a low-dimensional structure (metric space). We now find that these stoichiometry-preserving reaction networks possess additional, though approximate, structure and resemble low-dimensional regular lattices with a small amount of random edge rewiring. The heuristics-based discretization thus generates a nonlinear dimensionality reduction by a factor of 10 with an a posteriori error measure (probability of random rewiring). The structure becomes evident through a comparative analysis of CHNO reaction networks of varying stoichiometries against a panel of size-matched generative network models, taking into account their local, metric, and global properties. The generative models include random networks (Erdős-Rényi and bipartite random networks), regular lattices (periodic and nonperiodic), and network models with a tunable level of "randomness" (Watts-Strogatz graphs and regular lattices with random rewiring). The CHNO networks are simultaneously closely matched in all these properties by 3-4-dimensional regular lattices with 10% or less of edges randomly rewired. The effective dimensionality reduction is found to be independent of the system size, stoichiometry, and ruleset, suggesting that search and sampling algorithms for PESs of complex chemical reactions can be effectively leveraged.

Clustering coefficients for networks with higher order interactions

We introduce a clustering coefficient for nondirected and directed hypergraphs, which we call the quad clustering coefficient. We determine the average quad clustering coefficient and its distribution in real-world hypergraphs and compare its value with those of random hypergraphs drawn from the configuration model. We find that real-world hypergraphs exhibit a nonnegligible fraction of nodes with a maximal value of the quad clustering coefficient, while we do not find such nodes in random hypergraphs. Interestingly, these highly clustered nodes can have large degrees and can be incident to hyperedges of large cardinality. Moreover, highly clustered nodes are not observed in an analysis based on the pairwise clustering coefficient of the associated projected graph that has binary interactions, and hence higher order interactions are required to identify nodes with a large quad clustering coefficient.

Hodge Laplacian of Brain Networks

The closed loops or cycles in a brain network embeds higher order signal transmission paths, which provide fundamental insights into the functioning of the brain. In this work, we propose an efficient algorithm for systematic identification and modeling of cycles using persistent homology and the Hodge Laplacian. Various statistical inference procedures on cycles are developed. We validate the our methods on simulations and apply to brain networks obtained through the resting state functional magnetic resonance imaging. The computer codes for the Hodge Laplacian are given in https://github.com/laplcebeltrami/hodge.

(p,q)-biclique counting and enumeration for large sparse bipartite graphs

In this paper, we study the problem of (p , q )-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite graph G = ( U , V , E ) and two integer parameters p and q, we aim to efficiently count and enumerate all (p , q )-bicliques in G, where a (p , q )-biclique B(L, R) is a complete subgraph of G with L ⊆ U , R ⊆ V , | L | = p , and | R | = q . The problem of (p , q )-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature . This problem is computationally challenging, due to the worst-case exponential number of (p , q )-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q . To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer-based exploring strategy to enumerate (p , q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p , q )-bicliques optimizes the efficiency of graph neural networks. In this paper, we extend our techniques to count and enumerate (p , q )-bicliques on uncertain bipartite graphs. An efficient method IUBCList is developed on the top of BCList++, together with a couple of pruning techniques, including common neighbor refinement and search branch early termination, to discard unpromising uncertain (p , q )-bicliques early. The experimental results demonstrate that IUBCList significantly outperforms the baseline method by up to 2 orders of magnitude.

Topological data analysis of human brain networks through order statistics

Understanding the common topological characteristics of the human brain network across a population is central to understanding brain functions. The abstraction of human connectome as a graph has been pivotal in gaining insights on the topological properties of the brain network. The development of group-level statistical inference procedures in brain graphs while accounting for the heterogeneity and randomness still remains a difficult task. In this study, we develop a robust statistical framework based on persistent homology using the order statistics for analyzing brain networks. The use of order statistics greatly simplifies the computation of the persistent barcodes. We validate the proposed methods using comprehensive simulation studies and subsequently apply to the resting-state functional magnetic resonance images. We found a statistically significant topological difference between the male and female brain networks.

Detecting Square Grid Structure in an Animal Neuronal Network

An animal neural system ranges from a cluster of a few neurons to a brain of billions. At the lower range, it is possible to test each neuron for its role across a set of environmental conditions. However, the higher range requires another approach. One method is to disentangle the organization of the neuronal network. In the case of the entorhinal cortex in a rodent, a set of neuronal cells involved in spatial location activate in a regular grid-like arrangement. Therefore, it is of interest to develop methods to find these kinds of patterns in a neural network. For this study, a square grid arrangement of neurons is quantified by network metrics and then applied for identification of square grid structure in areas of the fruit fly brain. The results show several regions with contiguous clusters of square grid arrangements in the neural network, supportive of specialization in the information processing of the system.

Microstructural Characteristics of the Weighted and Directed International Crop Trade Networks

With increasing global demand for food, international food trade is playing a critical role in balancing the food supply and demand across different regions. Here, using trade datasets of four crops that provide more than 50% of the calories consumed globally, we constructed four international crop trade networks (iCTNs). We observed the increasing globalization in the international crop trade and different trade patterns in different iCTNs. The distributions of node degrees deviate from power laws, and the distributions of link weights follow power laws. We also found that the in-degree is positively correlated with the out-degree, but negatively correlated with the clustering coefficient. This indicates that the numbers of trade partners affect the tendency of economies to form clusters. In addition, each iCTN exhibits a unique topology which is different from the whole food network studied by many researchers. Our analysis on the microstructural characteristics of different iCTNs provides highly valuable insights into distinctive features of specific crop trades and has potential implications for model construction and food security.

Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties

Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe's Quartet demonstrates how such statistics can be misleading. We consider a similar problem in the context of graph mining. To study the relationships between different graph properties, we examine low-order non-isomorphic graphs and provide a simple visual analytics system to explore correlations across multiple graph properties. However, for larger graphs, studying the entire space quickly becomes intractable. We use different random graph generation methods to further look into the distribution of graph properties for higher order graphs and investigate the impact of various sampling methodologies. We also describe a method for generating many graphs that are identical over a number of graph properties and statistics yet are clearly different and identifiably distinct.

Network science characteristics of brain-derived neuronal cultures deciphered from quantitative phase imaging data

Understanding the mechanisms by which neurons create or suppress connections to enable communication in brain-derived neuronal cultures can inform how learning, cognition and creative behavior emerge. While prior studies have shown that neuronal cultures possess self-organizing criticality properties, we further demonstrate that in vitro brain-derived neuronal cultures exhibit a self-optimization phenomenon. More precisely, we analyze the multiscale neural growth data obtained from label-free quantitative microscopic imaging experiments and reconstruct the in vitro neuronal culture networks (microscale) and neuronal culture cluster networks (mesoscale). We investigate the structure and evolution of neuronal culture networks and neuronal culture cluster networks by estimating the importance of each network node and their information flow. By analyzing the degree-, closeness-, and betweenness-centrality, the node-to-node degree distribution (informing on neuronal interconnection phenomena), the clustering coefficient/transitivity (assessing the “small-world” properties), and the multifractal spectrum, we demonstrate that murine neurons exhibit self-optimizing behavior over time with topological characteristics distinct from existing complex network models. The time-evolving interconnection among murine neurons optimizes the network information flow, network robustness, and self-organization degree. These findings have complex implications for modeling neuronal cultures and potentially on how to design biological inspired artificial intelligence.

Recommendation decision-making algorithm for sharing accommodation using probabilistic hesitant fuzzy sets and bipartite network projection

In recent years, with the uninterrupted development of sharing accommodation, it not only caters to the diversified accommodation of tourists, but also takes an active role in expanding employment and entrepreneurship channels, enhancing the income of urban and rural residents, and promoting the revitalization of rural areas. However, with the continuous expansion of the scale of sharing accommodation, it is fairly complicated for users to search appropriate services or information. The decision-making problems become more and more complicated. Hence, a probabilistic hesitant fuzzy recommendation decision-making algorithm based on bipartite network projection is proposed in this paper. First of all, combining the users’ decision-making information and the experts’ evaluation information, a bipartite graph connecting users and alternatives is established. Then, the satisfaction degree of probabilistic hesitant fuzzy element is defined. Besides, the recommended alternative is obtained by the allocation of resources. Finally, a numerical case of Airbnb users is given to illustrate the feasibility and effectiveness of the proposed method.

STATISTICAL INFERENCE ON THE NUMBER OF CYCLES IN BRAIN NETWORKS

A cycle in a graph is a subset of a connected component with redundant additional connections. If there are many cycles in a connected component, the connected component is more densely connected. While the number of connected components represents the integration of the brain network, the number of cycles represents how strong the integration is. However, enumerating cycles in the network is not easy and often requires brute force enumerations. In this study, we present a new scalable algorithm for enumerating the number of cycles in the network. We show that the number of cycles is monotonically decreasing with respect to the filtration values during graph filtration. We further develop a new statistical inference framework for determining the significance of the number of cycles. The methods are applied in determining if the number of cycles is a statistically significant heritable network feature in the functional human brain network.

Exact topological inference of the resting-state brain networks in twins

A cycle in a brain network is a subset of a connected component with redundant additional connections. If there are many cycles in a connected component, the connected component is more densely connected. Whereas the number of connected components represents the integration of the brain network, the number of cycles represents how strong the integration is. However, it is unclear how to perform statistical inference on the number of cycles in the brain network. In this study, we present a new statistical inference framework for determining the significance of the number of cycles through the Kolmogorov-Smirnov (KS) distance, which was recently introduced to measure the similarity between networks across different filtration values by using the zeroth Betti number. In this paper, we show how to extend the method to the first Betti number, which measures the number of cycles. The performance analysis was conducted using the random network simulations with ground truths. By using a twin imaging study, which provides biological ground truth, the methods are applied in determining if the number of cycles is a statistically significant heritable network feature in the resting-state functional connectivity in 217 twins obtained from the Human Connectome Project. The MATLAB codes as well as the connectivity matrices used in generating results are provided at http://www.stat.wisc.edu/∼mchung/TDA.

In this paper, we propose a new topological distance based on the Kolmogorov-Smirnov (KS) distance that is adapted for brain networks, and compare them against other topological network distances including the Gromov-Hausdorff (GH) distances. KS-distance is recently introduced to measure the similarity between networks across different filtration values by using the zeroth Betti number, which measures the number of connected components. In this paper, we show how to extend the method to the first Betti number, which measures the number of cycles. The performance analysis was conducted using random network simulations with ground truths. Using a twin imaging study, which provides biological ground truth (of network differences), we demonstrate that the KS distances on the zeroth and first Betti numbers have the ability to determine heritability.

Memristive nanowires exhibit small-world connectivity

Small-world networks provide an excellent balance of efficiency and robustness that is not available with other network topologies. These characteristics are exhibited in the Memristive Nanowire Neural Network (MN³), a novel neuromorphic hardware architecture. This architecture is composed of an electrode array connected by stochastically deposited core-shell nanowires. We simulate the stochastic behavior of the nanowires by making various assumptions on their paths. First, we assume that the nanowires follow straight paths. Next, we assume that they follow arc paths with varying radii. Last, we assume that they follow paths generated by pink noise. For each of the three methods, we present a method to find whether a nanowire passes over an electrode, allowing us to represent the architecture as a bipartite graph. We find that the small-worldness coefficient increases logarithmically and is consistently greater than one, which is indicative of a small-world network.

Bipartite graphs in systems biology and medicine: a survey of methods and applications

The latest advances in high-throughput techniques during the past decade allowed the systems biology field to expand significantly. Today, the focus of biologists has shifted from the study of individual biological components to the study of complex biological systems and their dynamics at a larger scale. Through the discovery of novel bioentity relationships, researchers reveal new information about biological functions and processes. Graphs are widely used to represent bioentities such as proteins, genes, small molecules, ligands, and others such as nodes and their connections as edges within a network. In this review, special focus is given to the usability of bipartite graphs and their impact on the field of network biology and medicine. Furthermore, their topological properties and how these can be applied to certain biological case studies are discussed. Finally, available methodologies and software are presented, and useful insights on how bipartite graphs can shape the path toward the solution of challenging biological problems are provided.

Fractal and multifractal analyses of bipartite networks

Bipartite networks have attracted considerable interest in various fields. Fractality and multifractality of unipartite (classical) networks have been studied in recent years, but there is no work to study these properties of bipartite networks. In this paper, we try to unfold the self-similarity structure of bipartite networks by performing the fractal and multifractal analyses for a variety of real-world bipartite network data sets and models. First, we find the fractality in some bipartite networks, including the CiteULike, Netflix, MovieLens (ml-20m), Delicious data sets and (u, v)-flower model. Meanwhile, we observe the shifted power-law or exponential behavior in other several networks. We then focus on the multifractal properties of bipartite networks. Our results indicate that the multifractality exists in those bipartite networks possessing fractality. To capture the inherent attribute of bipartite network with two types different nodes, we give the different weights for the nodes of different classes, and show the existence of multifractality in these node-weighted bipartite networks. In addition, for the data sets with ratings, we modify the two existing algorithms for fractal and multifractal analyses of edge-weighted unipartite networks to study the self-similarity of the corresponding edge-weighted bipartite networks. The results show that our modified algorithms are feasible and can effectively uncover the self-similarity structure of these edge-weighted bipartite networks and their corresponding node-weighted versions.

Ensemble Classification of Alzheimer's Disease and Mild Cognitive Impairment Based on Complex Graph Measures from Diffusion Tensor Images

The human brain is a complex network of interacting regions. The gray matter regions of brain are interconnected by white matter tracts, together forming one integrative complex network. In this article, we report our investigation about the potential of applying brain connectivity patterns as an aid in diagnosing Alzheimer's disease and Mild Cognitive Impairment (MCI). We performed pattern analysis of graph theoretical measures derived from Diffusion Tensor Imaging (DTI) data representing structural brain networks of 45 subjects, consisting of 15 patients of Alzheimer's disease (AD), 15 patients of MCI, and 15 healthy subjects (CT). We considered pair-wise class combinations of subjects, defining three separate classification tasks, i.e., AD-CT, AD-MCI, and CT-MCI, and used an ensemble classification module to perform the classification tasks. Our ensemble framework with feature selection shows a promising performance with classification accuracy of 83.3% for AD vs. MCI, 80% for AD vs. CT, and 70% for MCI vs. CT. Moreover, our findings suggest that AD can be related to graph measures abnormalities at Brodmann areas in the sensorimotor cortex and piriform cortex. In this way, node redundancy coefficient and load centrality in the primary motor cortex were recognized as good indicators of AD in contrast to MCI. In general, load centrality, betweenness centrality, and closeness centrality were found to be the most relevant network measures, as they were the top identified features at different nodes. The present study can be regarded as a "proof of concept" about a procedure for the classification of MRI markers between AD dementia, MCI, and normal old individuals, due to the small and not well-defined groups of AD and MCI patients. Future studies with larger samples of subjects and more sophisticated patient exclusion criteria are necessary toward the development of a more precise technique for clinical diagnosis.

Network clustering and community detection using modulus of families of loops

We study the structure of loops in networks using the notion of modulus of loop families. We introduce an alternate measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link usage optimally. We propose weighting networks using these expected link usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks.

Automatic Identification of Character Types from Film Dialogs

We study the detection of character types from fictional dialog texts such as screenplays. As approaches based on the analysis of utterances' linguistic properties are not sufficient to identify all fictional character types, we develop an integrative approach that complements linguistic analysis with interactive and communication characteristics, and show that it can improve the identification performance. The interactive characteristics of fictional characters are captured by the descriptive analysis of semantic graphs weighted by linguistic markers of expressivity and social role. For this approach, we introduce a new data set of action movie character types with their corresponding sequences of dialogs. The evaluation results demonstrate that the integrated approach outperforms baseline approaches on the presented data set. Comparative in-depth analysis of a single screenplay leads on to the discussion of possible limitations of this approach and to directions for future research.

Uncovering the essential links in online commercial networks

Recommender systems are designed to effectively support individuals' decision-making process on various web sites. It can be naturally represented by a user-object bipartite network, where a link indicates that a user has collected an object. Recently, research on the information backbone has attracted researchers' interests, which is a sub-network with fewer nodes and links but carrying most of the relevant information. With the backbone, a system can generate satisfactory recommenda- tions while saving much computing resource. In this paper, we propose an enhanced topology-aware method to extract the information backbone in the bipartite network mainly based on the information of neighboring users and objects. Our backbone extraction method enables the recommender systems achieve more than 90% of the accuracy of the top-L recommendation, however, consuming only 20% links. The experimental results show that our method outperforms the alternative backbone extraction methods. Moreover, the structure of the information backbone is studied in detail. Finally, we highlight that the information backbone is one of the most important properties of the bipartite network, with which one can significantly improve the efficiency of the recommender system.

The Double-Stranded DNA Virosphere as a Modular Hierarchical Network of Gene Sharing

Virus genomes are prone to extensive gene loss, gain, and exchange and share no universal genes. Therefore, in a broad-scale study of virus evolution, gene and genome network analyses can complement traditional phylogenetics. We performed an exhaustive comparative analysis of the genomes of double-stranded DNA (dsDNA) viruses by using the bipartite network approach and found a robust hierarchical modularity in the dsDNA virosphere. Bipartite networks consist of two classes of nodes, with nodes in one class, in this case genomes, being connected via nodes of the second class, in this case genes. Such a network can be partitioned into modules that combine nodes from both classes. The bipartite network of dsDNA viruses includes 19 modules that form 5 major and 3 minor supermodules. Of these modules, 11 include tailed bacteriophages, reflecting the diversity of this largest group of viruses. The module analysis quantitatively validates and refines previously proposed nontrivial evolutionary relationships. An expansive supermodule combines the large and giant viruses of the putative order "Megavirales" with diverse moderate-sized viruses and related mobile elements. All viruses in this supermodule share a distinct morphogenetic tool kit with a double jelly roll major capsid protein. Herpesviruses and tailed bacteriophages comprise another supermodule, held together by a distinct set of morphogenetic proteins centered on the HK97-like major capsid protein. Together, these two supermodules cover the great majority of currently known dsDNA viruses. We formally identify a set of 14 viral hallmark genes that comprise the hubs of the network and account for most of the intermodule connections.

IMPORTANCE

Viruses and related mobile genetic elements are the dominant biological entities on earth, but their evolution is not sufficiently understood and their classification is not adequately developed. The key reason is the characteristic high rate of virus evolution that involves not only sequence change but also extensive gene loss, gain, and exchange. Therefore, in the study of virus evolution on a large scale, traditional phylogenetic approaches have limited applicability and have to be complemented by gene and genome network analyses. We applied state-of-the art methods of such analysis to reveal robust hierarchical modularity in the genomes of double-stranded DNA viruses. Some of the identified modules combine highly diverse viruses infecting bacteria, archaea, and eukaryotes, in support of previous hypotheses on direct evolutionary relationships between viruses from the three domains of cellular life. We formally identify a set of 14 viral hallmark genes that hold together the genomic network.

Critical time scale of coarse-graining entropy production

We study coarse-grained entropy production in an asymmetric random walk system on a periodic one-dimensional lattice. In coarse-grained systems, the original dynamics are unavoidably destroyed, but the coarse-grained entropy production is not hidden below the critical time-scale separation. The hidden entropy production is rapidly increasing near the critical time-scale separation.

Biconnectivity of the cellular metabolism: A cross-species study and its implication for human diseases

The maintenance of stability during perturbations is essential for living organisms, and cellular networks organize multiple pathways to enable elements to remain connected and communicate, even when some pathways are broken. Here, we evaluated the biconnectivity of the metabolic networks of 506 species in terms of the clustering coefficients and the largest biconnected components (LBCs), wherein a biconnected component (BC) indicates a set of nodes in which every pair is connected by more than one path. Via comparison with the rewired networks, we illustrated how biconnectivity in cellular metabolism is achieved on small and large scales. Defining the biconnectivity of individual metabolic compounds by counting the number of species in which the compound belonged to the LBC, we demonstrated that biconnectivity is significantly correlated with the evolutionary age and functional importance of a compound. The prevalence of diseases associated with each metabolic compound quantifies the compounds vulnerability, i.e., the likelihood that it will cause a metabolic disorder. Moreover, the vulnerability depends on both the biconnectivity and the lethality of the compound. This fact can be used in drug discovery and medical treatments.

Complex networks from space-filling bearings

Two-dimensional space-filling bearings are dense packings of disks that can rotate without slip. We consider the entire first family of bearings for loops of four disks and propose a hierarchical construction of their contact network. We provide analytic expressions for the clustering coefficient and degree distribution, revealing bipartite scale-free behavior with a tunable degree exponent depending on the bearing parameters. We also analyze their average shortest path and percolation properties.

Complex reaction networks in high temperature hydrocarbon chemistry

Complex network theory reveals novel insights into the chemical kinetics of high temperature hydrocarbon decomposition.

Extracting the information backbone in online system

Information overload is a serious problem in modern society and many solutions such as recommender system have been proposed to filter out irrelevant information. In the literature, researchers have been mainly dedicated to improving the recommendation performance (accuracy and diversity) of the algorithms while they have overlooked the influence of topology of the online user-object bipartite networks. In this paper, we find that some information provided by the bipartite networks is not only redundant but also misleading. With such “less can be more” feature, we design some algorithms to improve the recommendation performance by eliminating some links from the original networks. Moreover, we propose a hybrid method combining the time-aware and topology-aware link removal algorithms to extract the backbone which contains the essential information for the recommender systems. From the practical point of view, our method can improve the performance and reduce the computational time of the recommendation system, thus improving both of their effectiveness and efficiency.

Spectral coarse graining for random walks in bipartite networks

Many real-world networks display a natural bipartite structure, yet analyzing and visualizing large bipartite networks is one of the open challenges in complex network research. A practical approach to this problem would be to reduce the complexity of the bipartite system while at the same time preserve its functionality. However, we find that existing coarse graining methods for monopartite networks usually fail for bipartite networks. In this paper, we use spectral analysis to design a coarse graining scheme specific for bipartite networks, which keeps their random walk properties unchanged. Numerical analysis on both artificial and real-world networks indicates that our coarse graining can better preserve most of the relevant spectral properties of the network. We validate our coarse graining method by directly comparing the mean first passage time of the walker in the original network and the reduced one.

Clustering drives assortativity and community structure in ensembles of networks

Clustering, assortativity, and communities are key features of complex networks. We probe dependencies between these features and find that ensembles of networks with high clustering display both high assortativity by degree and prominent community structure, while ensembles with high assortativity show much less enhancement of the clustering or community structure. Further, clustering can amplify a small homophilic bias for trait assortativity in network ensembles. This marked asymmetry suggests that transitivity could play a larger role than homophily in determining the structure of many complex networks.

Complex networks in confined comminution

The physical process of confined comminution is investigated within the framework of complex networks. We first characterize the topology of the unweighted contact networks as generated by the confined comminution process. We find this process gives rise to an ultimate contact network which exhibits a scale-free degree distribution and small world properties. In particular, if viewed in the context of networks through which information travels along shortest paths, we find that the global average of the node vulnerability decreases as the comminution process continues, with individual node vulnerability correlating with grain size. A possible application to the design of synthetic networks (e.g., sensor networks) is highlighted. Next we turn our attention to the physics of the granular comminution process and examine force transmission with respect to the weighted contact networks, where each link is weighted by the inverse magnitude of the normal force acting at the associated contact. We find that the strong forces (i.e., force chains) are transmitted along pathways in the network which are mainly following shortest-path routing protocols, as typically found, for example, in communication systems. Motivated by our earlier studies of the building blocks for self-organization in dense granular systems, we also explore the properties of the minimal contact cycles. The distribution of the contact strain energy intensity of 4-cycle motifs in the ultimate state of the confined comminution process is shown to be consistent with a scale-free distribution with infinite variance, thereby suggesting that 4-cycle arrangements of grains are capable of storing vast amounts of energy in their contacts without breaking.

Hidden variables in bipartite networks

We introduce and study random bipartite networks with hidden variables. Nodes in these networks are characterized by hidden variables that control the appearance of links between node pairs. We derive analytic expressions for the degree distribution, degree correlations, the distribution of the number of common neighbors, and the bipartite clustering coefficient in these networks. We also establish the relationship between degrees of nodes in original bipartite networks and in their unipartite projections. We further demonstrate how hidden variable formalism can be applied to analyze topological properties of networks in certain bipartite network models, and verify our analytical results in numerical simulations.

Competition for popularity in bipartite networks

We present a dynamical model for rewiring and attachment in bipartite networks. Edges are placed between nodes that belong to catalogs that can either be fixed in size or growing in size. The model is motivated by an empirical study of data from the video rental service Netflix, which invites its users to give ratings to the videos available in its catalog. We find that the distribution of the number of ratings given by users and that of the number of ratings received by videos both follow a power law with an exponential cutoff. We also examine the activity patterns of Netflix users and find bursts of intense video-rating activity followed by long periods of inactivity. We derive ordinary differential equations to model the acquisition of edges by the nodes over time and obtain the corresponding time-dependent degree distributions. We then compare our results with the Netflix data and find good agreement. We conclude with a discussion of how catalog models can be used to study systems in which agents are forced to choose, rate, or prioritize their interactions from a large set of options.

When metabolism meets topology: Reconciling metabolite and reaction networks

The search for a systems-level picture of metabolism as a web of molecular interactions provides a paradigmatic example of how the methods used to characterize a system can bias the interpretation of its functional meaning. Metabolic maps have been analyzed using novel techniques from network theory, revealing some non-trivial, functionally relevant properties. These include a small-world structure and hierarchical modularity. However, as discussed here, some of these properties might actually result from an inappropriate way of defining network interactions. Starting from the so-called bipartite organization of metabolism, where the two meaningful subsets (reactions and metabolites) are considered, most current works use only one of the subsets by means of so-called graph projections. Unfortunately, projected graphs often ignore relevant biological and chemical constraints, thus leading to statistical artifacts. Some of these drawbacks and alternative approaches need to be properly addressed.

Unevenness of loop location in complex networks

The loop structure plays an important role in many aspects of complex networks and attracts much attention. Among the previous works, Bianconi [Phys. Rev. Lett. 100, 118701 (2008)] found that real networks often have very few short loops as compared to random models. In this paper, we focus on the uneven location of loops which makes some parts of the network rich while some other parts sparse in loops. We propose a node removing process to analyze the unevenness and find rich loop cores can exist in many real networks such as neural networks and food web networks. Finally, an index is presented to quantify the unevenness of loop location in complex networks.

Information mobility in complex networks

The concept of information mobility in complex networks is introduced on the basis of a stochastic process taking place in the network. The transition matrix for this process represents the probability that the information arising at a given node is transferred to a target one. We use the fractional powers of this transition matrix to investigate the stochastic process at fractional time intervals. The mobility coefficient is then introduced on the basis of the trace of these fractional powers of the stochastic matrix. The fractional time at which a network diffuses 50% of the information contained in its nodes (1/k(50)) is also introduced. We then show that the scale-free random networks display a better spread of information than the non-scale-free ones. We study 38 real-world networks and analyze their performance in spreading information from their nodes. We find that some real-world networks perform even better than the scale-free networks with the same average degree and we point out some of the structural parameters that make this possible.

Empirical analysis of Internet telephone network: from user ID to phone

In order to study the interaction between different communication networks, in this paper, personal computer (PC)-to-phone log data in the year of 2007 are collected from UUCALL database and described as an ID-to-phone bipartite network (ItPBN). The ItPBN contains one giant component (GC) and a large number of satellitic components (SCs), both of which are carefully analyzed. It is found that the ItPBN has power-law incoming/outgoing degree distributions as well as a power-law clustering function (by proposing a new definition of clustering coefficient) indicating a hierarchical and modular structure of the ItPBN. Furthermore, the fact that most of the weak links always surrounding those ID nodes of large degree in the GC suggests that weak links may be more important to keep the structure of the GC than those strong ones. More interestingly, it is also revealed that there is strong correlation between many statistical properties of different SCs and their size, these extra information may be very useful in modeling the ItPBN in the future.

Communicability and multipartite structures in complex networks at negative absolute temperatures

We here present a method of clearly identifying multipartite subgraphs in a network. The method is based on a recently introduced concept of the communicability, which very clearly identifies communities in a complex network. We here show that, while the communicability at a positive temperature is useful in identifying communities, the communicability at a negative temperature is useful in identifying multipartite subgraphs; the latter quantity between two nodes is positive when the two nodes belong to the same subgraph and is negative when they do not. The method is able to discover "almost" multipartite structures, where intercommunity connections vastly outweigh intracommunity connections. We illustrate the relevance of this work to real-life food web and protein-protein interaction networks.

Stability of synchronized states in networks of phase oscillators

The stability of synchronized states (frequency locked states) in networks of phase oscillators is investigated for several network topologies. It is shown that for some topologies there is more than one stable synchronized state according to the sign of coupling strength between oscillators. It is also shown that in some cases the synchronized state corresponds to zero order parameter.

Vulnerability of a killer whale social network to disease outbreaks

Emerging infectious diseases are among the main threats to conservation of biological diversity. A crucial task facing epidemiologists is to predict the vulnerability of populations of endangered animals to disease outbreaks. In this context, the network structure of social interactions within animal populations may affect disease spreading. However, endangered animal populations are often small and to investigate the dynamics of small networks is a difficult task. Using network theory, we show that the social structure of an endangered population of mammal-eating killer whales is vulnerable to disease outbreaks. This feature was found to be a consequence of the combined effects of the topology and strength of social links among individuals. Our results uncover a serious challenge for conservation of the species and its ecosystem. In addition, this study shows that the network approach can be useful to study dynamical processes in very small networks.

Bipartite network projection and personal recommendation

One-mode projecting is extensively used to compress bipartite networks. Since one-mode projection is always less informative than the bipartite representation, a proper weighting method is required to better retain the original information. In this article, inspired by the network-based resource-allocation dynamics, we raise a weighting method which can be directly applied in extracting the hidden information of networks, with remarkably better performance than the widely used global ranking method as well as collaborative filtering. This work not only provides a creditable method for compressing bipartite networks, but also highlights a possible way for the better solution of a long-standing challenge in modern information science: How to do a personal recommendation.

Critical behavior of the contact process in a multiscale network

Inspired by dengue and yellow fever epidemics, we investigated the contact process (CP) in a multiscale network constituted by one-dimensional chains connected through a Barabási-Albert scale-free network. In addition to the CP dynamics inside the chains, the exchange of individuals between connected chains (travels) occurs at a constant rate. A finite epidemic threshold and an epidemic mean lifetime diverging exponentially in the subcritical phase, concomitantly with a power law divergence of the outbreak's duration, were found. A generalized scaling function involving both regular and SF components was proposed for the quasistationary analysis and the associated critical exponents determined, demonstrating that the CP on this hybrid network and nonvanishing travel rates establishes a new universality class.

Spreading gossip in social networks

We study a simple model of information propagation in social networks, where two quantities are introduced: the spread factor, which measures the average maximal reachability of the neighbors of a given node that interchange information among each other, and the spreading time needed for the information to reach such a fraction of nodes. When the information refers to a particular node at which both quantities are measured, the model can be taken as a model for gossip propagation. In this context, we apply the model to real empirical networks of social acquaintances and compare the underlying spreading dynamics with different types of scale-free and small-world networks. We find that the number of friendship connections strongly influences the probability of being gossiped. Finally, we discuss how the spread factor is able to be applied to other situations.

Degree landscapes in scale-free networks

We generalize the degree-organizational view of real-world networks with broad degree distributions in a landscape analog with mountains (high-degree nodes) and valleys (low-degree nodes). For example, correlated degrees between adjacent nodes correspond to smooth landscapes (social networks), hierarchical networks to one-mountain landscapes (the Internet), and degree-disassortative networks without hierarchical features to rough landscapes with several mountains. To quantify the topology, we here measure the widths of the mountains and the separation between different mountains. We also generate ridge landscapes to model networks organized under constraints imposed by the space the networks are embedded in, associated to spatial or in molecular networks to functional localization.