The structure of water clusters that have adsorbed from one to six methane molecules is studied by molecular dynamics simulation. Characteristic structural units of Voronoi and hybrid polyhedra are employed to reveal the structural changes resulting from the attachment of CH4 molecules to the clusters. The most significant changes in topological properties are associated with variations in the number of faces of simplified polyhedra. A change is unambiguously detected in the small-angle peak intensity in the angular distribution of nearest geometrical neighbors determined with the use of the Voronoi polyhedra. The results of two different calculations of the number of hydrogen bonds in the clusters are compared, and the “nonsphericity” coefficients are calculated for the polyhedra.