A network monitoring device which monitors a network in which data is transmitted through relays, includes a monitoring frequency recording unit (111) which records monitoring frequencies for monitoring transmission statuses of the relays, a selection probability generating unit (112) which generates selection probability information which is probability values for the relays, a monitoring object determining unit (113) which determines, according to the monitoring frequency and the selection probability information, a relay the transmission status of which is to be monitored, a transmission status obtaining unit (106) which obtains transmission status information indicating a transmission status on the relay determined, a transmission status recording unit (107) which records the transmission status information, an activation level calculating unit (109) which calculates, using the transmission status information, activation level indicating suitability of the monitoring on the transmission statuses of the relays, and a monitoring frequency updating unit (110) which updates, based on the activation level, the monitoring frequency, and the network monitoring device detects the change in throughput on a data transmission path highly responsively.