Complex Networks: Lattices and Random Graphs

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Listen to an AI-generated conversation about this lesson
Download our mobile app to listen on the go
Get App

Questions and Answers

Which of the following network structures is characterized by high local clustering and long average path length?

  • Random network
  • Small-world network
  • Square lattice
  • Ring lattice (correct)

In a random network, most nodes have degrees that are significantly different from the average degree.

False (B)

What are the two principal formulations offered by the Erdős-Rényi (ER) model for generating random networks?

G(N, M) and G(N, p)

In the context of network degree distributions, the probability distribution of the number of links each node has is known as the ______.

<p>degree distribution</p>
Signup and view all the answers

Match the average path lengths and clustering coefficients with the corresponding network type:

<p>Regular Lattice = Long average path length, High clustering coefficient Random Network = Short average path length, Low clustering coefficient Small-World Network = Short average path length, High clustering coefficient</p>
Signup and view all the answers

What is the primary purpose of the rewiring step in the Watts-Strogatz small-world network algorithm?

<p>To introduce randomness and create shortcuts in the network (B)</p>
Signup and view all the answers

A small-world network with a rewiring probability p = 1 is essentially the same as a regular lattice.

<p>False (B)</p>
Signup and view all the answers

What aspect of the Watts-Strogatz model makes it suitable for modeling various systems, such as social ties and neural networks?

<p>It interpolates between extremes of ordered lattices and random graphs</p>
Signup and view all the answers

In the Watts-Strogatz model, as the rewiring probability p increases from 0 to 1, the network transitions from a regular lattice to a ______.

<p>random network</p>
Signup and view all the answers

Match the following p-values to the corresponding network structural feature in Watts-Strogatz model:

<p>p=0 = High clustering, long path lengths p=1 = Low clustering, short path lengths</p>
Signup and view all the answers

Which type of contagion requires exposure from multiple infected neighbors before an individual adopts the behavior?

<p>Complex Contagion (A)</p>
Signup and view all the answers

In a small-world network, higher rewiring probability (p) results in a network that is more clustered and has longer path lengths.

<p>False (B)</p>
Signup and view all the answers

What is the primary factor that controls the extent to which a small-world network is locally clustered versus globally connected?

<p>Rewiring probability p</p>
Signup and view all the answers

In the context of contagion dynamics, parts of a network that are weakly connected and lack sufficient overlap of infected neighbors to support the spread are referred to as ______.

<p>structural gaps</p>
Signup and view all the answers

Match the following contagion with the corresponding method of propagation:

<p>Simple contagion = A susceptible agent becomes infected with a given probability upon contact with a single infected neighbor. Complex contagion = An agent becomes infected only if a threshold number of its neighbors are already infected.</p>
Signup and view all the answers

Which of the following is a limitation of the small-world network model?

<p>It is not a generative model of network growth. (B)</p>
Signup and view all the answers

Simple contagions spread more effectively on regular lattices compared to small-world networks.

<p>False (B)</p>
Signup and view all the answers

What is the key difference in how complex contagions spread compared to simple contagions when the network is rewired (increasing p)?

<p>Rewiring can hinder the spread of complex contagions</p>
Signup and view all the answers

Networks that are statistically ______ have nodes that are close to the average degree.

<p>homogeneous</p>
Signup and view all the answers

Match the Contagion type to the expected Outcome on a Small-World Network with an increasing probability p (from Watts-Strogatz):

<p>Simple Contagion = Spreads more quickly as p increases, reaching distant parts of the network faster due to added shortcuts. Complex Contagion = Spread may be hindered as p increases, because successful transmission requires more redundant exposures, which are less likely with a purely random topology.</p>
Signup and view all the answers

Flashcards

Regular Networks

Networks where each node connects to a fixed, predictable set of neighbors. Examples are ring and square lattices.

Ring Lattice

Nodes arranged in a circle, each connected to its k nearest neighbors, which creates high local clustering but longer average path lengths.

Square Lattice

Nodes arranged in a two-dimensional grid, typically connected to adjacent neighbors, exhibiting strong locality and clustering.

Random Networks

A foundational network model where links form randomly between node pairs with a fixed probability, leading to statistically homogeneous networks.

Signup and view all the flashcards

The Erdős-Rényi (ER) Model

Offers two ways to generate random networks: fixed links or connection probability.

Signup and view all the flashcards

Degree Distribution

The probability distribution of the number of links each node has in a network.

Signup and view all the flashcards

Binomial Degree Distribution

Probability of k links forming out of N-1 possible connections in a random network.

Signup and view all the flashcards

Poisson Distribution

An approximate degree distribution for sparse, large random networks, depending only on the average degree.

Signup and view all the flashcards

Small-World Networks

Networks that combine high clustering (like lattices) and short average path lengths (like random networks).

Signup and view all the flashcards

Parameter p

A rewiring probability that determines the structure of a network, ranging from a regular lattice (p=0) to a random network (p=1).

Signup and view all the flashcards

Regular Networks

Networks emphasize locality and repeated interactions.

Signup and view all the flashcards

Small-world Networks

Networks capture both clustering of local ties and reachability of distant others.

Signup and view all the flashcards

Simple Contagion

A single exposure to a neighbor is enough to be 'infected'.

Signup and view all the flashcards

Complex Contagion

Adoption requires exposure from multiple neighbors.

Signup and view all the flashcards

Structural Gaps

Parts of the network that are weakly connected.

Signup and view all the flashcards

Study Notes

  • Summary of complex networks
  • Introduction to structural models that capture distinct patterns of connectivity
  • Network architecture impacts information, behaviors, and resource flow
  • Covers ring and square lattices, random graphs, and small-world networks

Regular Lattices/Networks

  • Regular networks where each node connects to a fixed, predictable set of neighbors
  • Ring Lattices:
  • Nodes are in a circle
  • Each node connects to k nearest neighbors
  • Have high local clustering
  • Have long average path length
  • Model small, localized communities with fixed social circles
  • Square Lattices:
  • Nodes in a two-dimensional grid
  • Each node connects to adjacent neighbors (4 or 8 nearest)
  • Exhibits strong locality and clustering
  • Used in spatial models simulating urban interactions

Random Networks

  • Foundational model made by linking node pairs with probability p
  • Are statistically homogeneous
  • Nodes have degrees close to the average
  • Few high-degree nodes present

Characteristics of Random Networks

  • Short average path lengths allowing most nodes to be reached quickly
  • Low clustering coefficients due to random link formation
  • They do not reflect real-world social networks features
  • Provide a baseline for comparison, allowing researchers to isolate effects

The Erdős-Rényi (ER) Model

  • Model named after Paul Erdős and Alfréd Rényi
  • Offers two formulations for random networks
  • G(N, M) Model
  • Input: N nodes and M links
  • Randomly connect pairs until M links exist
  • Maintains a fixed total link count, avoiding duplicate links
  • G(N, p) Model:
  • Input: N nodes and connection probability p
  • For each possible node pair, add a link with probability p
  • Computationally efficient with PN(N-1)/2 expected links
  • Each instantiation produces a different realization

Degree Distributions in Random Networks

  • Degree distribution is key to a network
  • It determines the probability of the number of links each node has
  • In the G(N, p) model, distributions determine structural properties/dynamic behavior
  • Link formations are independent and have a fixed probability
  • Node degree is seen as a random variable
  • Understanding the degree variable helps characterize overall network connectivity

Binomial Degree Distribution

  • Degree k of a node follows a binomial distribution: P(k) = (N-1 choose k) * p^k * (1-p)^(N-1-k)
  • Reflects the probability that k links are formed from N-1 possible connections

Key Properties of Binomial Degree Distribution

  • Mean degree: = p(N – 1)
  • Mode: Approximately at k =
  • Standard deviation: σk = √p(1 − p)(N − 1)

Moments of the Binomial Distribution

  • = p(N-1)
  • <k^2> = p(1-p)(N − 1) + p^2(N − 1)^2
  • σk = √(k^2) – (k)^2 = √p(1 − p)(N − 1)
  • As p increases, the mean and variance increase, resulting in a broader distribution.

Poisson Limit

  • For large N and small p, where average degree = p(N-1) remains constant, the binomial distribution converges to a Poisson distribution: P(k) = (e^(-) * ^k) / k!

Key properties of the Poisson Limit

  • Mean:
  • Mode: Approx. at
  • Standard deviation: σk = √

Moments of the Poisson Distribution

  • =
  • <k^2> = (1 + )
  • σk = √
  • The poisson form is analytically convenient and only depends on
  • Networks of different sizes but the same average degree have degree distributions

Comparison of Binomial and Poisson Distributions

  • Binomial distribution: Exact degree distribution for finite random networks
  • Poisson distribution: Approximate distribution valid for sparse, large networks
  • Both distributions peak near the mean degree and broaden with increasing

Small-World Networks

  • Bridge the gap between regular lattices and random networks
  • Defined by both local regularity and global reach
  • Have high clustering (like lattices) and short average path lengths

Watts-Strogatz Small-World Network Algorithm

  • Generates small-world networks from a regular lattice
  • Initialization:
  • Construct a regular ring lattice with N nodes
  • Each node connects to k nearest neighbors (k/2 on each side)
  • Rewiring Step:
  • For each link connecting a node to a neighbor, and with probability p:
  • Remove the link and reconnect the node to a randomly chosen node
  • With probability 1 – p:
  • Leave the link unchanged
  • Repeat the process for each node and neighbors at increasing distances

Parameter p: From Lattice to Randomness

  • Rewiring probability p determines network structure
  • p = 0: Network remains a regular lattice (high clustering, long path lengths)
  • p = 1: Network becomes a random network (low clustering, short path lengths)
  • 0 < p < 1: A small-world network emerges, with significant clustering and drastically reduced path lengths
  • They interpolate between ordered lattices and random graphs
  • They are suitable for modeling social ties, neural networks, and many other systems
  • Construction begins with a ring lattice, after which a small proportion of the links are randomly rewired to create shortcuts
  • The effect: Individuals are often just a few steps away from anyone else in the network- popularized by the phrase "six degrees of separation."
  • These networks are suited to modeling systems with local clustering coexisting with global connectivity
  • Examples of which include online social networks, professional collaborations, and rumor spreading

Contagion on Small-World Networks

  • Help simulate how behaviors and info spread in social structures
  • It explores contagion dynamics within networks exhibiting local clustering and long-range connectivity

Types of Contagion

  • Simple:
  • A single exposure to an "infected" neighbor is sufficient to adopt a behavior or become infected
  • Common in biological disease transmission and the spread of easily accepted information
  • Complex:
  • Adoption requires exposure from multiple infected neighbors
  • More appropriate for risky, unfamiliar, or socially contested behaviors
  • Needs reinforcement from multiple peers before adoption

Network Structure and Contagion Dynamics

  • Network structure influences how contagion spreads
  • Rewiring probability p controls local clustering vs. global connectivity
  • Low p: Resembles a regular lattice-highly clustered with long path lengths
  • High p: More random-less clustered with short path lengths
  • Intermediate p: Preserving clustering while introducing shortcuts

Contagion Outcomes on Small-World Networks

  • Simple contagions spread quickly, with shortcuts allowing infections to reach distant parts rapidly
  • Complex contagions: Rewiring the network hinders that spread
  • Redundant exposures are more likely in clustered neighborhoods

Structural Gaps and Contagion Failure

  • Complex contagions often fail to propagate across the entire network
  • Due to "structural gaps": Parts of the network are weakly connected
  • Findings underscore clustering and reinforcement in diffusion

Modeling Complex Contagion in Agent-Based Models

  • Each node is an agent with a state (S or I). Contagion spreads via social ties
  • Simple contagion:
  • A susceptible agent becomes infected with probability
  • Upon contact with a single infected neighbor
  • Complex contagion:
  • An agent becomes infected only if a threshold number of neighbors are infected
  • Small numbers of connected agents are set to the infected state
  • Then infected agents try to transmit the contagion to their susceptible neighbors
  • Model proceeds until no further infections occur
  • Highlights the importance of interventions effective for simple contagions
  • Seeding information

Limitations of the Small-World Model

  • Produces networks with narrow degree distributions which are unlike networks with heavy-tailed distributions that has connected hubs
  • It is not a generative model of network growth
  • Network size and structure must be predefined and it does not explain how the network emerged

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Complex Networks: Notes 2 PDF

More Like This

Use Quizgecko on...
Browser
Browser