An ICT-infrastructure (Network) graph is a necessary tool for solving of most network management problems. While the number of modern mobile devices in a Network grow up, permanent update of the Network graph is required to keep it actual and concistent. Therefore, it's required to develop more efficient and fast methods of building such graphs. In this paper we present parallel algorithm of Network graph discovery using routers' MIB data obtained with SNMP and its implementation. Described experiments confirm three-fold speed-up of the PetrSU Network graph building when using parallel algorithm.