Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIrreducible network backbones: unbiased graph filtering via maximum entropy
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Networks provide an informative, yet non-redundant description of complex systems only if links represent truly dyadic relationships that cannot be directly traced back to node-specific properties such as size, importance, or coordinates in some embedding space. In any real-world network, some links may be reducible, and others irreducible, to such local properties. This dichotomy persists despite the steady increase in data availability and resolution, which actually determines an even stronger need for filtering techniques aimed at discerning essential links from non-essential ones. Here we introduce a rigorous method that, for any desired level of statistical significance, outputs the network backbone that is irreducible to the local properties of nodes, i.e. their degrees and strengths. Unlike previous approaches, our method employs an exact maximum-entropy formulation guaranteeing that the filtered network encodes only the links that cannot be inferred from local information. Extensive empirical analysis confirms that this approach uncovers essential backbones that are otherwise hidden amidst many redundant relationships and inaccessible to other methods. For instance, we retrieve the hub-and-spoke skeleton of the US airport network and many specialised patterns of international trade. Being irreducible to local transportation and economic constraints of supply and demand, these backbones single out genuinely higher-order wiring principles.
rate research
Read More
The susceptible--infected--susceptible (SIS) epidemic process on complex networks can show metastability, resembling an endemic equilibrium. In a general setting, the metastable state may involve a large portion of the network, or it can be localized on small subgraphs of the contact network. Localized infections are not interesting because a true outbreak concerns network--wide invasion of the contact graph rather than localized infection of certain sites within the contact network. Existing approaches to localization phenomenon suffer from a major drawback: they fully rely on the steady--state solution of mean--field approximate models in the neighborhood of their phase transition point, where their approximation accuracy is worst; as statistical physics tells us. We propose a dispersion entropy measure that quantifies the localization of infections in a generic contact graph. Formulating a maximum entropy problem, we find an upper bound for the dispersion entropy of the possible metastable state in the exact SIS process. As a result, we find sufficient conditions such that any initial infection over the network either dies out or reaches a localized metastable state. Unlike existing studies relying on the solution of mean--field approximate models, our investigation of epidemic localization is based on characteristics of exact SIS equations. Our proposed method offers a new paradigm in studying spreading processes over complex networks.
Much effort has been devoted to understand how temporal network features and the choice of the source node affect the prevalence of a diffusion process. In this work, we addressed the further question: node pairs with what kind of local and temporal connection features tend to appear in a diffusion trajectory or path, thus contribute to the actual information diffusion. We consider the Susceptible-Infected spreading process with a given infection probability per contact on a large number of real-world temporal networks. We illustrate how to construct the information diffusion backbone where the weight of each link tells the probability that a node pair appears in a diffusion process starting from a random node. We unravel how these backbones corresponding to different infection probabilities relate to each other and point out the importance of two extreme backbones: the backbone with infection probability one and the integrated network, between which other backbones vary. We find that the temporal node pair feature that we proposed could better predict the links in the extreme backbone with infection probability one as well as the high weight links than the features derived from the integrated network. This universal finding across all the empirical networks highlights that temporal information are crucial in determining a node pairs role in a diffusion process. A node pair with many early contacts tends to appear in a diffusion process. Our findings shed lights on the in-depth understanding and may inspire the control of information spread.
In this paper, we reveal the relationship between entropy rate and the congestion in complex network and solve it analytically for special cases. Finding maximizing entropy rate will lead to an improvement of traffic efficiency, we propose a method to mitigate congestion by allocating limited traffic capacity to the nodes in network rationally. Different from former strategies, our method only requires local and observable information of network, and is low-cost and widely applicable in practice. In the simulation of the phase transition for various network models, our method performs well in mitigating congestion both locally and globally. By comparison, we also uncover the deficiency of former degree-biased approaches. Owing to the rapid development of transportation networks, our method may be helpful for modern society.
Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years a multitude of diverse, ad hoc solutions to this problem have been introduced. Here we propose that simple and well-understood ensembles of random networks (such as ErdH{o}s-R{e}nyi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model, and preferential attachment networks) are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.
Interactions between elements, which are usually represented by networks, have to delineate potentially unequal relationships in terms of their relative importance or direction. The intrinsic unequal relationships of such kind, however, are opaque or hidden in numerous real systems.For instance, when a node in a network with limited interaction capacity spends its capacity to its neighboring nodes, the allocation of the total amount of interactions to them can be vastly diverse. Even if such potentially heterogeneous interactions epitomized by weighted networks are observable, as a result of the aforementioned ego-centric allocation of interactions, the relative importance or dependency between two interacting nodes can only be implicitly accessible. In this work, we precisely pinpoint such relative dependency by proposing the framework to discover hidden dependent relations extracted from weighted networks. For a given weighted network, we provide a systematic criterion to select the most essential interactions for individual nodes based on the concept of information entropy. The criterion is symbolized by assigning the effective number of neighbors or the effective out-degree to each node, and the resultant directed subnetwork decodes the hidden dependent relations by leaving only the most essential directed interactions. We apply our methodology to two time-stamped empirical network data, namely the international trade relations between nations in the world trade web (WTW) and the network of people in the historical record of Korea, Annals of the Joseon Dynasty (AJD). Based on the data analysis, we discover that the properties of mutual dependency encoded in the two systems are vastly different.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
