Local dominance unveils clusters in networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929377447510016 |
|---|---|
| author | Shi, Dingyi Shang, Fan Chen, Bingsheng Expert, Paul Lü, Linyuan Stanley, H. Eugene Lambiotte, Renaud Evans, Tim S. Li, Ruiqi |
| author_facet | Shi, Dingyi Shang, Fan Chen, Bingsheng Expert, Paul Lü, Linyuan Stanley, H. Eugene Lambiotte, Renaud Evans, Tim S. Li, Ruiqi |
| contents | Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_15497 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Local dominance unveils clusters in networks Shi, Dingyi Shang, Fan Chen, Bingsheng Expert, Paul Lü, Linyuan Stanley, H. Eugene Lambiotte, Renaud Evans, Tim S. Li, Ruiqi Physics and Society Data Structures and Algorithms Clusters or communities can provide a coarse-grained description of complex systems at multiple scales, but their detection remains challenging in practice. Community detection methods often define communities as dense subgraphs, or subgraphs with few connections in-between, via concepts such as the cut, conductance, or modularity. Here we consider another perspective built on the notion of local dominance, where low-degree nodes are assigned to the basin of influence of high-degree nodes, and design an efficient algorithm based on local information. Local dominance gives rises to community centers, and uncovers local hierarchies in the network. Community centers have a larger degree than their neighbors and are sufficiently distant from other centers. The strength of our framework is demonstrated on synthesized and empirical networks with ground-truth community labels. The notion of local dominance and the associated asymmetric relations between nodes are not restricted to community detection, and can be utilised in clustering problems, as we illustrate on networks derived from vector data. |
| title | Local dominance unveils clusters in networks |
| topic | Physics and Society Data Structures and Algorithms |
| url | https://arxiv.org/abs/2209.15497 |