Higher-order organization of complex networks
19 Nov 2017Introduction
-
The paper presents a generalized framework for graph clustering (clusters of network motifs) on the basis of higher-order 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 cutM(S, S’) / min[volM(S), volM(S’)] where S’ is complement of S, cutM(S, S’) = number of instances of M which have atleast one node from both S and S’ and volM(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 WM where WM(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(m1.5), based on experiments O(m1.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 worst-case guarantees for the approximations employed and can be extended to identify higher order modular organization of networks.