On the Maximum Locally Clustered Subgraph and Some Related Problems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Bang Ye Wu

ABSTRACT

Motivated by detecting false friend links in online social networks, we define two optimization problems based on the balance theory for structural transitivity in social networks. We give a polynomial time algorithm for one problem and show the NP-hardness of the other. For the NP-hard problem, we show some polynomial time solvable cases and give a 2-approximation algorithm for a restricted version. We also propose a heuristic algorithm for a more general version of the problem. More... »

PAGES

234-246

Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-642-22615-1
978-3-642-22616-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22616-8_19

DOI

http://dx.doi.org/10.1007/978-3-642-22616-8_19

DIMENSIONS

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


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/None", 
          "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"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Motivated by detecting false friend links in online social networks, we define two optimization problems based on the balance theory for structural transitivity in social networks. We give a polynomial time algorithm for one problem and show the NP-hardness of the other. For the NP-hard problem, we show some polynomial time solvable cases and give a 2-approximation algorithm for a restricted version. We also propose a heuristic algorithm for a more general version of the problem.", 
    "editor": [
      {
        "familyName": "Wang", 
        "givenName": "Weifan", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhu", 
        "givenName": "Xuding", 
        "type": "Person"
      }, 
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22616-8_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22615-1", 
        "978-3-642-22616-8"
      ], 
      "name": "Combinatorial Optimization and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "NP-hard problem", 
      "social networks", 
      "online social networks", 
      "NP-hardness", 
      "polynomial time algorithm", 
      "friend links", 
      "heuristic algorithm", 
      "time algorithm", 
      "optimization problem", 
      "polynomial time solvable cases", 
      "algorithm", 
      "network", 
      "solvable cases", 
      "general version", 
      "related problems", 
      "version", 
      "subgraphs", 
      "balance theory", 
      "link", 
      "transitivity", 
      "theory", 
      "cases", 
      "maximum", 
      "problem", 
      "false friend links", 
      "structural transitivity", 
      "time solvable cases"
    ], 
    "name": "On the Maximum Locally Clustered Subgraph and Some Related Problems", 
    "pagination": "234-246", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019207603"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22616-8_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22616-8_19", 
      "https://app.dimensions.ai/details/publication/pub.1019207603"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:56", 
    "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_12.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22616-8_19"
  }
]
 

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-22616-8_19'

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-22616-8_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22616-8_19'

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-22616-8_19'


 

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

97 TRIPLES      23 PREDICATES      53 URIs      46 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22616-8_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf8747b3ac1504951923d5d266ec0d94c
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Motivated by detecting false friend links in online social networks, we define two optimization problems based on the balance theory for structural transitivity in social networks. We give a polynomial time algorithm for one problem and show the NP-hardness of the other. For the NP-hard problem, we show some polynomial time solvable cases and give a 2-approximation algorithm for a restricted version. We also propose a heuristic algorithm for a more general version of the problem.
7 schema:editor N98bf55ee0cff475ca3b628ce5a5e5c85
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N06eab110a9d147cda8d9fede59f31b7b
12 schema:keywords NP-hard problem
13 NP-hardness
14 algorithm
15 balance theory
16 cases
17 false friend links
18 friend links
19 general version
20 heuristic algorithm
21 link
22 maximum
23 network
24 online social networks
25 optimization problem
26 polynomial time algorithm
27 polynomial time solvable cases
28 problem
29 related problems
30 social networks
31 solvable cases
32 structural transitivity
33 subgraphs
34 theory
35 time algorithm
36 time solvable cases
37 transitivity
38 version
39 schema:name On the Maximum Locally Clustered Subgraph and Some Related Problems
40 schema:pagination 234-246
41 schema:productId Na1ab5d7c54334334be63da9c7d82d546
42 Nfea0e87b84604f3eb0f5d96949575c80
43 schema:publisher N3b132f3296a24904abce5eb42e240777
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019207603
45 https://doi.org/10.1007/978-3-642-22616-8_19
46 schema:sdDatePublished 2021-12-01T19:56
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N45e4460bcb6a4eabaeb32954638ab5e3
49 schema:url https://doi.org/10.1007/978-3-642-22616-8_19
50 sgo:license sg:explorer/license/
51 sgo:sdDataset chapters
52 rdf:type schema:Chapter
53 N06eab110a9d147cda8d9fede59f31b7b schema:isbn 978-3-642-22615-1
54 978-3-642-22616-8
55 schema:name Combinatorial Optimization and Applications
56 rdf:type schema:Book
57 N2167c21d23da4c6680e2e1cc4d0e108a rdf:first N36d8fcb762ab4868bfc1a1498a209d38
58 rdf:rest N9a491c618b3c43eb9c8b51b858b70d6c
59 N36d8fcb762ab4868bfc1a1498a209d38 schema:familyName Zhu
60 schema:givenName Xuding
61 rdf:type schema:Person
62 N3b132f3296a24904abce5eb42e240777 schema:name Springer Nature
63 rdf:type schema:Organisation
64 N45e4460bcb6a4eabaeb32954638ab5e3 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N74b75c09b0e0431fa7fe83f71713d310 schema:familyName Du
67 schema:givenName Ding-Zhu
68 rdf:type schema:Person
69 N98bf55ee0cff475ca3b628ce5a5e5c85 rdf:first Nf9096c22ab9b4adba9207ae9aa1d27d6
70 rdf:rest N2167c21d23da4c6680e2e1cc4d0e108a
71 N9a491c618b3c43eb9c8b51b858b70d6c rdf:first N74b75c09b0e0431fa7fe83f71713d310
72 rdf:rest rdf:nil
73 Na1ab5d7c54334334be63da9c7d82d546 schema:name doi
74 schema:value 10.1007/978-3-642-22616-8_19
75 rdf:type schema:PropertyValue
76 Nf8747b3ac1504951923d5d266ec0d94c rdf:first sg:person.013045767237.23
77 rdf:rest rdf:nil
78 Nf9096c22ab9b4adba9207ae9aa1d27d6 schema:familyName Wang
79 schema:givenName Weifan
80 rdf:type schema:Person
81 Nfea0e87b84604f3eb0f5d96949575c80 schema:name dimensions_id
82 schema:value pub.1019207603
83 rdf:type schema:PropertyValue
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
88 schema:name Computation Theory and Mathematics
89 rdf:type schema:DefinedTerm
90 sg:person.013045767237.23 schema:affiliation grid-institutes:None
91 schema:familyName Wu
92 schema:givenName Bang Ye
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
94 rdf:type schema:Person
95 grid-institutes:None schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan R.O.C.
96 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan R.O.C.
97 rdf:type schema:Organization
 




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


...