Table of contents

Higher-order organization of complex networks[ Edit ]

- 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*where_{M}(S, S’) / min[vol_{M}(S), vol_{M}(S’)]*S’*is complement of*S*,*cut*= number of instances of M which have atleast one node from both_{M}(S, S’)*S*and*S’*and*vol*= Number of nodes in instances of M that belong only to S._{M}(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*, based on experiments^{1.5})*O(m*where^{1.2})*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.

Read more…(324 words)

About the contributor:

Shagun SodhaniAnalytics and Data Science team @ Adobe Systems

100%

Loading…

Join the discussion. Add a reply…

Post

Table of contents

- Introduction
- Approach
- Algorithm
- Scalability
- Advantages

Contributor

Shagun SodhaniAnalytics and Data Science team @ Adobe Systems

100%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.