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
Giant component
Summary
In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices.
More precisely, in graphs drawn randomly from a probability distribution over arbitrarily large graphs, a giant component is a connected component whose fraction of the overall number of vertices is bounded away from zero. In sufficiently dense graphs distributed according to the Erdős–Rényi model, a giant component exists with high probability.
Giant components are a prominent feature of the Erdős–Rényi model (ER) of random graphs, in which each possible edge connecting pairs of a given set of n vertices is present, independently of the other edges, with probability p. In this model, if for any constant , then with high probability (in the limit as goes to infinity) all connected components of the graph have size O(log n), and there is no giant component. However, for there is with high probability a single giant component, with all other components having size O(log n). For , intermediate between these two possibilities, the number of vertices in the largest component of the graph, is with high probability proportional to .
Giant component is also important in percolation theory. When a fraction of nodes, , is removed randomly from an ER network of degree , there exists a critical threshold, . Above there exists a giant component (largest cluster) of size, . fulfills, . For the solution of this equation is , i.e., there is no giant component.
At , the distribution of cluster sizes behaves as a power law, ~ which is a feature of phase transition.
Alternatively, if one adds randomly selected edges one at a time, starting with an empty graph, then it is not until approximately edges have been added that the graph contains a large component, and soon after that the component becomes giant. More precisely, when t edges have been added, for values of t close to but larger than , the size of the giant component is approximately .
Official source
About this result
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 concepts (8)
Network science
Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology.
Giant component
In network theory, a giant component is a connected component of a given random graph that contains a significant fraction of the entire graph's vertices. More precisely, in graphs drawn randomly from a probability distribution over arbitrarily large graphs, a giant component is a connected component whose fraction of the overall number of vertices is bounded away from zero. In sufficiently dense graphs distributed according to the Erdős–Rényi model, a giant component exists with high probability.
Percolation
In physics, chemistry, and materials science, percolation () refers to the movement and filtering of fluids through porous materials. It is described by Darcy's law. Broader applications have since been developed that cover connectivity of many systems modeled as lattices or graphs, analogous to connectivity of lattice components in the filtration problem that modulates capacity for percolation.
Related courses (3)
COM-512: Networks out of control
The goal of this class is to acquire mathematical tools and engineering insight about networks whose structure is random, as well as learning and control techniques applicable to such network data.
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
PHYS-231: Data analysis for Physics
Ce cours présentera les bases de l'analyse des données et de l'apprentissage à partir des données, l'estimation des erreurs et la stochasticité en physique. Les concepts seront introduits théoriquemen