Mixture models and exploratory analysis in networks

Abstract

Networks are widely used in the biological, physical, and social sciences as a concise mathematical representation of the topology of systems of interacting components. Understanding the structure of these networks is one of the outstanding challenges in the study of complex systems. Here we describe a general technique for detecting structural features in large-scale network data that works by dividing the nodes of a network into classes such that the members of each class have similar patterns of connection to other nodes. Using the machinery of probabilistic mixture models and the expectation-maximization algorithm, we show that it is possible to detect, without prior knowledge of what we are looking for, a very broad range of types of structure in networks. We give a number of examples demonstrating how the method can be used to shed light on the properties of real-world networks, including social and information networks.

Fig. 1.

Application of the method described here to the “karate club” network of ref. . The two shaded regions indicate the division of the network in the real world, whereas the shades of the individual vertices indicate the decomposition chosen by the algorithm. The sizes of the vertices indicate the probabilities θ_1i for edges from vertices in group 1 (the left group) to be connected to each other vertex, with the probabilities ranging from 0 for the smallest vertices to 0.19 for the largest.

Fig. 2.

The adjacency network of English words described in the text. The two shaded groups contain adjectives and nouns respectively and the shades of the individual vertices represent the classification found by the algorithm.

Fig. 3.

A directed social network of U.S. high school students and the division into two groups found by the directed version of our method. Vertex shapes show the (self-identified) ethnicity of the students, as indicated.

Fig. 4.

The four-group network described in the text, in which connections between vertices are entirely random, except for connections to the eight keystone vertices in the center. Each of the four groups (dashed boxes) is thus distinguished solely by the unique pattern of its connections to the keystone vertices. Vertex shapes represent the groups to which vertices are assigned by our analyses using the traditional community detection (a) and maximum likelihood (b) methods of this paper.