Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
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 o...
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Conference item |
| Gepubliceerd in: |
Institute of Electrical and Electronics Engineers
2014
|
| _version_ | 1826271990577627136 |
|---|---|
| author | Beguerisse-Diaz, M Vangelov, B Barahona, M |
| author_facet | Beguerisse-Diaz, M Vangelov, B Barahona, M |
| author_sort | Beguerisse-Diaz, M |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:05:28Z |
| format | Conference item |
| id | oxford-uuid:4ffe7752-4eca-482e-a8e3-ae4f1b69b26c |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:05:28Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | oxford-uuid:4ffe7752-4eca-482e-a8e3-ae4f1b69b26c2022-03-26T16:10:55ZFinding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning TreeConference itemhttp://purl.org/coar/resource_type/c_5794uuid:4ffe7752-4eca-482e-a8e3-ae4f1b69b26cSymplectic Elements at OxfordInstitute of Electrical and Electronics Engineers2014Beguerisse-Diaz, MVangelov, BBarahona, MWe 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. |
| spellingShingle | Beguerisse-Diaz, M Vangelov, B Barahona, M Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title | Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title_full | Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title_fullStr | Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title_full_unstemmed | Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title_short | Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree |
| title_sort | finding role communities in directed networks using role based similarity markov stability and the relaxed minimum spanning tree |
| work_keys_str_mv | AT beguerissediazm findingrolecommunitiesindirectednetworksusingrolebasedsimilaritymarkovstabilityandtherelaxedminimumspanningtree AT vangelovb findingrolecommunitiesindirectednetworksusingrolebasedsimilaritymarkovstabilityandtherelaxedminimumspanningtree AT barahonam findingrolecommunitiesindirectednetworksusingrolebasedsimilaritymarkovstabilityandtherelaxedminimumspanningtree |