With increasing amounts of interaction data collected by high-throughput techniques,
understanding the structure and dynamics of biological networks becomes one of the central tasks in
post-genomic molecular biology. Recent studies have shown that many biological networks contain
a small set of "network motifs," which are suggested to be the basic cellular information-processing
units in these networks. Nevertheless, most biological networks have stochastic nature, due to the
intrinsic uncertainties of biological interactions and/or experimental noises accompanying the high-
throughput data. The building blocks in these networks thus also have stochastic properties. In this
paper, we study the problem of identifying stochastic network motifs that are derived from families
of mutually similar but not necessarily identical patterns of interactions. Motivated by existing
methods for detecting sequence motifs in biopolymer sequences, we establish Bayesian models for
stochastic biological networks and develop a group of Gibbs sampling strategies for finding stochastic
network motifs. The methods are applied to several available transcriptional regulatory networks and
protein-protein interaction networks, and several stochastic network motifs are successfully identified.