Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
arXiv:1309.1795 · doi:10.1109/GlobalSIP.2013.6737046
Abstract
We present a framework to cluster nodes in directed networks according to their roles by combining Role-Based Similarity (RBS) and Markov Stability, two techniques based on flows. First we compute the RBS matrix, which contains the pairwise similarities between nodes according to the scaled number of in- and out-directed paths of different lengths. The weighted RBS similarity matrix is then transformed into an undirected similarity network using the Relaxed Minimum-Spanning Tree (RMST) algorithm, which uses the geometric structure of the RBS matrix to unblur the network, such that edges between nodes with high, direct RBS are preserved. Finally, we partition the RMST similarity network into role-communities of nodes at all scales using Markov Stability to find a robust set of roles in the network. We showcase our framework through a biological and a man-made network.
arXiv comment4 pages, 2 figures
References in corpus (5)
Cited by in corpus (10)
- Flow-based network analysis of the Caenorhabditis elegans connectome
- Graph-based data clustering via multiscale community detection
- Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
- From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
- Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs
- Geometric graphs from data to aid classification tasks with graph convolutional networks
- Tensor clustering with algebraic constraints gives interpretable groups of crosstalk mechanisms in breast cancer
- Detecting highly cyclic structure with complex eigenpairs
- Low-rank Similarity Measure for Role Model Extraction
- Multiscale methods for signal selection in single-cell data