Hierarchical Clustering of Trees: Algorithms and Experiments View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Irene Finocchi , Rossella Petreschi

ABSTRACT

We focus on the problem of experimentally evaluating the quality of hierarchical decompositions of trees with respect to criteria relevant in graph drawing applications. We suggest a new family of tree clustering algorithms based on the notion of t-divider and we empirically show the relevance of this concept as a generalization of the ideas of centroid and separator. We compare the t-divider based algorithms with two well-known clustering strategies suitably adapted to work on trees. The experiments analyze how the performances of the algorithms are affected by structural properties of the input tree, such as degree and balancing, and give insight in the choice of the algorithm to be used on a given tree instance. More... »

PAGES

117-131

References to SciGraph publications

  • 2000. Navigating Graph Surfaces in APPROXIMATION AND COMPLEXITY IN NUMERICAL OPTIMIZATION
  • 1999-01-15. A Fully Animated Interactive System for Clustering and Navigating Huge Graphs in GRAPH DRAWING
  • 2000-03-03. Infinite Trees and the Future in GRAPH DRAWING
  • 1999. On the Nature of Structure and Its Identification in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2000-03-03. Partitioning Approach to Visualization of Large Graphs in GRAPH DRAWING
  • 1997. Multilevel visualization of clustered graphs in GRAPH DRAWING
  • 1999-01-15. Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs in GRAPH DRAWING
  • 2001-07-31. On the Validity of Hierarchical Decompositions in COMPUTING AND COMBINATORICS
  • Book

    TITLE

    Algorithm Engineering and Experimentation

    ISBN

    978-3-540-42560-1
    978-3-540-44808-2

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-44808-x_9

    DOI

    http://dx.doi.org/10.1007/3-540-44808-x_9

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1022717534


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Finocchi", 
            "givenName": "Irene", 
            "id": "sg:person.014240412541.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198\u00a0Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4757-3145-3_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000136018", 
              "https://doi.org/10.1007/978-1-4757-3145-3_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jvlc.1999.0143", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001459102"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46648-7_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002005192", 
              "https://doi.org/10.1007/3-540-46648-7_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46648-7_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002005192", 
              "https://doi.org/10.1007/3-540-46648-7_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-37623-2_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010525566", 
              "https://doi.org/10.1007/3-540-37623-2_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-37623-2_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010525566", 
              "https://doi.org/10.1007/3-540-37623-2_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90224-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010675302"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(85)90224-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010675302"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44679-6_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013580317", 
              "https://doi.org/10.1007/3-540-44679-6_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44679-6_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013580317", 
              "https://doi.org/10.1007/3-540-44679-6_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/345513.345353", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025865401"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-62495-3_41", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029153456", 
              "https://doi.org/10.1007/3-540-62495-3_41"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-37623-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030094304", 
              "https://doi.org/10.1007/3-540-37623-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-37623-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030094304", 
              "https://doi.org/10.1007/3-540-37623-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46648-7_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037144695", 
              "https://doi.org/10.1007/3-540-46648-7_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46648-7_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037144695", 
              "https://doi.org/10.1007/3-540-46648-7_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46784-x_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045485392", 
              "https://doi.org/10.1007/3-540-46784-x_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/43.87601", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061174288"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0136016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062839808"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0214055", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841844"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001", 
        "datePublishedReg": "2001-01-01", 
        "description": "We focus on the problem of experimentally evaluating the quality of hierarchical decompositions of trees with respect to criteria relevant in graph drawing applications. We suggest a new family of tree clustering algorithms based on the notion of t-divider and we empirically show the relevance of this concept as a generalization of the ideas of centroid and separator. We compare the t-divider based algorithms with two well-known clustering strategies suitably adapted to work on trees. The experiments analyze how the performances of the algorithms are affected by structural properties of the input tree, such as degree and balancing, and give insight in the choice of the algorithm to be used on a given tree instance.", 
        "editor": [
          {
            "familyName": "Buchsbaum", 
            "givenName": "Adam L.", 
            "type": "Person"
          }, 
          {
            "familyName": "Snoeyink", 
            "givenName": "Jack", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-44808-x_9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-42560-1", 
            "978-3-540-44808-2"
          ], 
          "name": "Algorithm Engineering and Experimentation", 
          "type": "Book"
        }, 
        "name": "Hierarchical Clustering of Trees: Algorithms and Experiments", 
        "pagination": "117-131", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-44808-x_9"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6c3a95e5cf727dce13fa674db2d0f9b0cb02b249cf7c7f8240df502ced62d16a"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022717534"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-44808-x_9", 
          "https://app.dimensions.ai/details/publication/pub.1022717534"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:55", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000257.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-44808-X_9"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-44808-x_9'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-44808-x_9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44808-x_9'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44808-x_9'


     

    This table displays all metadata directly associated to this object as RDF triples.

    127 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-44808-x_9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Neef541020aed430da7f39dc2be8d2e78
    4 schema:citation sg:pub.10.1007/3-540-37623-2_29
    5 sg:pub.10.1007/3-540-37623-2_9
    6 sg:pub.10.1007/3-540-44679-6_40
    7 sg:pub.10.1007/3-540-46648-7_39
    8 sg:pub.10.1007/3-540-46648-7_9
    9 sg:pub.10.1007/3-540-46784-x_13
    10 sg:pub.10.1007/3-540-62495-3_41
    11 sg:pub.10.1007/978-1-4757-3145-3_1
    12 https://doi.org/10.1006/jvlc.1999.0143
    13 https://doi.org/10.1016/0304-3975(85)90224-5
    14 https://doi.org/10.1109/43.87601
    15 https://doi.org/10.1137/0136016
    16 https://doi.org/10.1137/0214055
    17 https://doi.org/10.1145/345513.345353
    18 schema:datePublished 2001
    19 schema:datePublishedReg 2001-01-01
    20 schema:description We focus on the problem of experimentally evaluating the quality of hierarchical decompositions of trees with respect to criteria relevant in graph drawing applications. We suggest a new family of tree clustering algorithms based on the notion of t-divider and we empirically show the relevance of this concept as a generalization of the ideas of centroid and separator. We compare the t-divider based algorithms with two well-known clustering strategies suitably adapted to work on trees. The experiments analyze how the performances of the algorithms are affected by structural properties of the input tree, such as degree and balancing, and give insight in the choice of the algorithm to be used on a given tree instance.
    21 schema:editor N6f70b411568e49ea9d89bf51747088d0
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N2b5eb7a2f4a246d488b3a4b13b1f2d18
    26 schema:name Hierarchical Clustering of Trees: Algorithms and Experiments
    27 schema:pagination 117-131
    28 schema:productId N19901d0145a04287a64aa5a39753e625
    29 N75bdef1f5187417ca44954441a1f87bd
    30 Nf010304ea5b74a248a7f340d7c4de280
    31 schema:publisher N194f4ec9515e48b090d13bda1ff4e97d
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022717534
    33 https://doi.org/10.1007/3-540-44808-x_9
    34 schema:sdDatePublished 2019-04-15T22:55
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N2a62d1ba470e4b73965bc9d1ea7fd3d8
    37 schema:url http://link.springer.com/10.1007/3-540-44808-X_9
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N194f4ec9515e48b090d13bda1ff4e97d schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N19901d0145a04287a64aa5a39753e625 schema:name readcube_id
    45 schema:value 6c3a95e5cf727dce13fa674db2d0f9b0cb02b249cf7c7f8240df502ced62d16a
    46 rdf:type schema:PropertyValue
    47 N2a62d1ba470e4b73965bc9d1ea7fd3d8 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N2b5eb7a2f4a246d488b3a4b13b1f2d18 schema:isbn 978-3-540-42560-1
    50 978-3-540-44808-2
    51 schema:name Algorithm Engineering and Experimentation
    52 rdf:type schema:Book
    53 N34e10244aa9840b0909d49482b424697 rdf:first Ned478218659c4b98acb7cb0a5f2af2cf
    54 rdf:rest rdf:nil
    55 N6f70b411568e49ea9d89bf51747088d0 rdf:first N99caf4e65b914cd29d1637ccefc6deed
    56 rdf:rest N34e10244aa9840b0909d49482b424697
    57 N75bdef1f5187417ca44954441a1f87bd schema:name doi
    58 schema:value 10.1007/3-540-44808-x_9
    59 rdf:type schema:PropertyValue
    60 N99caf4e65b914cd29d1637ccefc6deed schema:familyName Buchsbaum
    61 schema:givenName Adam L.
    62 rdf:type schema:Person
    63 Na7fb8d01d552404088305728f5a6fbd3 rdf:first sg:person.011402427702.78
    64 rdf:rest rdf:nil
    65 Ned478218659c4b98acb7cb0a5f2af2cf schema:familyName Snoeyink
    66 schema:givenName Jack
    67 rdf:type schema:Person
    68 Neef541020aed430da7f39dc2be8d2e78 rdf:first sg:person.014240412541.72
    69 rdf:rest Na7fb8d01d552404088305728f5a6fbd3
    70 Nf010304ea5b74a248a7f340d7c4de280 schema:name dimensions_id
    71 schema:value pub.1022717534
    72 rdf:type schema:PropertyValue
    73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Information and Computing Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Computation Theory and Mathematics
    78 rdf:type schema:DefinedTerm
    79 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    80 schema:familyName Petreschi
    81 schema:givenName Rossella
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    83 rdf:type schema:Person
    84 sg:person.014240412541.72 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    85 schema:familyName Finocchi
    86 schema:givenName Irene
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
    88 rdf:type schema:Person
    89 sg:pub.10.1007/3-540-37623-2_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010525566
    90 https://doi.org/10.1007/3-540-37623-2_29
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/3-540-37623-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030094304
    93 https://doi.org/10.1007/3-540-37623-2_9
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/3-540-44679-6_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013580317
    96 https://doi.org/10.1007/3-540-44679-6_40
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/3-540-46648-7_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002005192
    99 https://doi.org/10.1007/3-540-46648-7_39
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/3-540-46648-7_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037144695
    102 https://doi.org/10.1007/3-540-46648-7_9
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/3-540-46784-x_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045485392
    105 https://doi.org/10.1007/3-540-46784-x_13
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/3-540-62495-3_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029153456
    108 https://doi.org/10.1007/3-540-62495-3_41
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-1-4757-3145-3_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000136018
    111 https://doi.org/10.1007/978-1-4757-3145-3_1
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1006/jvlc.1999.0143 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001459102
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/0304-3975(85)90224-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010675302
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1109/43.87601 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061174288
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1137/0136016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839808
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1137/0214055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841844
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1145/345513.345353 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025865401
    124 rdf:type schema:CreativeWork
    125 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    126 schema:name Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy
    127 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...