**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Connectivity (graph theory)

Summary

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

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (7)

Related publications (28)

Loading

Loading

Loading

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.

Related concepts (29)

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects corre

In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any tw

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.

2001Enrico 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.

2021Related lectures (20)

Related courses (11)

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization.
Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems.

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer science and in practice.

Related units (9)