Network Science — problem sets

Six problem sets from the Network Science course, 2nd year, Universitat Pompeu Fabra (2022). Each takes a real dataset and applies one family of graph methods to it: bipartite projection, network construction from text, HITS, PageRank, random-graph models, and spectral analysis.

The interest is mostly in the datasets — a food-flavour compound database, a corpus of Catalan tweets from the COVID lockdown, OECD/BRICS trade flows, a 114,529-host web-spam crawl, a Game of Thrones character graph, and Zachary's karate club.

Read this first — scaffolded coursework

These are course problem sets, not original projects. The course supplied the datasets, the surrounding exercise text, the plotting helpers and a good deal of the code; the student filled in the answers. Cells the course marked # LEAVE AS-IS or # Leave as-is are course code and are labelled as such in the extracted modules. Each module's docstring states which functions are the student's answers and which are scaffolding.

Problem sets and results

All numbers are read from the notebooks' stored outputs.

PS03 — flavour network (bipartite projection)

Ingredients and the flavour compounds they contain, projected into an ingredient–ingredient graph linked by shared compounds.

Distinct ingredients	1,530
Ingredient–ingredient graph	164 nodes, 2,043 edges

PS04 — building networks from text

Mention and co-mention graphs extracted from Catalan tweets during the COVID lockdown.

Most-frequent co-mention pairs: QuimTorraiPla → govern (92), elnacionalcat → joseantich (90), QuimTorraiPla → tjparfitt (59), josepcosta → sanchezcastejon (49), emergenciescat → govern (31).

PS05 — hubs and authorities (HITS) on trade flows

Directed export graphs for OECD ∪ BRICS+, 1980 vs 2013.

Year	Nodes	Edges
1980	41	1,082
2013	48	1,833

Top hubs (exporters) in 2013: China 0.1926, Canada 0.1242, Mexico 0.1071, Germany 0.0757. Top authorities (importers) in 2013: USA 0.1088 (1980 value), with USA, Japan, Germany and France leading the 2013 ranking.

The dataset's headline finding: China's exports grew 141.1× between 1980 and 2013 ($715M → $100,868M) against the USA's 6.2×, and China's hub score rises from 0.0081 to 0.1926 accordingly.

PS06 — PageRank on a web-spam graph

The webspam-uk2007 host graph.

Hosts	114,529
Labelled spam	344	0.30 %
Labelled non-spam	5,709	4.98 %
Unlabelled	108,476	94.71 %

25 power-iteration steps. Top hosts by PageRank: www.opsi.gov.uk 0.006376, www.ico.gov.uk 0.003762, www.adobe.co.uk 0.003418, www.dti.gov.uk 0.003083, www.kelkoo.co.uk 0.003080.

Re-running with spam links removed barely moves the ranking (www.opsi.gov.uk 0.006369 vs 0.006376), which is the point of the exercise: the top of the PageRank distribution is robust to this spam set. The gain-ratio analysis then surfaces hosts whose PageRank is anomalously high relative to their non-spam PageRank — e.g. www.aili.co.uk, gain 91.59.

PS07 — random graph models

Erdős–Rényi edge count over 1,000 trials at N=200, p=0.65: observed 12,937.12 edges against an expected 12,935.00 — a 0.016 % discrepancy.

Target vs observed average degree tracks closely across ⟨k⟩ ∈ [0, 2) (e.g. target 0.400 → observed 0.408), and the largest-connected-component sweep reproduces the giant-component transition. Preferential attachment produces the expected heavy-tailed degree distribution.

PS09 — spectral graph analysis

Laplacian L = D − A built by hand and verified equal to nx.laplacian_matrix element-by-element ("OK - computed correctly"), then used for spectral layout.

Applied to a 12×8 grid (recovers the lattice), three stochastic block models with decreasing inter-community probability (communities separate as it falls), a Game of Thrones subgraph of Houses Stark, Lannister and Targaryen (20 nodes), and Zachary's karate club. Extra credit: 3-D projection of a 3×3×3 grid using the third eigenvector as Z.

Structure

src/
  flavors_bipartite.py     PS03 — bipartite projection
  text_networks.py         PS04 — mention/co-mention extraction
  hits.py                  PS05 — hubs and authorities
  pagerank.py              PS06 — power iteration
  random_graph_models.py   PS07 — ER and BA generators
  spectral.py              PS09 — Laplacian and spectral projection
experiments/
  _paths.py                puts src/ on sys.path, resolves data/ dirs
  run_ps03_flavors.py  run_ps04_text_networks.py  run_ps05_hits.py
  run_ps06_pagerank.py run_ps07_network_models.py run_ps09_spectral.py
data/                      datasets, grouped per problem set
notebooks/                 the six original notebooks, with plots and questions

How to run

python -m venv .venv && source .venv/bin/activate   # Windows: .venv\Scripts\activate
pip install -r requirements.txt

python experiments/run_ps07_network_models.py --no-plots
python experiments/run_ps09_spectral.py --skip 3d

Drivers can be run from anywhere; _paths.py resolves everything relative to the repository root.

Limitations and honest notes

• src/spectral.py's diagonal_degree_matrix and adjacency_matrix are O(n²) with a list(g.nodes()) call inside the inner loop — effectively O(n³). Fine for the graphs here (≤ 96 nodes), unusable at scale. Preserved as submitted.
• Some datasets are gitignored for size; see data/ for what is bundled.

Author

José Mª Pérez Clar

Datasets, exercise statements and all code marked LEAVE AS-IS are Network Science course materials, UPF.