Abstract
Understanding the functions carried out by network subgraphs is important to revealing the organizing principles of diverse complex networks. Here, we study this question in the context of collaborative problem-solving, which is central to a variety of domains from engineering and medicine to economics and social planning. We analyze the frequency of all three- and four-node subgraphs in diverse real problem-solving networks. The results reveal a strong association between a dynamic property of network subgraphs-synchronizability-and the frequency and significance of these subgraphs in problem-solving networks. In particular, we show that highly-synchronizable subgraphs are overrepresented in the networks, while poorly-synchronizable subgraphs are underrepresented, suggesting that dynamical properties affect their prevalence, and thus the global structure of networks. We propose the possibility that selective pressures that favor more synchronizable subgraphs could account for their abundance in problem-solving networks. The empirical results also show that unrelated problem-solving networks display very similar local network structure, implying that network subgraphs could represent organizational routines that enable better coordination and control of problem-solving activities. The findings could also have potential implications in understanding the functionality of network subgraphs in other information-processing networks, including biological and social networks.