Higher-order organization of complex networks

Abstract

Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks--at the level of small network subgraphs--remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.

Fig. 1. Higher-order network structures and the higher-order network clustering framework

(A) Higher-order structures are captured by network motifs. For example, all 13 connected three-node directed motifs are shown here. (B) Clustering of a network based on motif M₇. For a given motif M, our framework aims to find a set of nodes S that minimizes motif conductance, ϕ_M(S), which we define as the ratio of the number of motifs cut (filled triangles cut) to the minimum number of nodes in instances of the motif in either S or $\overline{S}$ (13). In this case, there is one motif cut. (C) The higher-order network clustering framework. Given a graph and a motif of interest (in this case, M₇), the framework forms a motif adjacency matrix (W_M) by counting the number of times two nodes co-occur in an instance of the motif. An eigenvector of a Laplacian transformation of the motif adjacency matrix is then computed. The ordering σ of the nodes provided by the components of the eigenvector (15) produces nested sets S_r = {σ₁, …, σ_r} of increasing size r. We prove that the set S_r with the smallest motif-based conductance, ϕ_M(S_r), is a near-optimal higher-order cluster (13).

Fig. 2. Higher-order cluster in the C. elegans neuronal network

[See (29).] (A) The four-node bi-fan motif, which is overexpressed in neuronal networks (1). Intuitively, this motif describes a cooperative propagation of information from the nodes on the left to the nodes on the right. (B) The best higher-order cluster in the C. elegans frontal neuronal network based on the motif in (A). The cluster contains three ring motor neurons (RMEL, -V, and -R; cyan) with many outgoing connections, which serve as the source of information; six inner labial sensory neurons (IL2DL, -VR, -R, -DR, -VL, and -L; orange) with many incoming connections, serving as the destination of information; and four URA motor neurons (purple) acting as intermediaries. These RME neurons have been proposed as pioneers for the nerve ring (21), whereas the IL2 neurons are known regulators of nictation (22), and the higher-order cluster exposes their organization. The cluster also reveals that RIH serves as a critical intermediary of information processing. This neuron has incoming links from three RME neurons, outgoing connections to five of the six IL2 neurons, and the largest total number of connections of any neuron in the cluster. (C) Illustration of the higher-order cluster in the context of the entire network. Node locations are the true two-dimensional spatial embedding of the neurons. Most information flows from left to right, and we see that RMEV, -R, and -L and RIH serve as sources of information to the neurons on the right.

Fig. 3. Higher-order spectral analysis of a network of airports in Canada and the United States

[See (23).] (A) The three higher-order structures used in our analysis. Each motif is “anchored” by the blue nodes i and j, which means our framework only seeks to cluster together the blue nodes. Specifically, the motif adjacency matrix adds weight to the (i, j) edge on the basis of the number of third intermediary nodes (green squares).The first two motifs correspond to highly connected cities, and the motif on the right connects non-hubs to nonhubs. (B) The top 50 most populous cities in the United States, which correspond to nodes in the network. The edge thickness is proportional to the weight in the motif adjacency matrix W_M. The thick, dark lines indicate that large weights correspond to popular mainline routes. (C) Embedding of nodes provided by their corresponding components of the first two nontrivial eigenvectors of the normalized Laplacian for W_M. The marked cities are eight large U.S. hubs (green), three West Coast nonhubs (red), and three East Coast nonhubs (purple). The primary spectral coordinate (left to right) reveals how much of a hub the city is, and the second spectral coordinate (top to bottom) captures west-east geography (13). (D) Embedding of nodes provided by their corresponding components in the first two nontrivial eigenvectors of the standard, edge-based (non–higher-order) normalized Laplacian. This method does not capture the hub and geography found by the higher-order method. For example, Atlanta, the largest hub, is in the center of the embedding, next to Salina, a nonhub.