Balancing a Complete Signed Graph by Editing Edges and Deleting Nodes View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Bang Ye Wu , Jia-Fen Chen

ABSTRACT

A signed graph is a simple undirected graph in which each edge is either positive or negative. A signed graph is balanced if every cycle has even numbers of negative edges. In this paper we study the problem of balancing a complete signed graph by minimum editing cost, in which the editing operations includes inserting edges, deleting edges, and deleting nodes. We design a branch-and-bound algorithm, as well as a heuristic algorithm. By experimental results we show that the branch-and-bound algorithm is much efficient than a trivial one and the heuristic algorithm performs well. More... »

PAGES

79-88

Book

TITLE

Advances in Intelligent Systems and Applications - Volume 1

ISBN

978-3-642-35451-9
978-3-642-35452-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_10

DOI

http://dx.doi.org/10.1007/978-3-642-35452-6_10

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Jia-Fen", 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "A signed graph is a simple undirected graph in which each edge is either positive or negative. A signed graph is balanced if every cycle has even numbers of negative edges. In this paper we study the problem of balancing a complete signed graph by minimum editing cost, in which the editing operations includes inserting edges, deleting edges, and deleting nodes. We design a branch-and-bound algorithm, as well as a heuristic algorithm. By experimental results we show that the branch-and-bound algorithm is much efficient than a trivial one and the heuristic algorithm performs well.", 
    "editor": [
      {
        "familyName": "Chang", 
        "givenName": "Ruay-Shiung", 
        "type": "Person"
      }, 
      {
        "familyName": "Jain", 
        "givenName": "Lakhmi C.", 
        "type": "Person"
      }, 
      {
        "familyName": "Peng", 
        "givenName": "Sheng-Lung", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-35452-6_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-35451-9", 
        "978-3-642-35452-6"
      ], 
      "name": "Advances in Intelligent Systems and Applications - Volume 1", 
      "type": "Book"
    }, 
    "keywords": [
      "heuristic algorithm", 
      "graph", 
      "undirected graph", 
      "negative edges", 
      "nodes", 
      "algorithm", 
      "experimental results", 
      "simple undirected graph", 
      "edge", 
      "trivial one", 
      "cost", 
      "operation", 
      "number", 
      "branches", 
      "results", 
      "one", 
      "cycle", 
      "paper", 
      "problem", 
      "minimum editing cost", 
      "editing cost", 
      "Editing Edges"
    ], 
    "name": "Balancing a Complete Signed Graph by Editing Edges and Deleting Nodes", 
    "pagination": "79-88", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029877210"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-35452-6_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-35452-6_10", 
      "https://app.dimensions.ai/details/publication/pub.1029877210"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_336.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-35452-6_10"
  }
]
 

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/978-3-642-35452-6_10'

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/978-3-642-35452-6_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_10'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-35452-6_10'


 

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

98 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-35452-6_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4625a2fc4b614142b0d20ac2e687d3ea
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description A signed graph is a simple undirected graph in which each edge is either positive or negative. A signed graph is balanced if every cycle has even numbers of negative edges. In this paper we study the problem of balancing a complete signed graph by minimum editing cost, in which the editing operations includes inserting edges, deleting edges, and deleting nodes. We design a branch-and-bound algorithm, as well as a heuristic algorithm. By experimental results we show that the branch-and-bound algorithm is much efficient than a trivial one and the heuristic algorithm performs well.
7 schema:editor Nec0d416e6e174fa28beaf0d6d130da9c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N8190c77ecb56455fa53e92897cc553bd
12 schema:keywords Editing Edges
13 algorithm
14 branches
15 cost
16 cycle
17 edge
18 editing cost
19 experimental results
20 graph
21 heuristic algorithm
22 minimum editing cost
23 negative edges
24 nodes
25 number
26 one
27 operation
28 paper
29 problem
30 results
31 simple undirected graph
32 trivial one
33 undirected graph
34 schema:name Balancing a Complete Signed Graph by Editing Edges and Deleting Nodes
35 schema:pagination 79-88
36 schema:productId N013ae39a02694b3987d330d14635a6f8
37 Naed11f005f16413489cc338092ce82ac
38 schema:publisher Nb2457908a5e04bc48cf6addd9be83c9f
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029877210
40 https://doi.org/10.1007/978-3-642-35452-6_10
41 schema:sdDatePublished 2021-12-01T20:05
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N7211da50d480494ca0f2eec5000560ca
44 schema:url https://doi.org/10.1007/978-3-642-35452-6_10
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N013ae39a02694b3987d330d14635a6f8 schema:name dimensions_id
49 schema:value pub.1029877210
50 rdf:type schema:PropertyValue
51 N4625a2fc4b614142b0d20ac2e687d3ea rdf:first sg:person.013045767237.23
52 rdf:rest N709ee07ccd594fc6a9744ee56a986a99
53 N50a14a3222114666b2817b8286ade999 rdf:first Nb1f767beff994e43985bc926ad4ee90e
54 rdf:rest Nc7ed1b1da9744710974990ea86eda5e0
55 N709ee07ccd594fc6a9744ee56a986a99 rdf:first Nd19d9f10a7c245a3836270a9d6035936
56 rdf:rest rdf:nil
57 N7211da50d480494ca0f2eec5000560ca schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N7422a105fe2f4ffc8bdcd59469ca1427 schema:familyName Chang
60 schema:givenName Ruay-Shiung
61 rdf:type schema:Person
62 N8190c77ecb56455fa53e92897cc553bd schema:isbn 978-3-642-35451-9
63 978-3-642-35452-6
64 schema:name Advances in Intelligent Systems and Applications - Volume 1
65 rdf:type schema:Book
66 N94d4ca7a747243f2ad247fa65f125586 schema:familyName Peng
67 schema:givenName Sheng-Lung
68 rdf:type schema:Person
69 Naed11f005f16413489cc338092ce82ac schema:name doi
70 schema:value 10.1007/978-3-642-35452-6_10
71 rdf:type schema:PropertyValue
72 Nb1f767beff994e43985bc926ad4ee90e schema:familyName Jain
73 schema:givenName Lakhmi C.
74 rdf:type schema:Person
75 Nb2457908a5e04bc48cf6addd9be83c9f schema:name Springer Nature
76 rdf:type schema:Organisation
77 Nc7ed1b1da9744710974990ea86eda5e0 rdf:first N94d4ca7a747243f2ad247fa65f125586
78 rdf:rest rdf:nil
79 Nd19d9f10a7c245a3836270a9d6035936 schema:affiliation grid-institutes:grid.412047.4
80 schema:familyName Chen
81 schema:givenName Jia-Fen
82 rdf:type schema:Person
83 Nec0d416e6e174fa28beaf0d6d130da9c rdf:first N7422a105fe2f4ffc8bdcd59469ca1427
84 rdf:rest N50a14a3222114666b2817b8286ade999
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
89 schema:name Computation Theory and Mathematics
90 rdf:type schema:DefinedTerm
91 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
92 schema:familyName Wu
93 schema:givenName Bang Ye
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
95 rdf:type schema:Person
96 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
97 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, R.O.C.
98 rdf:type schema:Organization
 




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


...