Higherorder organization of complex networks
19 Nov 2017Introduction

The paper presents a generalized framework for graph clustering (clusters of network motifs) on the basis of higherorder connectivity patterns.
Approach

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.
Algorithm

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.
Scalability
 Worst case O(m^{1.5}), based on experiments O(m^{1.2}) where m is the number of edges.
Advantages

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 worstcase guarantees for the approximations employed and can be extended to identify higher order modular organization of networks.