Performance of module identification methods. To test the performance of the method, we build ‘random networks’ with known module structure. Each test network comprises 128 nodes divided into 4 modules of 32 nodes. Each node is connected to the other nodes in its module with probability pi, and to nodes in other modules with probability po < pi. On average, thus, each node is connected to kout = 96 po nodes in other modules and to kin = 31 pi in the same module. Additionally, pi and po are selected so that the average degree of the nodes is k = 16. We display networks with: a, kin = 15 and kout = 1; b, kin = 11 and kout = 5; and c, kin = kout = 8. d, The performance of a module identification algorithm is typically defined as the fraction of correctly classified nodes. We compare our algorithm to the Girvan–Newman algorithm5,18, which is the reference algorithm for module identification11,18,19. Note that our method is 90% accurate even when half of a node's links are to nodes in outside modules. e, Our module-identification algorithm is stochastic, so different runs yield, in principle, different partitions. To test the robustness of the algorithm, we obtain 100 partitions of the network depicted in c and plot, for each pair of nodes in the network, the fraction of times that they are classified in the same module. As shown in the figure, most pairs of nodes are either always classified in the same module (red) or never classified in the same module (dark blue), which indicates that the solution is robust.