Local dominance unveils clusters in networks
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...
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Nature Research
2024
|
| _version_ | 1826313057174814720 |
|---|---|
| author | Shi, D Shang, F Chen, B Expert, P Lü, L Stanley, HE Lambiotte, R Evans, TS Li, R |
| author_facet | Shi, D Shang, F Chen, B Expert, P Lü, L Stanley, HE Lambiotte, R Evans, TS Li, R |
| author_sort | Shi, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-09-25T04:06:51Z |
| format | Journal article |
| id | oxford-uuid:4cbd07d5-764b-4fc3-ae44-78dbaa53daf9 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:06:51Z |
| publishDate | 2024 |
| publisher | Nature Research |
| record_format | dspace |
| spelling | oxford-uuid:4cbd07d5-764b-4fc3-ae44-78dbaa53daf92024-05-31T20:19:44ZLocal dominance unveils clusters in networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4cbd07d5-764b-4fc3-ae44-78dbaa53daf9EnglishJisc Publications RouterNature Research2024Shi, DShang, FChen, BExpert, PLü, LStanley, HELambiotte, REvans, TSLi, RClusters 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. |
| spellingShingle | Shi, D Shang, F Chen, B Expert, P Lü, L Stanley, HE Lambiotte, R Evans, TS Li, R Local dominance unveils clusters in networks |
| title | Local dominance unveils clusters in networks |
| title_full | Local dominance unveils clusters in networks |
| title_fullStr | Local dominance unveils clusters in networks |
| title_full_unstemmed | Local dominance unveils clusters in networks |
| title_short | Local dominance unveils clusters in networks |
| title_sort | local dominance unveils clusters in networks |
| work_keys_str_mv | AT shid localdominanceunveilsclustersinnetworks AT shangf localdominanceunveilsclustersinnetworks AT chenb localdominanceunveilsclustersinnetworks AT expertp localdominanceunveilsclustersinnetworks AT lul localdominanceunveilsclustersinnetworks AT stanleyhe localdominanceunveilsclustersinnetworks AT lambiotter localdominanceunveilsclustersinnetworks AT evansts localdominanceunveilsclustersinnetworks AT lir localdominanceunveilsclustersinnetworks |