Numerous theoretical and experimental studies have investigated antagonistic coevolution between parasites and their hosts. Although experimental tests of theory from a range of biological systems are largely concordant regarding the influence of several driving processes, we know little as to how mechanisms acting at the smallest scales (individual molecular and phenotypic changes) may result in the emergence of structures at larger scales, such as coevolutionary dynamics and local adaptation. We capitalized on methods commonly employed in community ecology to quantify how the structure of community interaction matrices, so called ‘bipartite networks’, reflected observed coevolutionary dynamics, and how phages from these communities may or may not have adapted locally to their bacterial hosts. We found a consistent nested network structure for two phage types, one previously demonstrated to exhibit arms race coevolutionary dynamics and the other fluctuating coevolutionary dynamics. Both phages increased their host ranges through evolutionary time, but we found no evidence for a trade off with impact on bacteria. Finally, only bacteria from the arms race phage showed local adaptation, and we provide preliminary evidence that these bacteria underwent (sometimes different) molecular changes in the wzy gene associated with the LPS receptor, while bacteria coevolving with the fluctuating selection phage did not show local adaptation and had partial deletions of the pilF gene associated with Type IV pili. We conclude that the structure of phage-bacteria interaction networks is not necessarily specific to coevolutionary dynamics, and discuss hypotheses for why only one of the two phages was, nevertheless, locally adapted.