The microstructure of highly aggregated colloidal dispersions was investigated by probing the rheological behavior of magnetic suspensions. The dynamic moduli as functions of frequency and strain amplitude are shown to closely resemble that of colloidal gels indicating the formation of network structure. The two types of characteristic critical strain amplitudes, γc and γy, were characterized in terms of the changing microstructure. The amplitude of γc indicates the transition from linear to nonlinear viscoelasticity and depends only on particle volume fraction not magnetic interactions. The study of scaling behavior suggests that it is related to the breakage of interfloc, i.e., floc-floc structure. However, yielding strain, γy, was found to be independent of particle volume fraction as well as magnetic interaction. It relates to extensive deformation resulting in yielding behavior. The scaling of elastic constant, Ge, implies that this yielding behavior and hence γy is due to the breakage of long-range interfloc interactions. Also, the deformation of flocs due to increase strain was indicated from the investigation of the fractal nature.