Network visualizations are commonly used to analyze relationships in various contexts. To efficiently explore a network visualization, the user needs to quickly navigate to different parts of the network and analyze local details. Recent advancements in display and interaction technologies inspire new visions for improved visualization and interaction design. Past research into network design has identified some key benefits to visualizing networks in 3D versus 2D. However, little work has been done to study the impact of varying levels of embodied interaction on network analysis. We present a controlled user study that compared four environments featuring conditions and hardware that leveraged different amounts of embodiment and visual perception ranging from a 2D visualization desktop environment with a standard mouse to a 3D visualization virtual reality environment. We measured the accuracy, speed, perceived workload, and preferences of 20 participants as they completed three network analytic tasks, each of which required unique navigation and substantial effort. For the task that required participants to iterate over the entire visualization rather than focus on a specific area, we found that participants were more accurate using a VR and a trackball mouse than conventional desktop settings. From a workload perspective, VR was generally considered the least mentally demanding and least frustrating in two of our three tasks. It was also preferred and ranked as the most effective and visually appealing condition overall. However, using VR to compare two side-by-side networks was difficult, and it was similar to or slower than other conditions in two of the three tasks. Overall, the accuracy and workload advantages of conditions with greater embodiment in specific tasks suggest promising opportunities to create more effective environments in which to analyze network visualizations.