Back to search

Rochester Institute of Technology

Sampling and Counting Graph Structures with Triangle Motifs

Abstract

dc:description.abstract

Understanding the structure of real-world networks often relies on identifying significant (i.e., occurring significantly more frequently than random) subgraph patterns, or motifs, such as triangles. To assess their significance, null models generate random samples from a constrained distribution of graphs, preserving selected properties while randomizing others. These models may either generate random graphs or sample structures from a fixed input graph. This thesis focuses on the latter, specifically the problem of sampling and counting graph structures that incorporate triangle motifs. While efficient algorithms exist for sampling classical structures such as matchings, extending these methods to higher-order motifs remains an important challenge. We introduce the Monomer–Dimer–Trimer (MDT) model: the problem of sampling collections of vertex-independent edges and triangles from a fixed input graph. To address this problem, we develop a Markov chain Monte Carlo (MCMC) method for approximately sampling from the space of valid structures and analyze its mixing time. We establish polynomial mixing time bounds on graphs of bounded pathwidth and degree, with a corollary extending to bounded treewidth. By the sampling-to-counting reduction, this also yields approximate counting algorithms for MDT structures on the same class of graphs. Our analysis highlights the challenges in extending existing techniques for mixing time bounds to settings involving higher-order motifs, and contributes toward the development of null models for the organization of such motifs in networks. We also consider a separate counting problem: enumerating graphs with a prescribed number of vertices and triangles within restricted families of path-like graphs. We present combinatorial formulations for counting these structures and show how they give rise to efficient sampling procedures via the counting-to-sampling reduction. Together, these results advance understanding of sampling and counting of higher-order structures in graphs.

Degree

thesis:*
Name thesis:degree_name
Computer Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science, Department of

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Robinson, Sherry
Contributors dc:contributor
  • Ivona Bezáková

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/12576

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Robinson, Sherry. Sampling and Counting Graph Structures with Triangle Motifs. Thesis thesis, https://repository.rit.edu/theses/12576