Methods and apparatus for topology discovery of a network having heterogeneous network devices are disclosed. A network appliance communicates with the network devices to acquire device descriptors and characterize the network devices accordingly. Topology discovery is based on device characteristics, media-access data, and encoded connectivity patterns, where each connectivity pattern is defined by devices of specific device types and respective media-access data. A topology deduction module of the network appliance synthesizes a network image starting with unconnected devices and progressively incorporating detected connectivity patterns.