Efficient discovery of large-scale patterns in weighted networks

Networks provide a rich and mathematically principled approach to characterizing the structure of complex systems. A common step in understanding the structure and function of real-world networks is to characterize their large-scale organizational pattern via community detection, in which we aim to find a network partition that groups together vertices with similar connectivity patterns. Although interactions in most real-world systems take real or integer valued weights, common approaches to community detection use only the unweighted edges, thereby ignoring a potentially rich source of additional information. In this talk, I will describe a generalization of the popular stochastic block model that can discover community structure from both the existence and weight of edges. This model can be efficiently fitted to real-world networks using ``approximate inference'' techniques, like the cavity method, originally developed in statistical physics and which are now commonly used by computer scientists in machine learning. Applied to several real-world networks, I show that edge weights sometimes contain hidden information that is distinct from what is contained in edge existences. Learning from weights also provides better estimates of missing information. I will close with a few brief comments on the impact of weight information on the detectability threshold for recovering hidden patterns in these systems, and on future opportunities in this area.