Higher-order organization of complex networks

19 Nov 2017

Introduction

The paper presents a generalized framework for graph clustering (clusters of network motifs) on the basis of higher-order connectivity patterns.
Link to the paper

Given a motif M, the framework aims to find a cluster of the set of nodes S such that nodes of S participate in many instances of M and avoid cutting instances of M (that is only a subset of nodes in instances of M appears in S).
Mathematically, the aim is to minimise the motif conductance metric given as cut_M(S, S’) / min[vol_M(S), vol_M(S’)] where S’ is complement of S, cut_M(S, S’) = number of instances of M which have atleast one node from both S and S’ and vol_M(S) = Number of nodes in instances of M that belong only to S.
Solving the above equation is computationally infeasible and an approximate solution is proposed using eigenvalues and matrices.
The approximate solution is easy to implement, efficient and guaranteed to find clusters that are at most a quadratic factor away from the optimal.

Given the network and motif M, form a motif adjacency matrix W_M where W_M(i, j) is the number of instances of M that contains i and j.
Compute spectral ordering of the nodes from normalized motif laplacian matrix.
Compute prefix set of spectral ordering with small motif conductance.

Worst case O(m^1.5), based on experiments O(m^1.2) where m is the number of edges.

Applicable to directed, undirected and weighted graphs (allows for negative edge weights as well).
In case the motif is not known beforehand, the framework can be used to compute significant motifs.
The proposed framework unifies the two fundamental tools of network science (motif analysis and network partitioning) along with some worst-case guarantees for the approximations employed and can be extended to identify higher order modular organization of networks.