Discrete Mathematics, Graphs and Network Models

Introduction

Data science frequently studies objects that are discrete rather than continuous: customers, products, transactions, documents, web pages, users, proteins, locations and events. These objects are often related through purchases, communication, citations, hyperlinks, shared attributes or semantic associations. Graph theory provides a formal language for representing and analysing such relationships, while combinatorics and recurrence relations support counting, optimisation and algorithm design.

A graph model does not merely display relationships. It permits questions such as: Which users are structurally influential? How many routes connect two locations? Which products are likely to be recommended together? Is a transaction network divided into communities? Can a knowledge graph infer a missing relationship? These questions require mathematical representations, measures and algorithms.

This chapter develops the foundations needed to model social, transactional, recommendation and knowledge-graph data. It combines formal definitions with computational interpretation, worked examples and limitations relevant to postgraduate data science.

Learning Objectives

By the end of this chapter, you should be able to:

1. Apply combinatorial principles to discrete data problems.
2. Formulate and solve simple recurrence relations.
3. Represent directed, undirected, weighted, signed and bipartite graphs.
4. Analyse paths, cycles, connectivity, trees and spanning trees.
5. Compute and interpret degree, closeness, betweenness and eigenvector centrality.
6. Construct and interpret adjacency, incidence and graph Laplacian matrices.
7. Select suitable graph algorithms for search, shortest paths, ranking and community analysis.
8. Evaluate graph models critically, including their assumptions, bias, scalability and ethical implications.

1. Combinatorics for Data Science

Combinatorics is the mathematics of finite arrangements, selections and configurations. It is relevant to feature-subset selection, experiment design, hashing, search spaces, probability models and the complexity of graph algorithms.

1.1 Fundamental counting principles

If a process consists of successive stages with n₁, n₂, ..., n_k choices at each stage, and every complete outcome contains one choice from each stage, then the multiplication principle gives

where N is the number of complete outcomes. The principle assumes that the stated choices are the relevant alternatives at each stage.

If outcomes belong to mutually exclusive cases with counts N₁, ..., N_k, the addition principle gives

For example, a recommendation system selecting one of 8 categories and one of 5 price bands has 8 × 5 = 40 category–price combinations.

1.2 Permutations and combinations

The number of ordered selections of r distinct objects from n objects is

The number of unordered selections is

The permutation formula applies when order matters and repetition is not allowed. The combination formula applies when order does not matter and repetition is not allowed.

If repetition is allowed, the number of ordered sequences of length r from n types is n^r. The number of unordered selections with repetition is

Worked example: feature subsets

Suppose a modelling team has 12 candidate variables and wishes to compare every model using exactly 4 variables. The number of subsets is

C(12,4) = 12!/(4!8!) = 495.

Thus, exhaustive evaluation requires 495 feature subsets before considering hyperparameters or resampling. This illustrates why combinatorial search can quickly become computationally impractical.

1.3 Inclusion–exclusion

When sets overlap, adding their sizes double-counts shared elements. For two sets A and B,

For three sets,

This is useful when counting users satisfying overlapping conditions, such as users who purchased a product, viewed it or added it to a basket.

2. Recurrence Relations and Discrete Processes

A recurrence relation defines a sequence using earlier terms. It is useful for analysing recursive algorithms, dynamic programming, population processes, ranking iterations and time-evolving networks.

A first-order linear recurrence has the form

where a and b are constants and x₀ is an initial value. If a ≠ 1, its closed form is

If a = 1, then x_t = x₀ + tb. When |a| < 1, the influence of the initial condition decays and the sequence approaches the fixed point x^* = b/(1−a).

Worked example: iterative network score

Suppose a score is updated by x_t = 0.8x_t−1+6, with x₀ = 10. The first two values are x₁ = 14 and x₂ = 17.2. The limiting score is

x^* = 6/(1−0.8) = 30.

The model converges because the magnitude of the multiplier, 0.8, is less than 1. In practical ranking systems, convergence also depends on normalisation, graph structure and whether the update operator is stable.

Second-order recurrences, such as x_t = c₁x_t−1+c₂x_t−2, are solved using a characteristic equation. However, real graph algorithms often use matrix recurrences, discussed later in connection with random walks and PageRank.

3. Graph Fundamentals

A graph is formally written as G=(V,E), where V is a set of vertices or nodes and E is a set of edges. Nodes may represent users, products or entities; edges represent relationships or interactions.

Important graph types include:

The degree of an undirected node v is deg(v), the number of incident edges. In a directed graph, deg^+(v) is out-degree and deg^−(v) is in-degree. The handshaking lemma states

because every undirected edge contributes two to the total degree. For a directed graph,

A subgraph contains selected vertices and edges from a larger graph. A complete graph K_n contains every possible edge between n distinct vertices and therefore has n(n−1)/2 edges. A graph is dense when it contains a large fraction of possible edges and sparse when it contains relatively few.

4. Paths, Cycles and Connectivity

A walk is a sequence of vertices and edges in which repetition is allowed. A trail does not repeat edges. A path does not repeat vertices. A cycle is a closed path whose initial and final vertices coincide.

For a weighted graph, the length of a path is usually the sum of its edge weights:

This interpretation assumes weights represent additive quantities such as distance, cost or time. If weights represent similarity or strength, a transformation may be required before shortest-path algorithms are used.

Two vertices are connected if a path exists between them. An undirected graph is connected if every pair of vertices is connected. A directed graph is strongly connected if every ordered pair is mutually reachable; it is weakly connected if connectivity appears after ignoring edge directions.

A bridge is an edge whose removal increases the number of connected components. An articulation point is a vertex whose removal increases that number. These concepts identify vulnerable links in infrastructure, supply and communication networks.

The distance d(u,v) is the length of a shortest path between vertices u and v. The diameter is the maximum finite distance among vertex pairs. In disconnected graphs, distance may be infinite, so average path length must be defined on connected pairs or components.

5. Trees and Spanning Structures

A tree is a connected undirected graph with no cycles. For a tree with n ≥ 1 vertices, the following are equivalent:

• It is connected and has n−1 edges.
• It is acyclic and has n−1 edges.
• Exactly one path exists between every pair of vertices.

A rooted tree designates one vertex as the root and gives each non-root vertex a parent. Such structures appear in taxonomies, decision trees, file systems and hierarchical knowledge representation.

A spanning tree of a connected graph contains all vertices and is a tree. A minimum spanning tree (MST) minimises the total edge weight among all spanning trees. Kruskal’s algorithm sorts edges by increasing weight and adds an edge when it does not create a cycle. Prim’s algorithm grows a tree by repeatedly adding the least-weight edge connecting the current tree to an unvisited vertex. Both require suitable handling of ties and are normally implemented with a disjoint-set structure or priority queue.

An MST is not a shortest-path tree: it minimises total network connection cost, not the distance from one source to every destination.

6. Graph Representation and Matrices

6.1 Adjacency matrix

For a graph with n vertices, the adjacency matrix A is an n×n matrix. For a simple unweighted graph, A_ij=1 if an edge joins i and j, and 0 otherwise. In an undirected graph, A=A^T. For a weighted graph, A_ij stores the edge weight, with absent edges represented by 0, infinity or a separate mask depending on the algorithm.

Matrix powers have a useful interpretation: for an unweighted graph, (A^k)_ij equals the number of walks of exactly k edges from i to j. This counts walks, not necessarily simple paths.

6.2 Incidence matrix

An incidence matrix records which vertices touch which edges. For an undirected graph it has one row per vertex and one column per edge, with a 1 when incident and 0 otherwise. For a directed graph, a common signed convention places −1 at the source and +1 at the destination.

6.3 Graph Laplacian

For an undirected weighted graph, let D be the diagonal degree matrix, where D_ii=∑_j A_ij. The combinatorial Laplacian is

For any vector x,

where each undirected edge is counted once. This identity assumes symmetric non-negative weights. It shows that the Laplacian penalises large differences between connected vertices and underlies spectral clustering, semi-supervised learning and graph signal processing. The number of zero eigenvalues of L equals the number of connected components.

7. Centrality and Structural Importance

Centrality measures identify nodes that are important according to a specified definition. No centrality measure is universally best; interpretation depends on the network and task.

Degree centrality

For an undirected graph with n vertices, normalised degree centrality is

It measures immediate connectivity. In directed graphs, in-degree may indicate popularity, whereas out-degree may indicate activity or broadcasting.

Closeness centrality

For a connected graph,

where d(v,u) is shortest-path distance. For disconnected graphs, harmonic centrality is often safer:

with the term defined as 0 when u is unreachable from v.

Betweenness centrality

Here σ_st is the number of shortest paths from s to t, and σ_st(v) is the number passing through v. Normalisation is commonly by (n−1)(n−2)/2 for undirected graphs. Betweenness identifies brokerage, but it can be unstable when edge weights or ties change.

Eigenvector centrality

Eigenvector centrality assigns high scores to nodes connected to other high-scoring nodes. It is represented by

where A is the adjacency matrix, x is the score vector and λ is an eigenvalue. Under conditions such as a non-negative, irreducible adjacency matrix, the Perron–Frobenius theorem supports a positive dominant eigenvector. In directed networks, PageRank modifies this idea using a damped random walk to address sinks and disconnected structure.

Centrality must not be interpreted causally. A highly central user is not necessarily influential in changing behaviour, and a high-degree account may be automated or fraudulent.

8. Fundamental Network Algorithms

Breadth-first search

Breadth-first search (BFS) explores an unweighted graph layer by layer from a source. It computes shortest path lengths in number of edges and runs in O(|V|+|E|) time with adjacency lists. It is appropriate when all edges have equal cost.

Depth-first search

Depth-first search (DFS) explores as far as possible before backtracking. It supports cycle detection, topological sorting in directed acyclic graphs and connected-component analysis. Its time complexity with adjacency lists is also O(|V|+|E|)—assuming each vertex and edge is processed a constant number of times.

Dijkstra’s algorithm

Dijkstra’s algorithm finds shortest paths from one source when all edge weights are non-negative. With a binary heap and adjacency lists, a common complexity is O((|V|+|E|)log|V|). It is invalid for graphs containing negative edge weights.

Bellman–Ford

Bellman–Ford supports negative edge weights and can detect reachable negative cycles. Its typical complexity is O(|V||E|). A negative cycle makes a finite shortest path undefined for vertices reachable through repeated cycling.

Floyd–Warshall

Floyd–Warshall computes all-pairs shortest paths using dynamic programming:

where d_ij^(k) is the best distance from i to j using only the first k intermediate vertices. Its time complexity is O(|V|³), so it is generally more suitable for smaller dense graphs.

Random walks and PageRank

A random walk moves from a node to a neighbour according to transition probabilities. If P is a row-stochastic transition matrix and r_t is a row vector of node probabilities, then

PageRank introduces a damping parameter α, commonly near 0.85, and a teleportation distribution q:

The vector q is a probability distribution, and α lies between 0 and 1. The equation is solved iteratively or through linear algebra. PageRank is a ranking model, not a direct measure of truth, quality or social value.

Community detection

Community detection seeks groups with more internal connection than expected under a chosen null model. Modularity is one widely used objective:

where m is the number of edges, k_i is the degree of node i, c_i is its community label and δ(c_i,c_j) equals 1 when the labels match and 0 otherwise. Modularity has a resolution limit and can produce different partitions depending on the algorithm and random seed.

9. Bipartite, Recommendation and Knowledge Graphs

In a bipartite graph, vertices are divided into sets U and I, such as users and items. Edges represent interactions. A user–item incidence matrix R can support collaborative filtering. The product RR^T measures shared items between users, while R^TR measures shared users between items. These products count co-occurrences and may require normalisation so that popular items do not dominate similarity.

A knowledge graph is commonly represented as triples (subject, predicate, object). For example, (Ada, worksAt, Institution X). Unlike a simple graph, predicates carry semantic types, and edges may have qualifiers, provenance and validity intervals. Link prediction may estimate the plausibility of a missing triple, but predicted associations are hypotheses rather than verified facts.

Graph embeddings map nodes, edges or subgraphs into vectors. Methods include random-walk approaches, message-passing graph neural networks and knowledge-graph embedding models. Their effectiveness depends on sampling, negative examples, temporal leakage, graph homophily and the quality of labels. Embeddings may encode sensitive attributes even when those attributes are removed explicitly.

10. Detailed Applied Case: Product Recommendation Network

Background

Consider an illustrative online retailer with customers, products and timestamped purchase events. The organisation wishes to recommend complementary products while avoiding recommendations based on accidental or outdated associations.

Problem

A raw transaction table does not directly show product relationships. The team must define an edge, distinguish meaningful co-purchases from popularity effects, identify product communities and evaluate recommendations without leaking future information.

Analysis

Construct a product graph in which each product is a node. Connect products purchased by the same customer within a 30-day window. Let w_ij be the number of qualifying customers who purchased both products i and j. A simple weighted adjacency matrix stores these counts. Because high-volume products create many edges, the team also considers a normalised association measure, such as cosine similarity:

where n_ij is the number of customers purchasing both items and n_i, n_j are the numbers purchasing each item. The measure lies between 0 and 1 for non-negative purchase vectors, although it does not account for expected co-occurrence under a statistical null model.

BFS can identify products within a limited number of association steps. Weighted shortest paths can be used when edge cost is defined as 1/w_ij, but this transformation assumes stronger association should represent shorter distance and requires care when weights are zero. Degree identifies broadly connected products; betweenness may reveal products bridging otherwise separate categories; community detection may expose complementary product families.

Approach and solution

The team uses a time-based split: earlier transactions form the graph and later transactions form the evaluation period. Candidate recommendations are generated from neighbouring products and ranked using a combination of association strength, inventory availability and business rules. Evaluation includes precision at k, recall at k, coverage and novelty. Recommendations involving regulated, age-restricted or sensitive products receive additional controls.

Outcome

The graph reveals that some apparently strong relationships are caused by a small number of bulk purchasers. Minimum-support thresholds, customer-level deduplication and time validation reduce these artefacts. The resulting system improves useful complementary recommendations while preserving an audit trail for why a pair was suggested.

Learning points

1. Graph construction is a modelling decision, not a neutral data transformation.
2. Centrality and community structure depend on edge definitions and weights.
3. Temporal validation is essential in evolving transaction networks.
4. Popularity, exposure and purchasing power can create structural bias.
5. Human-readable provenance improves governance and debugging.

11. Limitations, Governance and Best Practice

Graph results are sensitive to missing nodes, missing edges, duplicate records, boundary choices and time windows. A social graph may represent observed communication rather than friendship. Absence of an edge may mean no relationship, no observation or restricted access. Analysts must therefore distinguish a closed-world assumption—unrecorded relationships are treated as false—from an open-world assumption—unrecorded relationships may simply be unknown.

Privacy risks are substantial because relational data can identify people through structure even after names are removed. Re-identification, inference of sensitive affiliations, discriminatory ranking and surveillance are important concerns. Data minimisation, purpose limitation, access control, retention limits, provenance and documented consent should guide graph projects. Differential privacy or aggregation may reduce risk, but privacy protection can also reduce utility and distort connectivity.

Best practice includes:

• Define nodes, edges, direction, weight and time semantics before analysis.
• Validate graph construction against domain knowledge.
• Preserve provenance and version graph snapshots.
• Select algorithms whose assumptions match the data.
• Report disconnected components, missingness and sensitivity analyses.
• Prevent temporal and entity leakage in predictive evaluation.
• Compare centrality results across reasonable model specifications.
• Monitor changes in graph structure after deployment.
• Treat predictions and inferred links as uncertain outputs.
• Document fairness, privacy and security risks.

Contemporary graph data science increasingly combines symbolic knowledge graphs with machine-learning embeddings, temporal graphs, graph neural networks and retrieval systems. These methods can improve representation of relational context, but they introduce new concerns: oversmoothing in deep message passing, spurious propagation, opaque explanations, adversarial edges and computational demands. A sophisticated model does not compensate for a poorly defined graph.

Chapter Summary

Discrete mathematics supplies counting principles and recurrence relations for analysing finite search spaces, iterative processes and algorithmic complexity. Graphs model entities and relationships using vertices, edges, weights, direction, signs and time. Paths, cycles, connectivity, bridges and articulation points describe reachability and structural vulnerability, while trees and spanning trees support hierarchy and network design.

Adjacency, incidence and Laplacian matrices provide algebraic representations. Centrality measures capture different notions of importance: degree measures local connectivity, closeness measures reachability, betweenness measures brokerage and eigenvector methods measure connection to important neighbours. BFS, DFS, Dijkstra, Bellman–Ford, Floyd–Warshall, random walks and community detection solve distinct problems under distinct assumptions.

Recommendation and knowledge-graph applications demonstrate that graph construction is an interpretive act. Reliable analysis requires temporal validation, sensitivity testing, provenance, privacy protection and careful distinction between observed and inferred relationships.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An entity represented as a node in a graph.

Edge: A relationship or interaction between vertices.

Degree: Number of edges incident to a vertex.

Directed graph: A graph whose edges have source and destination.

Weighted graph: A graph whose edges carry numerical values.

Path: A sequence of vertices with no repeated vertex.

Cycle: A closed path.

Connectivity: Reachability between vertices.

Bridge: An edge whose removal increases components.

Articulation point: A vertex whose removal increases components.

Tree: A connected acyclic undirected graph.

Spanning tree: A tree containing every vertex of a connected graph.

Adjacency matrix: Matrix encoding vertex-to-vertex connections.

Graph Laplacian: Matrix L=D−A for an undirected weighted graph.

Centrality: A measure of structural importance.

Betweenness centrality: Importance based on shortest paths passing through a node.

Bipartite graph: Graph with two vertex sets and cross-set edges only.

PageRank: A damped random-walk ranking method.

Knowledge graph: A graph of semantically typed entities and relations.

Review Questions

Short Answer Questions

1. State the multiplication principle and give one data-science example.
2. What is the difference between a walk, a trail and a path?
3. Why does the degree sum of an undirected graph equal twice its number of edges?
4. Distinguish an adjacency matrix from a graph Laplacian.
5. Why is Dijkstra’s algorithm unsuitable for negative edge weights?

Long Answer Questions

1. Explain the main graph types used in social, transactional and knowledge-graph data, including their modelling implications.
2. Derive and interpret the closed form of the recurrence x_t=ax_t−1+b for a≠1.
3. Compare degree, closeness, betweenness and eigenvector centrality, including one limitation of each.
4. Explain how BFS, DFS, Dijkstra, Bellman–Ford and Floyd–Warshall differ in purpose and assumptions.
5. Discuss the construction, interpretation and governance of a product co-purchase graph.

Analytical / Application Questions

1. A communication network has 10 vertices and 18 undirected edges. Use the handshaking lemma to determine the sum of all vertex degrees. Explain whether the result alone proves that the graph is connected.
2. Design a graph representation for a knowledge graph containing entities, typed relations, provenance and validity dates. Explain which information a simple adjacency matrix would lose.
3. A recommendation graph contains many popular products and a small number of niche products. Propose a centrality, weighting and evaluation strategy that reduces popularity bias and avoids temporal leakage.

Multiple Choice Questions with Answers

Question 1

How many unordered subsets of 4 variables can be selected from 12 variables?

A. 48

B. 220

C. 495

D. 1,728

Correct Answer: C. 495

Question 2

For an undirected graph with 15 edges, what is the sum of all vertex degrees?

A. 15

B. 30

C. 45

D. 225

Correct Answer: B. 30

Question 3

Which condition is required for Dijkstra’s algorithm to provide valid shortest paths?

A. The graph must be complete

B. All edge weights must be non-negative

C. The graph must be acyclic

D. Every vertex must have equal degree

Correct Answer: B. All edge weights must be non-negative

Question 4

Which centrality measure is most directly associated with brokerage on shortest paths?

A. Degree centrality

B. Closeness centrality

C. Betweenness centrality

D. Density

Correct Answer: C. Betweenness centrality

Question 5

For an undirected weighted graph, the standard combinatorial Laplacian is

A. L = A − D

B. L = A + D

C. L = D − A

D. L = D⁻¹A

Correct Answer: C. L = D − A

Question 6

A tree with 20 vertices has how many edges?

A. 19

B. 20

C. 21

D. 40

Correct Answer: A. 19

Question 7

What does BFS compute in an unweighted graph when started from a source?

A. A minimum spanning tree by weight

B. Shortest path lengths measured in edges

C. All negative cycles

D. The dominant eigenvector

Correct Answer: B. Shortest path lengths measured in edges

Question 8

In a bipartite user–item graph, what does R^TR primarily represent when R is a user–item incidence matrix?

A. User-to-user co-occurrence

B. Item-to-item co-occurrence through users

C. Shortest path distances

D. The graph Laplacian

Correct Answer: B. Item-to-item co-occurrence through users

Question 9

In PageRank, the damping parameter controls

A. The number of graph vertices

B. The balance between following links and teleportation

C. Whether edges are directed

D. The weight of self-loops only

Correct Answer: B. The balance between following links and teleportation

Question 10

Which statement about an MST is correct?

A. It minimises every source-to-destination distance

B. It contains all vertices and minimises total spanning weight

C. It can contain cycles if weights are positive

D. It requires directed edges

Correct Answer: B. It contains all vertices and minimises total spanning weight