The present work analyses a particular scenario of consensus formation, where the individuals navigate across an underlying network defining the topology of the walks. The consensus, associated to a given opinion coded as a simple messages, is generated by interactions during the agent's walk and manifest itself in the collapse of the various opinions into a single one. We analyze how the topology of the underlying networks and the rules of interaction between the agents promote or inhibit the emergence of this consensus. We find that non-linear interaction rules are required to form consensus and that consensus is more easily achieved in networks whose degree distribution is narrower.