Evolving Information Networks

The graph is an explicit modelling choice

Vertices can represent people, documents or devices; edges can represent friendship, citation or communication. Preserve direction, weight and time when they are meaningful. A follower relation is not interchangeable with mutual friendship, and a message count is not a direct measurement of trust. Define the sampling boundary: a network of observed users omits unobserved people and ties. Many apparent structural patterns can change when the measurement process changes.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Degree, paths and clustering measure different features

Degree counts incident edges, shortest paths describe reachability and clustering measures local closure among neighbours. In an undirected simple graph, the sum of degrees is twice the number of edges because each edge contributes to two endpoints. A vertex can have modest degree yet connect otherwise separate groups. Consequently, popularity, brokerage and influence should not be treated as synonyms. Choose a measure according to the question rather than ranking every node with one universal score.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Random graphs are baselines, not universal explanations

An independent-edge random graph provides a simple baseline in which each potential edge appears with a fixed probability. Its expected degree follows from the number of possible neighbours. Real networks often have clustering or degree heterogeneity absent from that model. A configuration-style baseline preserves more degree information and can support a different comparison. Rejecting one null model does not identify the true generating mechanism; several processes may produce similar observed statistics.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Growth and preferential attachment

A growth model can add vertices and connect them with probabilities influenced by existing degree, producing cumulative advantage. This offers one possible explanation for highly uneven connectivity. A straight-looking line on a log-log plot is not sufficient evidence of a power law, and a heavy-tailed distribution does not prove preferential attachment caused it. Fit competing models, examine finite-size effects and account for measurement cutoffs before making a generative claim.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Cascades, thresholds and correlation

A cascade model describes how local state changes trigger others. In a threshold model, a node adopts after enough neighbours adopt; in a probabilistic contagion model, exposures may succeed randomly. Network structure affects whether a change remains local or spreads widely. Observed similarity among connected users can also arise from homophily or shared external events. Distinguish causal influence from correlation, especially when using observational interaction logs to evaluate a proposed diffusion mechanism.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Search and incentives reshape the network

Link-ranking and search algorithms direct attention, which can change which content receives future links. Mechanisms that reward contributions also affect participant behaviour, including strategic or automated behaviour. A ranking objective such as engagement can create feedback loops not captured by a static graph analysis. Evaluate interventions over time and include the actors' incentives. A centrality increase after a platform change may reflect the platform's exposure policy rather than improved intrinsic content quality.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Worked degree and temporal evaluation

For an undirected graph with degrees 3, 2, 2, 1 and 0, the degree sum is 8, so the graph has four edges. The zero-degree vertex is isolated and must not be silently dropped when reporting average degree, which is 8/5 = 1.6. For link prediction, train on edges observed before a cutoff and test on later edges. Randomly splitting a complete historical graph can reveal future topology and overstate predictive performance.

References: Carleton 4206 official calendar record · Albert-László Barabási: Network Science, author-maintained open textbook

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton 4206 official calendar record ↗Course scope · 2026–27
• Albert-László Barabási: Network Science, author-maintained open textbook ↗Supplementary primary reference