Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Mining sequences, graphs and networks

Covers definitions, algorithms and measures used to mine sequential patterns, and to mine and analyse graphs and networks (frequent subsequences, PrefixSpan, graph metrics, PageRank, frequent subgraphs, modularity and link prediction).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Mining sequences, graphs and networks finds useful order, structure and relationships in data. An engineer uses these methods to discover user behaviour patterns (clickstreams, purchase sequences), detect communities or anomalies in social or communication networks, and predict links or influence spread in networked systems.

Key ideas

Start from first principles and simple definitions.

  • Graph: a pair G = (V, E) where V is a set of vertices (nodes) and E is a set of edges. If edges have direction, G is a directed graph; otherwise it is undirected. If edges have numbers (weights), the graph is weighted.

  • Sequence: an ordered list of items or itemsets. A sequence database is a collection of sequences (one per transaction/customer/session).

  • Subsequence: sequence s = <a1, a2, ... ak> is a subsequence of sequence t = <b1, b2, ... bm> if there exist indices i1 < i2 < ... < ik such that aj = bij for all j. If elements are itemsets (events with multiple items), require aj ⊆ bij. If matches must be adjacent, call it a contiguous subsequence.

  • Support (sequence mining): the support of a sequence s is the fraction (or count) of sequences in the database that contain s as a subsequence. A sequence is frequent if its support ≥ minimum support threshold (minsup).

  • Sequential pattern mining problem: given a sequence database and minsup, find all frequent subsequences.

  • Two common algorithm families:

    • Apriori-based sequential mining (GSP): iteratively generate candidate k-length sequences from frequent (k−1)-sequences and test support by scanning database. Uses Apriori property: every (k)-frequent sequence has all (k−1)-subsequences frequent.
    • Pattern-growth methods (PrefixSpan): avoid candidate generation by projecting the database on prefixes and growing patterns recursively. For each frequent prefix, build a projected database of suffixes, then find local frequent items to extend the prefix. In itemset-sequence mining, distinguish I-extension (add an item to the last element) and S-extension (append a new element).
  • Closed sequence: a frequent sequence s is closed if no supersequence of s has the same support. Maximal sequence is frequent and has no frequent supersequence.

  • Adjacency matrix: for graph G with n vertices, A is an n×n matrix where A_{ij} = 1 if edge (i,j) exists (or the weight), else 0.

  • Degree (undirected): for node v, deg(v) = number of incident edges. For directed graphs: in-degree and out-degree.

  • Clustering coefficient: tendency of a node’s neighbours to be connected; local C_v = 2 e_v / (deg(v)(deg(v)-1)) for undirected simple graphs (e_v edges among neighbours).

  • Centrality measures:

    • Degree centrality: number of neighbours (simple, local).
    • Betweenness centrality: sum over all node pairs of the fraction of their shortest paths that pass through node v (global, expensive to compute exactly).
    • Eigenvector centrality / PageRank: node importance proportional to importance of its neighbours; PageRank is eigenvector centrality with random jump (damping).
    • Closeness centrality: inverse of the average shortest-path distance from v to all reachable nodes (use harmonic closeness for directed/disconnected graphs).
  • Connected component: a maximal set of nodes where each pair is connected by a path (for undirected graphs). For directed graphs use strongly connected components (SCCs).

  • Frequent subgraph mining: given a database of (labelled) graphs and support threshold, find subgraphs that appear in at least minsup graphs. Challenges: graph isomorphism (need canonical labelling) and expensive subgraph isomorphism checks. Example algorithms: gSpan (uses DFS code canonical form) and FFSM.

  • Link prediction: estimate probability of a future or missing edge. Simple scores: Common neighbours, Jaccard similarity, Adamic–Adar. Link prediction often uses node features or graph embeddings.

  • Community detection: partition nodes into groups with more internal edges than external edges. Modularity is a common objective to measure partition quality.

When deriving or proving algorithm correctness on exams, state the Apriori property, show induction on sequence length for candidate pruning, and explain why PrefixSpan reduces database scans by projection.

If an exam needs a diagram: for a small graph draw labelled nodes (A,B,C...) and edges as arrows for directed edges; for sequence mining draw a table with sequence id (SID) and sequence items separated by commas. Label projected suffixes in PrefixSpan steps.

Formulas

support(s) = count(s) / N — where count(s) is the number of sequences in the database that contain s, N is total number of sequences (unitless). Applies to sequence mining support measured as fraction.

support_count(s) = count(s) — count measured in number of sequences (unit: count).

PR(v) = (1 - d)/N + d * sum_{u in In(v)} PR(u) / outdeg(u) — PR(v) is PageRank of node v (unitless), d is damping factor (typical value 0.85), In(v) is set of nodes with edges to v, outdeg(u) is number of out-links from u. Applies to directed web-like graphs; teleportation avoids rank sinks. If outdeg(u)=0 (dangling), redistribute PR(u) uniformly to all nodes (or add its mass to the teleportation term).

J(u, v) = |N(u) ∩ N(v)| / |N(u) ∪ N(v)| — Jaccard similarity between nodes u and v; N(x) is neighbour set. Unitless, [0,1]. C_v = 2 e_v / (k_v (k_v - 1)) — local clustering coefficient for undirected simple graphs; e_v is the number of edges among neighbours of v, k_v = deg(v). Unitless, in [0,1].

Q = (1/(2m)) * sum_{i,j} [A_{ij} - (k_i * k_j)/(2m)] * delta(c_i, c_j) — modularity Q, where m is total number of edges, A_{ij} adjacency (1 or weight), k_i degree of i, c_i is community of node i, delta = 1 if c_i = c_j else 0. Unitless; higher Q (max ~1) means better community structure.

betweenness(v) = sum_{s != v != t} (sigma_{st}(v) / sigma_{st}) — sigma_{st} is number of shortest paths between s and t; sigma_{st}(v) is number of those passing through v. Unitless. closeness(v) = 1 / (sum_{u} dist(v,u)) — closeness centrality (use harmonic closeness HC(v) = sum_{u != v} 1/dist(v,u) for disconnected/directed graphs). Unitless; higher means more central.

Worked examples

Example 1 — Sequential pattern mining by hand (PrefixSpan style):

Dataset (N=5 sequences). Each sequence is ordered items (single items): SID1: <A, B, C> SID2: <A, C> SID3: <B, C> SID4: <A, B> SID5: <B, A, C>

Let minsup = 40% → minimum count = ceil(0.4 * 5) = 2 (so count ≥2). Step 1: find frequent 1-item sequences (count items present anywhere in sequence): A present in SID1,SID2,SID4,SID5 → count(A)=4 (frequent) B present in SID1,SID3,SID4,SID5 → count(B)=4 (frequent) C present in SID1,SID2,SID3,SID5 → count(C)=4 (frequent)

Step 2: For prefix <A>, build projected DB of suffixes after first A in each supporting SID: SID1 suffix <B,C>, SID2 suffix <C>, SID4 suffix <B>, SID5 suffix <C>. Find frequent items in these suffixes: B (in SID1,SID4) count=2; C (in SID1,SID2,SID5) count=3. So sequences <A,B> and <A,C> are frequent. Similarly prefix <B> projection gives frequent extensions; prefix <C> may have no extension.

Continue until no extension meets minsup. The final frequent sequences (examples): <A>, <B>, <C>, <A,B>, <A,C>, <B,C> (counts as computed). Show counts explicitly in exam answers.

Example 2 — PageRank one iteration on a small directed graph: Draw nodes: A → B, B → C, C → A, B → A (so edges: A->B, B->C, C->A, B->A). N=3. Use d=0.85 and initial PR0 = 1/3 for each node. Formula: PR1(v) = (1-d)/N + d * sum_{u in In(v)} PR0(u)/outdeg(u). Compute outdegs: outdeg(A)=1, outdeg(B)=2, outdeg(C)=1. PR1(A) = 0.05 + 0.85 * ( PR0(C)/1 + PR0(B)/2 ) = 0.05 + 0.85 * (1/3 + 1/6) = 0.05 + 0.85 * (1/2) = 0.05 + 0.425 = 0.475 PR1(B) = 0.05 + 0.85 * ( PR0(A)/1 ) = 0.05 + 0.85 * (1/3) = 0.05 + 0.283333... = 0.333333... PR1(C) = 0.05 + 0.85 * ( PR0(B)/2 ) = 0.05 + 0.85 * (1/6) = 0.05 + 0.141666... = 0.191666... Check sum ≈ 1 (0.475 + 0.333333 + 0.191666 = 1.0). Final answer: PR after 1 iteration: A=0.475, B≈0.3333, C≈0.1917.

Example 3 — Frequent subgraph idea (small): Database of 3 graphs (each undirected, unlabeled for simplicity): G1: triangle between nodes 1-2-3-1 G2: path 1-2-3 G3: triangle 1-2-3-1 plus extra node 3-4 With minsup=2 (appear in at least 2 graphs), the subgraph 'path of length 2' occurs in all three; the triangle occurs in G1 and G3 → frequent. On exam show subgraph isomorphism checks: map node labels ignoring id to find occurrences. gSpan would enumerate DFS codes; for short answers you can list frequent subgraphs and counts.

Common mistakes

  • In directed graphs forgetting edge direction when computing degree or PageRank (use in-/out-degree correctly).
  • Normalisation errors in PageRank (not checking that ranks sum to 1) or using wrong outdeg denominator.
  • For frequent subgraphs: ignoring isomorphism and double-counting the same subgraph appearance.
  • When using PrefixSpan or GSP, forgetting to project correctly (losing item order) or not pruning by minsup early.

For your exam

Typical question types: definitions (define subsequence, frequent sequential pattern, graph isomorphism), short notes (compare Apriori-based vs pattern-growth sequential mining), derivations (prove Apriori property for sequences), numericals (trace PrefixSpan or one/two iterations of PageRank on small graphs), small programs/pseudocode (write or explain PrefixSpan or gSpan high-level steps), diagrams (draw graph and label degrees/centralities), and comparison/analysis questions.

What full-marks answers include:

  • Clear definitions (bold the term if asked), assumptions (directed/undirected, labeled/unlabeled), and thresholds (minsup value and whether support measured as count or fraction).
  • Step-by-step operations for the chosen algorithm with intermediate tables (e.g., projection lists for PrefixSpan) or iterations with numeric values for PageRank, with units or unitless noted.
  • For graph mining proofs, reason about isomorphism or canonical form (state how you avoid duplicates), and state time/space complexity qualitatively.

Quick check

  1. Define a subsequence.
  2. Write the PageRank update formula and name each term.
  3. What is the difference between a closed and a maximal sequential pattern?

Answers: 1) A subsequence is an ordered list appearing in another sequence at increasing indices. 2) PR(v) = (1-d)/N + d * sum_{u in In(v)} PR(u)/outdeg(u) where PR(v) is node rank, d damping, N node count, In(v) incoming neighbours, outdeg(u) outgoing links of u. 3) A closed pattern has no supersequence with same support; a maximal pattern has no frequent supersequence at all.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?