Maximum Split Clustering Under Connectivity Constraints View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2003-09

AUTHORS

Pierre Hansen, Brigitte Jaumard, Christophe Meyer, Bruno Simeone, Valeria Doring

ABSTRACT

Consider N entities to be classified (e.g., geographical areas), a matrix of dissimilarities between pairs of entities, a graph H with vertices associated with these entities such that the edges join the vertices corresponding to contiguous entities. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside of it. The single-linkage algorithm (ignoring contiguity between entities) provides partitions into M clusters for which the smallest split of the clusters, called split of the partition, is maximum. We study here the partitioning of the set of entities into M connected clusters for all M between N - 1 and 2 (i.e., clusters such that the subgraphs of H induced by their corresponding sets of entities are connected) with maximum split subject to that condition. We first provide an exact algorithm with a Θ (N2) complexity for the particular case in which H is a tree. This algorithm suggests in turn a first heuristic algorithm for the general problem. Several variants of this heuristic are Also explored. We then present an exact algorithm for the general case based on iterative determination of cocycles of subtrees and on the solution of auxiliary set covering problems. As solution of the latter problems is time-consuming for large instances, we provide another heuristic in which the auxiliary set covering problems are solved approximately. Computational results obtained with the exact and heuristic algorithms are presented on test problems from the literature. More... »

PAGES

143-180

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00357-003-0011-7

DOI

http://dx.doi.org/10.1007/s00357-003-0011-7

DIMENSIONS

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


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": "HEC Montr\u00e9al", 
          "id": "https://www.grid.ac/institutes/grid.256696.8", 
          "name": [
            "\u00c9cole des Hautes \u00c9tudes, Commerciales de Montr\u00e9al, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hansen", 
        "givenName": "Pierre", 
        "id": "sg:person.016640446116.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Montreal", 
          "id": "https://www.grid.ac/institutes/grid.14848.31", 
          "name": [
            "Universit\u00e9 de Montr\u00e9al, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jaumard", 
        "givenName": "Brigitte", 
        "id": "sg:person.07721500366.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721500366.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Montreal", 
          "id": "https://www.grid.ac/institutes/grid.14848.31", 
          "name": [
            "Universit\u00e9 de Montr\u00e9al, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meyer", 
        "givenName": "Christophe", 
        "id": "sg:person.015550437565.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015550437565.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "University of Rome \u201cLa Sapienza\u201d, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simeone", 
        "givenName": "Bruno", 
        "id": "sg:person.012600006066.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Ecole Polytechnique de Montr\u00e9al", 
          "id": "https://www.grid.ac/institutes/grid.183158.6", 
          "name": [
            "\u00c9cole Polytechnique de Montr\u00e9al, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doring", 
        "givenName": "Valeria", 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-09", 
    "datePublishedReg": "2003-09-01", 
    "description": "Consider N entities to be classified (e.g., geographical areas), a matrix of dissimilarities between pairs of entities, a graph H with vertices associated with these entities such that the edges join the vertices corresponding to contiguous entities. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside of it. The single-linkage algorithm (ignoring contiguity between entities) provides partitions into M clusters for which the smallest split of the clusters, called split of the partition, is maximum. We study here the partitioning of the set of entities into M connected clusters for all M between N - 1 and 2 (i.e., clusters such that the subgraphs of H induced by their corresponding sets of entities are connected) with maximum split subject to that condition. We first provide an exact algorithm with a \u0398 (N2) complexity for the particular case in which H is a tree. This algorithm suggests in turn a first heuristic algorithm for the general problem. Several variants of this heuristic are Also explored. We then present an exact algorithm for the general case based on iterative determination of cocycles of subtrees and on the solution of auxiliary set covering problems. As solution of the latter problems is time-consuming for large instances, we provide another heuristic in which the auxiliary set covering problems are solved approximately. Computational results obtained with the exact and heuristic algorithms are presented on test problems from the literature.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00357-003-0011-7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1126672", 
        "issn": [
          "0176-4268", 
          "1432-1343"
        ], 
        "name": "Journal of Classification", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "20"
      }
    ], 
    "name": "Maximum Split Clustering Under Connectivity Constraints", 
    "pagination": "143-180", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a411d079093c9b6c6cd10f9a710ae6ae13a8161c30c5fe2597e35f4ca6a54807"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00357-003-0011-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034442331"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00357-003-0011-7", 
      "https://app.dimensions.ai/details/publication/pub.1034442331"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:26", 
    "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_8672_00000489.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00357-003-0011-7"
  }
]
 

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/s00357-003-0011-7'

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/s00357-003-0011-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00357-003-0011-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00357-003-0011-7'


 

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

97 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00357-003-0011-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N96f529e277e3465bbbe7b2da8b912891
4 schema:datePublished 2003-09
5 schema:datePublishedReg 2003-09-01
6 schema:description Consider N entities to be classified (e.g., geographical areas), a matrix of dissimilarities between pairs of entities, a graph H with vertices associated with these entities such that the edges join the vertices corresponding to contiguous entities. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside of it. The single-linkage algorithm (ignoring contiguity between entities) provides partitions into M clusters for which the smallest split of the clusters, called split of the partition, is maximum. We study here the partitioning of the set of entities into M connected clusters for all M between N - 1 and 2 (i.e., clusters such that the subgraphs of H induced by their corresponding sets of entities are connected) with maximum split subject to that condition. We first provide an exact algorithm with a Θ (N2) complexity for the particular case in which H is a tree. This algorithm suggests in turn a first heuristic algorithm for the general problem. Several variants of this heuristic are Also explored. We then present an exact algorithm for the general case based on iterative determination of cocycles of subtrees and on the solution of auxiliary set covering problems. As solution of the latter problems is time-consuming for large instances, we provide another heuristic in which the auxiliary set covering problems are solved approximately. Computational results obtained with the exact and heuristic algorithms are presented on test problems from the literature.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N85d73f48589c436ebcb0a9dbfc0db511
11 Nc4cec1f6e500402eaf78552c2d5203ef
12 sg:journal.1126672
13 schema:name Maximum Split Clustering Under Connectivity Constraints
14 schema:pagination 143-180
15 schema:productId N02c21e9a0fa546b39342aa66a708034e
16 N05e8412b207442b9af3af8bd603d2046
17 Nc44739fe240c486a8c4cc14aa2c0cf94
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034442331
19 https://doi.org/10.1007/s00357-003-0011-7
20 schema:sdDatePublished 2019-04-10T17:26
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N8108ffa12b074925b7492302f08df36d
23 schema:url http://link.springer.com/10.1007/s00357-003-0011-7
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N02c21e9a0fa546b39342aa66a708034e schema:name dimensions_id
28 schema:value pub.1034442331
29 rdf:type schema:PropertyValue
30 N05e8412b207442b9af3af8bd603d2046 schema:name doi
31 schema:value 10.1007/s00357-003-0011-7
32 rdf:type schema:PropertyValue
33 N235343350f034581ba1a25eb0c1f60a7 schema:affiliation https://www.grid.ac/institutes/grid.183158.6
34 schema:familyName Doring
35 schema:givenName Valeria
36 rdf:type schema:Person
37 N2f23fb9424c94ad5966e31eb4de7e54a rdf:first sg:person.015550437565.39
38 rdf:rest N404fe007e4c44a13b680ec3cb9f1482f
39 N36e58dfa638e4376a9f9b0275d184d82 rdf:first sg:person.07721500366.17
40 rdf:rest N2f23fb9424c94ad5966e31eb4de7e54a
41 N404fe007e4c44a13b680ec3cb9f1482f rdf:first sg:person.012600006066.78
42 rdf:rest N9bd97a8725404c698952e5a1294ac7f2
43 N8108ffa12b074925b7492302f08df36d schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N85d73f48589c436ebcb0a9dbfc0db511 schema:issueNumber 2
46 rdf:type schema:PublicationIssue
47 N96f529e277e3465bbbe7b2da8b912891 rdf:first sg:person.016640446116.30
48 rdf:rest N36e58dfa638e4376a9f9b0275d184d82
49 N9bd97a8725404c698952e5a1294ac7f2 rdf:first N235343350f034581ba1a25eb0c1f60a7
50 rdf:rest rdf:nil
51 Nc44739fe240c486a8c4cc14aa2c0cf94 schema:name readcube_id
52 schema:value a411d079093c9b6c6cd10f9a710ae6ae13a8161c30c5fe2597e35f4ca6a54807
53 rdf:type schema:PropertyValue
54 Nc4cec1f6e500402eaf78552c2d5203ef schema:volumeNumber 20
55 rdf:type schema:PublicationVolume
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
60 schema:name Computation Theory and Mathematics
61 rdf:type schema:DefinedTerm
62 sg:journal.1126672 schema:issn 0176-4268
63 1432-1343
64 schema:name Journal of Classification
65 rdf:type schema:Periodical
66 sg:person.012600006066.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
67 schema:familyName Simeone
68 schema:givenName Bruno
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600006066.78
70 rdf:type schema:Person
71 sg:person.015550437565.39 schema:affiliation https://www.grid.ac/institutes/grid.14848.31
72 schema:familyName Meyer
73 schema:givenName Christophe
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015550437565.39
75 rdf:type schema:Person
76 sg:person.016640446116.30 schema:affiliation https://www.grid.ac/institutes/grid.256696.8
77 schema:familyName Hansen
78 schema:givenName Pierre
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640446116.30
80 rdf:type schema:Person
81 sg:person.07721500366.17 schema:affiliation https://www.grid.ac/institutes/grid.14848.31
82 schema:familyName Jaumard
83 schema:givenName Brigitte
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721500366.17
85 rdf:type schema:Person
86 https://www.grid.ac/institutes/grid.14848.31 schema:alternateName University of Montreal
87 schema:name Université de Montréal, Canada
88 rdf:type schema:Organization
89 https://www.grid.ac/institutes/grid.183158.6 schema:alternateName Ecole Polytechnique de Montréal
90 schema:name École Polytechnique de Montréal, Canada
91 rdf:type schema:Organization
92 https://www.grid.ac/institutes/grid.256696.8 schema:alternateName HEC Montréal
93 schema:name École des Hautes Études, Commerciales de Montréal, Canada
94 rdf:type schema:Organization
95 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
96 schema:name University of Rome “La Sapienza”, Italy
97 rdf:type schema:Organization
 




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


...