Recent neuroimaging studies have employed graph theory as a data-driven approach to describe topological organization of the brain under different neurological disorders or task conditions and across life span. In this exploratory study, we tested whether subtle differences in interoception related to intravesical fullness can alter brain topological architecture in healthy participants. 17 right-handed women underwent a series of resting state fMRI scans that included catheterization and partial bladder filling. Using a whole brain regions of interest (ROIs), we computed several graph theory metrics to assess the efficiency of brain-wide information exchange. Results showed that brain network's topological properties significantly changed in many brain regions when we binary compared different interoceptive resting state conditions. Notably, we observed changes in global efficiency in the salience network, the central executive network, anterior dorsal attention network and the posterior default-mode network (DMN) as bladder became full and interoceptive signals intensified. Moreover, degree (the number of connections for each node), and betweenness centrality (how connected a particular region is to other regions) differed between the empty bladder, the catheterized empty bladder, and the catheterized and partially filled bladder. Comparing resting state data before and after an interoceptive task (repeated intravesical infusion and drainage) further showed increased average path length for the salience networks and decreased clustering coefficient of the DMN. These results suggest visceral interoception influences brain topological properties of resting state networks.