Many real world networks – social, technological, biological – have wonderful structures. Some structures may be apparent (e.g. trees) while others may be hidden (e.g. communities). How can we discover hidden structures? Known approaches to “structure mining” in networks come from a variety of disciplines, including probability, statistics, combinatorics, physics, optimization, theoretical computer science, signal processing and information theory. We will focus on new probabilistic approaches to structure mining. They bring together insights from random matrices, random graphs, and semidefinite programming.