26 Dec 2016 | Austin R. Benson, David F. Gleich, Jure Leskovec
The paper introduces a generalized framework for clustering networks based on higher-order connectivity patterns, specifically focusing on network motifs. The framework provides mathematical guarantees on the optimality of the clusters and scales to networks with billions of edges. The authors demonstrate the effectiveness of the framework by revealing higher-order organization in various networks, including neuronal networks and transportation networks. The framework is based on a motif conductance measure, which is a generalization of the conductance metric in spectral graph theory. The algorithm efficiently identifies clusters by forming a motif adjacency matrix and computing an eigenvector of the normalized motif Laplacian matrix. The method is applicable to directed, undirected, weighted, and signed networks, and can be used to identify motifs that are important for the modular organization of a network. The paper also discusses the theoretical foundations, computational complexity, and extensions of the method to other types of motifs and network structures.The paper introduces a generalized framework for clustering networks based on higher-order connectivity patterns, specifically focusing on network motifs. The framework provides mathematical guarantees on the optimality of the clusters and scales to networks with billions of edges. The authors demonstrate the effectiveness of the framework by revealing higher-order organization in various networks, including neuronal networks and transportation networks. The framework is based on a motif conductance measure, which is a generalization of the conductance metric in spectral graph theory. The algorithm efficiently identifies clusters by forming a motif adjacency matrix and computing an eigenvector of the normalized motif Laplacian matrix. The method is applicable to directed, undirected, weighted, and signed networks, and can be used to identify motifs that are important for the modular organization of a network. The paper also discusses the theoretical foundations, computational complexity, and extensions of the method to other types of motifs and network structures.