Network Taxonomy

Four Categories of Real-World Networks

The MLRD course identifies four distinct types of networks, each with structural properties that arise from their generative mechanisms. When asked to evaluate whether a given graph is “realistic”, use these properties.

1. Social Networks

Examples: Facebook friend graph, Twitter follow graph, professional networks, collaboration networks.

Properties:

• Undirected (friendship is mutual; though follower graphs are directed, the exam treats social networks as primarily undirected at the friendship level).
• High triadic closure: if A knows B and B knows C, A is highly likely to know C. This produces high local clustering coefficients: $C_i$ values near 1 are common.
• Structure: dense cliques of strong ties linked by weaker bridging ties (Granovetter’s weak ties). Edge betweenness is high on these bridging edges.
• Generative principle: triadic closure and homophily (people connect to similar others).

2. Information / Knowledge Networks

Examples: the World Wide Web (pages linked by hyperlinks), citation networks (paper A cites paper B), Wikipedia link graphs.

Properties:

• Directed (links are one-way; page A links to page B does not imply B links to A).
• Bow-tie structure: a large strongly connected core (SCC), pages that link into the core (IN), pages linked from the core (OUT), and tendrils/tubes that connect in one direction only.
• Massive in-degree disparities: a few pages (Google, Wikipedia, major news sites) receive millions of incoming links; the vast majority receive none. Degree distribution follows a power law with $\alpha \approx 2.1$ for the Web.
• Few constraints on who links to whom — no physical proximity required.

3. Technological Networks

Examples: Internet router network (physical cables between routers), power grids, road networks, rail networks, pipeline networks.

Properties:

• Constrained by physical geography and cost: a router can only connect to nearby routers via physical cables. Edges have real-world length.
• Maximum degree is capped: each node can physically accommodate only so many connections (ports, cables, pipes). This prevents the emergence of extreme hubs.
• Vulnerable to targeted hub attack: although hubs are less extreme than in information networks, removing key interconnection points fragments the network. Major Internet exchange points or power substations are critical bottlenecks.
• Structure reflects engineering design: often hierarchical (core, distribution, access layers) rather than organic.

4. Biological Networks

Examples: protein–protein interaction networks, gene regulatory networks, neural connectomes, metabolic networks, food webs.

Properties:

• May be directed or undirected depending on the system; edges represent physical or functional relationships.
• Highly modular: functional subunits (protein complexes, neural circuits, metabolic pathways) form dense subgraphs with sparse connections between modules.
• Resilient to random failure: removing random nodes rarely fragments the network because biological systems have evolved redundancy and alternative pathways.
• Pattern of connections is functionally significant: the specific wiring diagram determines the system’s behaviour, not just the degree distribution.

Evaluating Exam Graphs

When asked “does this real-world network resemble the graph in the question?”, compare against the four types:

2020 Q9 $4 \times 4$ grid: NOT realistic. Properties missing: no hubs (uniform degree), no clustering variation, regular lattice structure, no power-law degree distribution, no weak ties or local bridges between communities. Real networks look nothing like regular grids.

2025 Q8 graph (A–H): somewhat more realistic for a small social network. Has a leaf (E — peripheral member), a moderately central connector (C), and some clustering (triangle C–D–F). But still artificial: real networks have many more nodes, power-law degree distribution, and organic growth patterns.

Summary Table

Property	Social	Information	Technological	Biological
Edge direction	Undirected	Directed	Mostly undirected	Both
Clustering	High	Low–medium	Low	High (modular)
Degree distribution	Power-law-ish	Power-law	Constrained	Varies
Hub existence	Yes	Extreme hubs	Capped hubs	Moderate
Key mechanism	Triadic closure	Preferential attachment	Physical/cost constraints	Functional modularity
Attack resilience	Moderate	Very fragile	Fragile	Resilient

Past paper questions: y2020p3q9