Lecture

Scale-Free Networks: Power Laws and Preferential Attachment

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.

Description

This lecture covers the concepts of scale-free networks, power laws, and preferential attachment. It explains the Pareto Law, degree distributions, the Barabasi-Albert Model, and the Simon model. The lecture delves into the implementation of the Preferential Attachment rule, different versions of the Barabasi-Albert Model, and the expected node degree. It also discusses alternative approximations using Continuum Theory, assortativity in networks, and the size of the Giant component. The lecture concludes with a critique of scale-free networks and a comparison between Power Law and Lognormal distributions.

Official source

Ontological neighbourhood

Statistics

Statistical inference: Mathematical statistics

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Scale-free network

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as where is a parameter whose value is typically in the range (wherein the second moment (scale parameter) of is infinite but the first moment is finite), although occasionally it may lie outside these bounds. The name "scale-free" means that some moments of the degree distribution are not defined, so that the network does not have a characteristic scale or "size".

Power law

In statistics, a power law is a functional relationship between two quantities, where a relative change in one quantity results in a relative change in the other quantity proportional to a power of the change, independent of the initial size of those quantities: one quantity varies as a power of another. For instance, considering the area of a square in terms of the length of its side, if the length is doubled, the area is multiplied by a factor of four.

Log-normal distribution

In probability theory, a log-normal (or lognormal) distribution is a continuous probability distribution of a random variable whose logarithm is normally distributed. Thus, if the random variable X is log-normally distributed, then Y = ln(X) has a normal distribution. Equivalently, if Y has a normal distribution, then the exponential function of Y, X = exp(Y), has a log-normal distribution. A random variable which is log-normally distributed takes only positive real values.

Chi-squared distribution

In probability theory and statistics, the chi-squared distribution (also chi-square or -distribution) with degrees of freedom is the distribution of a sum of the squares of independent standard normal random variables. The chi-squared distribution is a special case of the gamma distribution and is one of the most widely used probability distributions in inferential statistics, notably in hypothesis testing and in construction of confidence intervals.

Cauchy distribution

The Cauchy distribution, named after Augustin Cauchy, is a continuous probability distribution. It is also known, especially among physicists, as the Lorentz distribution (after Hendrik Lorentz), Cauchy–Lorentz distribution, Lorentz(ian) function, or Breit–Wigner distribution. The Cauchy distribution is the distribution of the x-intercept of a ray issuing from with a uniformly distributed angle. It is also the distribution of the ratio of two independent normally distributed random variables with mean zero.

Related lectures (64)

Statistical analysis of network data

Covers stochastic properties, network structures, models, statistics, centrality measures, and sampling methods in network data analysis.

Handling Networks: Graph Theory

Covers the fundamentals of handling networks and centrality measures in graph theory.

Social and Information Networks: Structure

Explores the structure of social and information networks, focusing on giant components, clustering, tie formation, and network 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.

Model Specification: The Error Term MOOC: Introduction to Discrete Choice Models