Network Phenomena

Phase Transition

For a Random Graph Model with parameter $p(n)$, a threshold function, or critical value, for a property is a function $t(n)$ such that the property holds with a probability approaching 1 if $p(n)=\Omega (t(n))$, while approaching 0 if $p(n)=o(t(n))$. When such a threshold function exists, it is said that a phase transition occurs at that threshold.

Giant Component

In a Random Graph Model, a giant component is one whose size grows proportionally to the number of nodes. We usually denote the size of a component as the fraction of nodes it contains: $|C|/n\in (0,1]$.

A finer definition refers to a component with nodes fewer than $n^{2/3}/2$ as a small component, and one with nodes more than $n^{2/3}$ as a large component.

Small-World Effect

A small-world network has a small diameter and average path length compared to its number of nodes. Usually we look for a $O(\ln n)$ diameter.