Costas Bampos, Vasileios Megalooikonomou
Graphical representations model complex networks by encoding entities as vertices and interactions as edges, with recurring subgraphs—or motifs—revealing fundamental organizational principles. We present a novel application of Hidden Markov Models (HMMs) to network motif detection: subgraphs are encoded as short symbolic sequences and scored with standard HMM kernels (Viterbi/Forward; optional Baum–Welch), producing graded likelihoods that tolerate missing or noisy edges. On a 253-node directed benchmark the HMM pipeline recovers known 4-node motifs with accuracy comparable to exact enumeration while providing a probabilistic, weight-aware scoring framework that enables principled model comparison. We also include a concise complexity comparison with ESU, FANMOD and G-Tries and discuss engineering choices (seed-and-filter, scoring-only workflows) that make the approach practical. To our knowledge, this is the first application of HMMs to network motif detection.
