Hierarchical clustering of asymmetric networks
This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter. Our constructio...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer-Verlag
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115058 |
| _version_ | 1826213521542610944 |
|---|---|
| author | Carlsson, Gunnar Mémoli, Facundo Ribeiro, Alejandro Segarra, Santiago M |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Carlsson, Gunnar Mémoli, Facundo Ribeiro, Alejandro Segarra, Santiago M |
| author_sort | Carlsson, Gunnar |
| collection | MIT |
| description | This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter. Our construction of hierarchical clustering methods is built around the concept of admissible methods, which are those that abide by the axioms of value—nodes in a network with two nodes are clustered together at the maximum of the two dissimilarities between them—and transformation—when dissimilarities are reduced, the network may become more clustered but not less. Two particular methods, termed reciprocal and nonreciprocal clustering, are shown to provide upper and lower bounds in the space of admissible methods. Furthermore, alternative clustering methodologies and axioms are considered. In particular, modifying the axiom of value such that clustering in two-node networks occurs at the minimum of the two dissimilarities entails the existence of a unique admissible clustering method. Finally, the developed clustering methods are implemented to analyze the internal migration in the United States. Keywords: Hierarchical clustering; Asymmetric network; Directed graph; Axiomatic construction; Reciprocal clustering; Nonreciprocal clustering |
| first_indexed | 2024-09-23T15:50:33Z |
| format | Article |
| id | mit-1721.1/115058 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:50:33Z |
| publishDate | 2018 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1150582022-09-29T16:31:18Z Hierarchical clustering of asymmetric networks Carlsson, Gunnar Mémoli, Facundo Ribeiro, Alejandro Segarra, Santiago M Massachusetts Institute of Technology. Institute for Data, Systems, and Society Segarra, Santiago M This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter. Our construction of hierarchical clustering methods is built around the concept of admissible methods, which are those that abide by the axioms of value—nodes in a network with two nodes are clustered together at the maximum of the two dissimilarities between them—and transformation—when dissimilarities are reduced, the network may become more clustered but not less. Two particular methods, termed reciprocal and nonreciprocal clustering, are shown to provide upper and lower bounds in the space of admissible methods. Furthermore, alternative clustering methodologies and axioms are considered. In particular, modifying the axiom of value such that clustering in two-node networks occurs at the minimum of the two dissimilarities entails the existence of a unique admissible clustering method. Finally, the developed clustering methods are implemented to analyze the internal migration in the United States. Keywords: Hierarchical clustering; Asymmetric network; Directed graph; Axiomatic construction; Reciprocal clustering; Nonreciprocal clustering National Science Foundation (U.S.) (Grant CCF-1217963) National Science Foundation (U.S.) (Grant CCF-0952867) National Science Foundation (U.S.) (Grant IIS-1422400) National Science Foundation (U.S.) (Grant CCF-1526513) National Science Foundation (U.S.) (Grant DMS-0905823) National Science Foundation (U.S.) (Grant DMS-0406992) United States. Air Force Office of Scientific Research (Grant FA9550-09-0-1-0531) United States. Air Force Office of Scientific Research (Grant FA9550-09-1-0643) 2018-04-27T19:03:02Z 2018-09-02T05:00:05Z 2017-11 2017-10 2018-03-03T04:48:48Z Article http://purl.org/eprint/type/JournalArticle 1862-5347 1862-5355 http://hdl.handle.net/1721.1/115058 Carlsson, Gunnar et al. “Hierarchical Clustering of Asymmetric Networks.” Advances in Data Analysis and Classification 12, 1 (November 2017): 65–105 © Springer-Verlag en http://dx.doi.org/10.1007/s11634-017-0299-5 Advances in Data Analysis and Classification Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag GmbH Germany application/pdf Springer-Verlag Springer Berlin Heidelberg |
| spellingShingle | Carlsson, Gunnar Mémoli, Facundo Ribeiro, Alejandro Segarra, Santiago M Hierarchical clustering of asymmetric networks |
| title | Hierarchical clustering of asymmetric networks |
| title_full | Hierarchical clustering of asymmetric networks |
| title_fullStr | Hierarchical clustering of asymmetric networks |
| title_full_unstemmed | Hierarchical clustering of asymmetric networks |
| title_short | Hierarchical clustering of asymmetric networks |
| title_sort | hierarchical clustering of asymmetric networks |
| url | http://hdl.handle.net/1721.1/115058 |
| work_keys_str_mv | AT carlssongunnar hierarchicalclusteringofasymmetricnetworks AT memolifacundo hierarchicalclusteringofasymmetricnetworks AT ribeiroalejandro hierarchicalclusteringofasymmetricnetworks AT segarrasantiagom hierarchicalclusteringofasymmetricnetworks |