26 Dec 2016 | Austin R. Benson, David F. Gleich, Jure Leskovec
The paper introduces a framework for clustering complex networks based on higher-order connectivity patterns, such as network motifs. This framework provides mathematical guarantees on the optimality of clusters and scales to large networks with billions of edges. It reveals higher-order organization in various networks, including neuronal and transportation networks. The framework uses a generalized conductance metric, which measures the ratio of motif cuts to the minimum number of nodes in instances of the motif. The algorithm constructs a motif adjacency matrix, computes the spectral ordering of nodes, and identifies clusters with minimal motif conductance. It is efficient for triangular motifs and can handle networks with billions of edges. The framework can be applied to directed, undirected, and weighted networks, as well as networks with positive and negative edge signs. It also allows for the identification of important motifs for modular organization. The framework extends to other spectral methods and can be used for overlapping clusters. The algorithm is shown to be effective in identifying higher-order modular organization in networks, such as the C. elegans neuronal network, and provides insights into network organization beyond traditional edge-based clustering. The framework is applicable to a wide range of network types, including directed, undirected, weighted, and signed networks.The paper introduces a framework for clustering complex networks based on higher-order connectivity patterns, such as network motifs. This framework provides mathematical guarantees on the optimality of clusters and scales to large networks with billions of edges. It reveals higher-order organization in various networks, including neuronal and transportation networks. The framework uses a generalized conductance metric, which measures the ratio of motif cuts to the minimum number of nodes in instances of the motif. The algorithm constructs a motif adjacency matrix, computes the spectral ordering of nodes, and identifies clusters with minimal motif conductance. It is efficient for triangular motifs and can handle networks with billions of edges. The framework can be applied to directed, undirected, and weighted networks, as well as networks with positive and negative edge signs. It also allows for the identification of important motifs for modular organization. The framework extends to other spectral methods and can be used for overlapping clusters. The algorithm is shown to be effective in identifying higher-order modular organization in networks, such as the C. elegans neuronal network, and provides insights into network organization beyond traditional edge-based clustering. The framework is applicable to a wide range of network types, including directed, undirected, weighted, and signed networks.