Month: December 2020

Edge-based analysis of networks: curvatures of graphs and hypergraphs

Marzieh Eidi, Amirhossein Farzam, Wilmer Leal, Areejit Samal & Jürgen Jost
Theory in Biosciences volume 139, pages337–348(2020)

The relations, rather than the elements, constitute the structure of networks. We therefore develop a systematic approach to the analysis of networks, modelled as graphs or hypergraphs, that is based on structural properties of (hyper)edges, instead of vertices. For that purpose, we utilize so-called network curvatures. These curvatures quantify the local structural properties of (hyper)edges, that is, how, and how well, they are connected to others. In the case of directed networks, they assess the input they receive and the output they produce, and relations between them. With those tools, we can investigate biological networks. As examples, we apply our methods here to protein–protein interaction, transcriptional regulatory and metabolic networks.

Read the full article at: link.springer.com

Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

Artem Kaznatcheev, David Cohen, Peter Jeavons

JAIR Vol. 69 (2020)

Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness landscapes can be represented using valued constraints, and investigate what the structure of such representations reveals about the complexity of local search.
First, we show that for fitness landscapes representable by binary Boolean valued constraints there is a minimal necessary constraint graph that can be easily computed. Second, we consider landscapes as equivalent if they allow the same (improving) local search moves; we show that a minimal constraint graph still exists, but is NP-hard to compute.
We then develop several techniques to bound the length of any sequence of local search moves. We show that such a bound can be obtained from the numerical values of the constraints in the representation, and show how this bound may be tightened by considering equivalent representations. In the binary Boolean case, we prove that a degree 2 or treestructured constraint graph gives a quadratic bound on the number of improving moves made by any local search; hence, any landscape that can be represented by such a model will be tractable for any form of local search.
Finally, we build two families of examples to show that the conditions in our tractability results are essential. With domain size three, even just a path of binary constraints can model a landscape with an exponentially long sequence of improving moves. With a treewidth-two constraint graph, even with a maximum degree of three, binary Boolean constraints can model a landscape with an exponentially long sequence of improving moves.

Read the full article at: www.jair.org

The Emergence of Higher-Order Structure in Scientific and Technological Knowledge Networks

Thomas Gebhart, Russell J. Funk

The growth of science and technology is a recombinative process, wherein new discoveries and inventions are built from prior knowledge. Yet relatively little is known about the manner in which scientific and technological knowledge develop and coalesce into larger structures that enable or constrain future breakthroughs. Network science has recently emerged as a framework for measuring the structure and dynamics of knowledge. While helpful, existing approaches struggle to capture the global properties of the underlying networks, leading to conflicting observations about the nature of scientific and technological progress. We bridge this methodological gap using tools from algebraic topology to characterize the higher-order structure of knowledge networks in science and technology across scale. We observe rapid growth in the higher-order structure of knowledge in many scientific and technological fields. This growth is not observable using traditional network measures. We further demonstrate that the emergence of higher-order structure coincides with decline in lower-order structure, and has historically far outpaced the corresponding emergence of higher-order structure in scientific and technological collaboration networks. Up to a point, increases in higher-order structure are associated with better outcomes, as measured by the novelty and impact of papers and patents. However, the nature of science and technology produced under higher-order regimes also appears to be qualitatively different from that produced under lower-order ones, with the former exhibiting greater linguistic abstractness and greater tendencies for building upon prior streams of knowledge.

Read the full article at: arxiv.org

Information Length Analysis of Linear Autonomous Stochastic Processes

Adrian-Josue Guel-Cortez and Eun-jin Kim

Entropy 2020, 22(11), 1265;

When studying the behaviour of complex dynamical systems, a statistical formulation can provide useful insights. In particular, information geometry is a promising tool for this purpose. In this paper, we investigate the information length for n-dimensional linear autonomous stochastic processes, providing a basic theoretical framework that can be applied to a large set of problems in engineering and physics. A specific application is made to a harmonically bound particle system with the natural oscillation frequency ω, subject to a damping γ and a Gaussian white-noise. We explore how the information length depends on ω and γ, elucidating the role of critical damping γ=2ω in information geometry. Furthermore, in the long time limit, we show that the information length reflects the linear geometry associated with the Gaussian statistics in a linear stochastic process.

Read the full article at: www.mdpi.com