Connectivity (graph theory) | EPFL Graph Search

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. Connected vertices and graphs In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length 1, i.e. by a single edge, the vertices are called adjacent. A graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connecte

Target cell-type specificity of a cortico-amygdala long range synaptic connection

Ayah Khubieh

An important function of the brain is to analyze sensory information, and to modulate animal behaviour according to previous experience. During processes of emotional learning, sensory percepts with a reinforcing quality, also called unconditioned stimuli (US), influence the quality of innocuous sensory stimuli. A brain structure involved in the integration of innocuous and reinforcing sensory stimuli is the lateral amygdala (LA), an input station to further amygdalar circuits. Little is known about which upstream brain regions convey US-information to the LA; however, evidence indicates that the posterior insular cortex, which processes nociceptive somatosensory information, might be a candidate. The LA microcircuit is composed of principal neurons and inhibitory interneurons; the latter play a prominent role in the control of local activity and plasticity. To investigate how the posterior insular cortex might recruit LA neurons, we used optogenetically-assisted circuit mapping in combination with genetic identification of cell types with Cre-mouse lines. Specifically, a VGluT2-Cre mouse line, producing a marker for excitatory neurons, and VIP-Cre and SOM-Cre mice as markers for two classes of inhibitory interneurons, were used. We found that VGluT2-Cre+ neurons received strong excitatory and feedforward inhibitory inputs from the posterior insular cortex. The excitatory input was sufficient to induce action potential firing, hence engaging the local circuit. VIP-Cre+ interneurons were moderately excited by posterior insular cortex input, and received strong feedforward inhibition. Both VIP-Cre+ and SOM-Cre+ interneurons also received feedforward, polysynaptic excitation, likely the result of the activity of local principal neurons. Finally, SOM-Cre+ interneurons received moderate excitatory and feedforward inhibitory input from the posterior insular cortex, and their connectivity probability was high. This study supports the notion that the posterior insular cortex can convey US-information to the LA, with the potential to strongly activate LA principal neurons. However, it suggests that a disinhibition of LA principal neurons through VIP interneurons, which has been observed in previous studies, might be shaped by additional afferents, possibly including neuromodulatory inputs. Through systematic recordings of input connections to defined neuron types in the LA, this study provides an entry point to the understanding of the synaptic connectivity rules that govern the activation of amygdalar circuits by incoming long-range cortical inputs.

EPFL2021

Graph orientations with edge-connection and parity constraints

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge- connected graph with |V| + |E| even has a (k-1)-edge- connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k edge- disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.

2001

Exploring MEG brain fingerprints: Evaluation, pitfalls, and interpretations

Enrico Amico, Alessandra Griffa, Ekansh Sareen, Dimitri Nestor Alice Van De Ville, Sélima Zahar

Individual characterization of subjects based on their functional connectome (FC), termed “FC fingerprinting”, has become a highly sought-after goal in contemporary neuroscience research. Recent functional magnetic resonance imaging (fMRI) studies have demonstrated unique characterization and accurate identification of individuals as an accomplished task. However, FC fingerprinting in magnetoencephalography (MEG) data is still widely unexplored. Here, we study resting-state MEG data from the Human Connectome Project to assess the MEG FC fingerprinting and its relationship with several factors including amplitude- and phase-coupling functional connectivity measures, spatial leakage correction, frequency bands, and behavioral significance. To this end, we first employ two identification scoring methods, differential identifiability and success rate, to provide quantitative fingerprint scores for each FC measurement. Secondly, we explore the edgewise and nodal MEG fingerprinting patterns across the different frequency bands (delta, theta, alpha, beta, and gamma). Finally, we investigate the cross-modality fingerprinting patterns obtained from MEG and fMRI recordings from the same subjects. We assess the behavioral significance of FC across connectivity measures and imaging modalities using partial least square correlation analyses. Our results suggest that fingerprinting performance is heavily dependent on the functional connectivity measure, frequency band, identification scoring method, and spatial leakage correction. We report higher MEG fingerprinting performances in phase-coupling methods, central frequency bands (alpha and beta), and in the visual, frontoparietal, dorsal-attention, and default-mode networks. Furthermore, cross-modality comparisons reveal a certain degree of spatial concordance in fingerprinting patterns between the MEG and fMRI data, especially in the visual system. Finally, the multivariate correlation analyses show that MEG connectomes have strong behavioral significance, which however depends on the considered connectivity measure and temporal scale. This comprehensive, albeit preliminary investigation of MEG connectome test-retest identifiability offers a first characterization of MEG fingerprinting in relation to different methodological and electrophysiological factors and contributes to the understanding of fingerprinting cross-modal relationships. We hope that this first investigation will contribute to setting the grounds for MEG connectome identification.

2021