Concept

Random graph

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph. A random graph is obtained by starting with a set of n isolated vertices and adding successive edges between them at random. The aim of the study in this field is to determine at what stage a particular property of the graph is likely to arise. Different random graph models produce different probability distributions on graphs. Most commonly studied is the one proposed by Edgar Gilbert, denoted G(n,p), in which every possible edge occurs independently with probability 0 < p < 1. The probability of obtaining any one particular random graph with m edges is with the notation . A closely related model, the Erdős–Rényi model denoted G(n,M), assigns equal probability to all graphs with exactly M edges. With 0 ≤ M ≤ N, G(n,M) has elements and every element occurs with probability . The latter model can be viewed as a snapshot at a particular time (M) of the random graph process , which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly from the set of missing edges. If instead we start with an infinite set of vertices, and again let every possible edge occur independently with probability 0 < p < 1, then we get an object G called an infinite random graph.

Official source

https://en.wikipedia.org/wiki/Random_graph

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 courses (14)

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the data science world (pandas, scikit-learn, Spark, etc.) ...

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised. ...

NX-421: Neural signals and signal processing

Understanding, processing, and analysis of signals and images obtained from the central and peripheral nervous system ...

Related lectures (32)

Statistical Physics of Clusters

Explores the statistical physics of clusters, focusing on complexity and equilibrium behavior.

Phase Transitions: Connectivity in Random Graphs

Delves into phase transitions in random graphs, emphasizing the emergence of a giant component with varying connectivity.

Node Degree and Strength

Explores node degree and strength in network neuroscience, discussing random vs real networks and the challenges of fitting power laws to real data.

Related publications (28)

Recovering Communities in Structured Random Graphs

The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random graph in which edges crossing between different communities appear with smaller probability than edges induced by communities. The communities themselves form a collection of vertex-disjoint sparse cuts in the expected graph, and can be recovered, often exactly, from a sample as long as a separation condition on the intra- and int

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2026

Finding Planted Cycles in a Random Graph

In this paper, we study the problem of finding a collection of planted cycles in an Erdös‐Rényi random graph , in analogy to the famous Planted Clique Problem. When the cycles are planted on a uniformly random subset of vertices, we show that almost‐exact recovery (i.e., recovering all but a vanishing fraction of planted‐cycle edges as ) is information‐theoretically possible if and impossible if . Moreover, despite the worst‐case computational hardness of finding long cycles, we design a polynomial‐time alg

Wiley2026

RAPID-Graph: Recursive All-Pairs Shortest Paths Using Processing-in-Memory for Dynamic Programming on Graphs

All-pairs shortest paths (APSP) remains a major bottleneck for large-scale graph analytics, as data movement with cubic complexity overwhelms the bandwidth of conventional memory hierarchies. We propose RAPID-Graph, a processing-in-memory (PIM) system co-designed across algorithm, architecture, and device levels to address this challenge. At the algorithm level, we introduce a recursion-aware partitioner that enables an exact APSP computation by decomposing graphs into vertex tiles to reduce data dependency

Institute of Electrical and Electronics Engineers Inc.2026

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Official source

https://en.wikipedia.org/wiki/Random_graph

About this result

Related courses (14)

CS-401: Applied data analysis

PHYS-467: Machine learning for physicists

NX-421: Neural signals and signal processing

Understanding, processing, and analysis of signals and images obtained from the central and peripheral nervous system ...

Related lectures (32)

Statistical Physics of Clusters

Explores the statistical physics of clusters, focusing on complexity and equilibrium behavior.

Phase Transitions: Connectivity in Random Graphs

Delves into phase transitions in random graphs, emphasizing the emergence of a giant component with varying connectivity.

Node Degree and Strength

Explores node degree and strength in network neuroscience, discussing random vs real networks and the challenges of fitting power laws to real data.

Related publications (28)

Recovering Communities in Structured Random Graphs

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2026

Finding Planted Cycles in a Random Graph

Wiley2026

RAPID-Graph: Recursive All-Pairs Shortest Paths Using Processing-in-Memory for Dynamic Programming on Graphs

Institute of Electrical and Electronics Engineers Inc.2026

Related people (32)

Patrick Thiran

Patrick Thiran is a full professor in network and systems theory at the School of Computer and Communication Sciences at EPFL. He holds an electrical engineering degree from the Université Catholique de Louvain, Louvain-la-Neuve, Belgium, an M.Sc. degree in electrical engineering from the University of California at Berkeley, USA, and he received the PhD degree from EPFL, in 1996. He became an adjunct professor in 1998, an assistant professor in 2002, an associate professor in 2006 and a full professor in 2011. He was with Sprint Advanced Technology Labs in Burlingame, California, in 2000-01. His research interests are in communication and social networks, performance analysis and stochastic models. He is currently active in the analysis and design of wireless and PLC networks (scaling laws, medium access control), in network monitoring (network tomography, multi-layer networks), and data-driven network science. He also contributed to network calculus and to the theory of locally coupled neural networks and self-organizing maps. He served as an associate editor for the IEEE Transactions on Circuits and Systems in 1997-99 and for the IEEE/ACM Transactions on Networking in 2006-10. He is currently on the editorial board of the IEEE Journal on Selected Areas in Communication. He is/was on the program committee of different conferences in networking, including ACM Sigcomm, Sigmetrics, IMC, CoNext and IEEE Infocom. He was TPC chair of AMC IMC 2011 and CoNext 2012. He is a Fellow of the Belgian American Educational Foundation and of the IEEE. He received the 1996 EPFL Doctoral Prize and the 2008 Crédit Suisse Teaching Award.

Sofia Charlotta Olhede

I am a professor of Statistics at EPFL. I did my PhD in Mathematics at Imperial College London, and graduated in 2003. I was an assistant professor (lecturer) at Imperial College London 2002-2006, and an associate professor (senior lecturer) 2006-2007. In 2007 I moved to University College London and became a full professor. I moved to EPFL in 2019, and in 2018 I became an Institute of Mathematical Statistics Fellow with citation “For seminal contributions to the theory and application of large and heteroge

Wulfram Gerstner

Wulfram Gerstner is Director of the Laboratory of Computational Neuroscience LCN at the EPFL. His research in computational neuroscience concentrates on models of spiking neurons and spike-timing dependent plasticity, on the problem of neuronal coding in single neurons and populations, as well as on the link between biologically plausible learning rules and behavioral manifestations of learning. He teaches courses for Physicists, Computer Scientists, Mathematicians, and Life Scientists at the EPFL. After studies of Physics in Tübingen and at the Ludwig-Maximilians-University Munich (Master 1989), Wulfram Gerstner spent a year as a visiting researcher in Berkeley. He received his PhD in theoretical physics from the Technical University Munich in 1993 with a thesis on associative memory and dynamics in networks of spiking neurons. After short postdoctoral stays at Brandeis University and the Technical University of Munich, he joined the EPFL in 1996 as assistant professor. Promoted to Associate Professor with tenure in February 2001, he is since August 2006 a full professor with double appointment in the School of Computer and Communication Sciences and the School of Life Sciences. Wulfram Gerstner has been invited speaker at numerous international conferences and workshops. He has served on the editorial board of the Journal of Neuroscience, Network: Computation in Neural Systems', Journal of Computational Neuroscience', and `Science'.

Thomas Mountford

Teaching & PhD Past EPFL PhD Students Damien Gauthier, Samir Brahim Belhaouari, Driss Baraka, Daniel Rodrigues Valesin, Samuel Schöpfer, Kamran Kalbasi, Jacques Saliba, Hao Xue, Keming Chen Past EPFL PhD Students as codirector Guillaume Charles Woessner Courses Analysis I MATH-101(d) Study the fundamental concepts of analysis, and the differential and integral calculus of real-valued functions of one real variable. Markov chains MATH-332 The course follows the text of Norris

Younes Pierre Zine

Expertise I mainly work on (deterministic and random) nonlinear PDEs by using techniques and insights from PDE theory, probability theory and Fourier analysis.My website:https://younes-zine.github.io Expertise I mainly work on (deterministic and random) nonlinear PDEs by using techniques and insights from PDE theory, probability theory and Fourier analysis.My website:https://younes-zine.github.io Education Ph.D. | 2020 – 2023 The University of Edinburgh

Pierre Vandergheynst

Pierre Vandergheynst received the M.S. degree in physics and the Ph.D. degree in mathematical physics from the Université catholique de Louvain, Louvain-la-Neuve, Belgium, in 1995 and 1998, respectively. From 1998 to 2001, he was a Postdoctoral Researcher with the Signal Processing Laboratory, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He was Assistant Professor at EPFL (2002-2007), where he is now a Full Professor of Electrical Engineering and, by courtesy, of Computer and Communication Sciences. As of 2015, Prof. Vandergheynst serves as EPFL’s Vice-Provost for Education. His research focuses on harmonic analysis, sparse approximations and mathematical data processing in general with applications covering signal, image and high dimensional data processing, computer vision, machine learning, data science and graph-based data processing. He was co-Editor-in-Chief of Signal Processing (2002-2006), Associate Editor of the IEEE Transactions on Signal Processing (2007-2011), the flagship journal of the signal processing community and currently serves as Associate Editor of Computer Vision and Image Understanding and SIAM Imaging Sciences. He has been on the Technical Committee of various conferences, serves on the steering committee of the SPARS workshop and was co-General Chairman of the EUSIPCO 2008 conference. Pierre Vandergheynst is the author or co-author of more than 70 journal papers, one monograph and several book chapters. He has received two IEEE best paper awards. Professor Vandergheynst is a laureate of the Apple 2007 ARTS award and of the 2009-2010 De Boelpaepe prize of the Royal Academy of Sciences of Belgium.

Olivier Lévêque

Olivier Lévêque was born in Switzerland in 1971. He received the physics diploma from EPFL in 1995 and completed his PhD in mathematics at EPFL in 2001. Since then, he has been with the Laboratory of Information Theory at EPFL. He spent the academical year 2005-2006 at the Electrical Engineering Department of Stanford University, where he was appointed as lecturer. His research interests include stochastic analysis, random matrices, wireless communications and information theory.

Emmanuel Abbé

Teaching & PhD PhD Students Denys Pushkin, Ortal Yona Senouf, Vladyslav Shashkov Past EPFL PhD Students Elisabetta Cornacchia, Aryo Lotfi Courses Reasoning in artificial intelligence MATH-700 Large language models have raised the potential of artificial intelligence in various applications, including science and mathematics, but their reasoning capabilities remain under investigations. This class focuses on defining, measuring and improving the reasoning capabilities of such AI models. Awa

Michael Christoph Gastpar

Michael Gastpar is a (full) Professor at EPFL. From 2003 to 2011, he was a professor at the University of California at Berkeley, earning his tenure in 2008. He received his Dipl. El.-Ing. degree from ETH Zürich, Switzerland, in 1997 and his MS degree from the University of Illinois at Urbana-Champaign, IL, USA, in 1999. He defended his doctoral thesis at EPFL on Santa Claus day, 2002. He was also a (full) Professor at Delft University of Technology, The Netherlands. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He is a Fellow of the IEEE. He is the co-recipient of the 2013 Communications Society & Information Theory Society Joint Paper Award. He was an Information Theory Society Distinguished Lecturer (2009-2011). He won an ERC Starting Grant in 2010, an Okawa Foundation Research Grant in 2008, an NSF CAREER award in 2004, and the 2002 EPFL Best Thesis Award. He has served as an Associate Editor for Shannon Theory for the IEEE Transactions on Information Theory (2008-11), and as Technical Program Committee Co-Chair for the 2010 International Symposium on Information Theory, Austin, TX.

Paolo De Los Rios

Paolo De Los Rios earned his master in Electronic Engineering at the Turin Institute of Technology (Politecnico di Torino) in May 1993. In November 1993 he moved to Trieste, Italy, to enter the PhD program in Theoretical Condensed Matter Theory at the International School for Advanced Studies (SISSA/ISAS) where he obtained the PhD degree in October 1996 for his work on the statistical physics of disordered systems. After a one year postdoc at the Max-Planck Institute for the Physics of Complex Systems in Dresden, Germany, in November 1997 he moved to the University of Fribourg, Switzerland, to join the group of Prof. Yi-Cheng Zhang. There he has worked on various applications of statistical physics to complex systems. In September 2000 he has been appointed Assistant Professor in Statistical Physics of Living Matter and Complex Systems at the Institute of Theoretical Physics of the University of Lausanne, Switzerland. Since April 2010 he is Associate Professor at the Institute of Theoretical Physics of the Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland.

Related units (16)

Signal Processing Laboratory 2

Adaptive Systems Laboratory

Signal Processing Laboratory 4

Related concepts (11)

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.

Complex network

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research (since 2000) inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.

Percolation theory

In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles Network theory and Percolation (cognitive psychology).

Related notebooks (4)

Basic Example of Anderson Localization in a 1D System

Demonstration of Anderson localization[1]¶ This notebook is intended to show a very basic example of the Anderson localization in one-dimensional system. In [1]: import numpy as np from numpy import linalg as LA import matplotlib.pyplot as plt

from future import print_function

from ipywidgets import interact, interactive, fixed, interact_manual import ipywidgets as widgets %matplotlib inline To show the idea of Anderson localization, we can consider 1D chain of

N

atoms with perio

Classical Monte Carlo Simulations of the Ising Model on Square Lattice

"## Classical Monte-Carlo simulations of the Ising model on square lattice\n", "\n", "The Ising model considers the following Hamiltonian\n", "\n", "

\\hat{\\mathcal{H}} = -J\\displaystyle\\sum_{}\\sigma_i \\sigma_j

,\n", "\n", "in which spins

\\sigma_i

can take only two discrete values

\\sigma_i \\in \\{-1,+1\\}

. Below, we will consider spins on two-dimensional square lattice taking into account couplings

J

only for the nearest neighbor sites. For

J > 0

the ferromagneti

Adaptive Echo Cancellation using LMS Filter

Adaptive Echo Cancellation[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will use the adaptive LMS filter to estimate the impulse response of a reverberating room. A typical use case is handsfree telephony: since the received signal, amplified and played by the speaker, is picked up by the microphone, we need to eliminate it from the signal that is transmitted back in order to avoid a feedback loop. The signal picked up by the microph

Building a Dual-Tone Multi-Frequency (DTMF) Decoder using Short-Time Fourier Transform

Dual-tone multi-frequency (DTMF) signaling[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will build a dual-tone multi-frequency decoder based on the short-time Fourier transform. In [1]:

first our usual bookkeeping

%matplotlib inline import matplotlib import matplotlib.pyplot as plt import numpy as np import IPython In [2]: plt.rcParams["figure.figsize"] = (14,4)

Introduction[4]¶ DTMF signaling is the way analog phones send the n