Category: Papers

Arithmetic success and gender-based characterization of brain connectivity across EEG bands

Sait Demir, İlker Türker

Biomedical Signal Processing and Control
Volume 64, February 2021, 102222

• Functional brain networks employing coherence method is conducted in a comparative manner across EEG bands.

• Female brain is more connected under rest condition, while male brain boosts connectivity under arithmetic workload.

• Unsuccessful brains yield more assortative behavior based on beta band networks.

• Arithmetically successful brains yield greater connectivity under rest condition for most EEG bands.

• Theta band better diagnoses gender-based differences, while gamma band better discriminates success-based connectivity.

Read the full article at: www.sciencedirect.com

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