Vulnerability of clustering under node failure in complex networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-03-01

AUTHORS

Alan Kuhnle, Nam P. Nguyen, Thang N. Dinh, My T. Thai

ABSTRACT

Robustness in response to unexpected events is always desirable for real-world networks. To improve the robustness of any networked system, it is important to analyze vulnerability to external perturbation such as random failures or adversarial attacks occurring to elements of the network. In this paper, we study an emerging problem in assessing the robustness of complex networks: the vulnerability of the clustering of the network to the failure of network elements. Specifically, we identify vertices whose failures will critically damage the network by degrading its clustering, evaluated through the average clustering coefficient. This problem is important because any significant change made to the clustering, resulting from element-wise failures, could degrade network performance such as the ability for information to propagate in a social network. We formulate this vulnerability analysis as an optimization problem, prove its NP-completeness and non-monotonicity, and offer two algorithms to identify the vertices most important to clustering. Finally, we conduct comprehensive experiments in synthesized social networks generated by various well-known models as well as traces of real social networks. The empirical results over other competitive strategies show the efficacy of our proposed algorithms. More... »

PAGES

8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s13278-017-0426-5

DOI

http://dx.doi.org/10.1007/s13278-017-0426-5

DIMENSIONS

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


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"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA", 
          "id": "http://www.grid.ac/institutes/grid.15276.37", 
          "name": [
            "Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kuhnle", 
        "givenName": "Alan", 
        "id": "sg:person.014363247535.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014363247535.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer and Information Sciences, Towson University, Towson, MD, USA", 
          "id": "http://www.grid.ac/institutes/grid.265122.0", 
          "name": [
            "Department of Computer and Information Sciences, Towson University, Towson, MD, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nguyen", 
        "givenName": "Nam P.", 
        "id": "sg:person.01324434022.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01324434022.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Virginia Commonwealth University, Richmond, VA, USA", 
          "id": "http://www.grid.ac/institutes/grid.224260.0", 
          "name": [
            "Department of Computer Science, Virginia Commonwealth University, Richmond, VA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dinh", 
        "givenName": "Thang N.", 
        "id": "sg:person.014265045367.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014265045367.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA", 
          "id": "http://www.grid.ac/institutes/grid.15276.37", 
          "name": [
            "Division of Algorithms and Technologies for Networks Analysis, Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam", 
            "Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Thai", 
        "givenName": "My T.", 
        "id": "sg:person.014521212361.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014521212361.49"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4614-0857-4_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038948493", 
          "https://doi.org/10.1007/978-1-4614-0857-4_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11427186_54", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013907940", 
          "https://doi.org/10.1007/11427186_54"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/35019019", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008269744", 
          "https://doi.org/10.1038/35019019"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/30918", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041985305", 
          "https://doi.org/10.1038/30918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2458-13-784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053327670", 
          "https://doi.org/10.1186/1471-2458-13-784"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10878-014-9730-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005517416", 
          "https://doi.org/10.1007/s10878-014-9730-4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-03-01", 
    "datePublishedReg": "2017-03-01", 
    "description": "Robustness in response to unexpected events is always desirable for real-world networks. To improve the robustness of any networked system, it is important to analyze vulnerability to external perturbation such as random failures or adversarial attacks occurring to elements of the network. In this paper, we study an emerging problem in assessing the robustness of complex networks: the vulnerability of the clustering of the network to the failure of network elements. Specifically, we identify vertices whose failures will critically damage the network by degrading its clustering, evaluated through the average clustering coefficient. This problem is important because any significant change made to the clustering, resulting from element-wise failures, could degrade network performance such as the ability for information to propagate in a social network. We formulate this vulnerability analysis as an optimization problem, prove its NP-completeness and non-monotonicity, and offer two algorithms to identify the vertices most important to clustering. Finally, we conduct comprehensive experiments in synthesized social networks generated by various well-known models as well as traces of real social networks. The empirical results over other competitive strategies show the efficacy of our proposed algorithms.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s13278-017-0426-5", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3850833", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1048971", 
        "issn": [
          "1869-5450", 
          "1869-5469"
        ], 
        "name": "Social Network Analysis and Mining", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "keywords": [
      "social networks", 
      "real social networks", 
      "synthesized social networks", 
      "real-world networks", 
      "complex networks", 
      "adversarial attacks", 
      "comprehensive experiments", 
      "network performance", 
      "node failures", 
      "network elements", 
      "NP-completeness", 
      "networked systems", 
      "optimization problem", 
      "network", 
      "vulnerability analysis", 
      "average clustering coefficient", 
      "clustering", 
      "unexpected events", 
      "algorithm", 
      "clustering coefficient", 
      "random failures", 
      "robustness", 
      "empirical results", 
      "vulnerability", 
      "attacks", 
      "vertices", 
      "information", 
      "competitive strategy", 
      "performance", 
      "traces", 
      "system", 
      "model", 
      "experiments", 
      "elements", 
      "strategies", 
      "ability", 
      "results", 
      "failure", 
      "external perturbations", 
      "analysis", 
      "events", 
      "coefficient", 
      "perturbations", 
      "changes", 
      "efficacy", 
      "response", 
      "significant changes", 
      "problem", 
      "paper"
    ], 
    "name": "Vulnerability of clustering under node failure in complex networks", 
    "pagination": "8", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084036815"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s13278-017-0426-5"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s13278-017-0426-5", 
      "https://app.dimensions.ai/details/publication/pub.1084036815"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T21:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_745.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s13278-017-0426-5"
  }
]
 

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/s13278-017-0426-5'

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/s13278-017-0426-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s13278-017-0426-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s13278-017-0426-5'


 

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

164 TRIPLES      21 PREDICATES      80 URIs      65 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s13278-017-0426-5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0806
4 schema:author Na5a28840121246719d3839521bf08238
5 schema:citation sg:pub.10.1007/11427186_54
6 sg:pub.10.1007/978-1-4614-0857-4_1
7 sg:pub.10.1007/s10878-014-9730-4
8 sg:pub.10.1038/30918
9 sg:pub.10.1038/35019019
10 sg:pub.10.1186/1471-2458-13-784
11 schema:datePublished 2017-03-01
12 schema:datePublishedReg 2017-03-01
13 schema:description Robustness in response to unexpected events is always desirable for real-world networks. To improve the robustness of any networked system, it is important to analyze vulnerability to external perturbation such as random failures or adversarial attacks occurring to elements of the network. In this paper, we study an emerging problem in assessing the robustness of complex networks: the vulnerability of the clustering of the network to the failure of network elements. Specifically, we identify vertices whose failures will critically damage the network by degrading its clustering, evaluated through the average clustering coefficient. This problem is important because any significant change made to the clustering, resulting from element-wise failures, could degrade network performance such as the ability for information to propagate in a social network. We formulate this vulnerability analysis as an optimization problem, prove its NP-completeness and non-monotonicity, and offer two algorithms to identify the vertices most important to clustering. Finally, we conduct comprehensive experiments in synthesized social networks generated by various well-known models as well as traces of real social networks. The empirical results over other competitive strategies show the efficacy of our proposed algorithms.
14 schema:genre article
15 schema:isAccessibleForFree true
16 schema:isPartOf Nd7e45c84b78c4ce8a4fcef4fc421fe47
17 Nd9885e2a5e6e462eb03370d983c4bc26
18 sg:journal.1048971
19 schema:keywords NP-completeness
20 ability
21 adversarial attacks
22 algorithm
23 analysis
24 attacks
25 average clustering coefficient
26 changes
27 clustering
28 clustering coefficient
29 coefficient
30 competitive strategy
31 complex networks
32 comprehensive experiments
33 efficacy
34 elements
35 empirical results
36 events
37 experiments
38 external perturbations
39 failure
40 information
41 model
42 network
43 network elements
44 network performance
45 networked systems
46 node failures
47 optimization problem
48 paper
49 performance
50 perturbations
51 problem
52 random failures
53 real social networks
54 real-world networks
55 response
56 results
57 robustness
58 significant changes
59 social networks
60 strategies
61 synthesized social networks
62 system
63 traces
64 unexpected events
65 vertices
66 vulnerability
67 vulnerability analysis
68 schema:name Vulnerability of clustering under node failure in complex networks
69 schema:pagination 8
70 schema:productId N0edb14380d1e4fe4a701a7ff1f6cbaea
71 N18f1759af0db4816a1734695bd6b0ab6
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084036815
73 https://doi.org/10.1007/s13278-017-0426-5
74 schema:sdDatePublished 2022-11-24T21:02
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher N2f416de74c22470f89a45505a53c2a4b
77 schema:url https://doi.org/10.1007/s13278-017-0426-5
78 sgo:license sg:explorer/license/
79 sgo:sdDataset articles
80 rdf:type schema:ScholarlyArticle
81 N0edb14380d1e4fe4a701a7ff1f6cbaea schema:name dimensions_id
82 schema:value pub.1084036815
83 rdf:type schema:PropertyValue
84 N18f1759af0db4816a1734695bd6b0ab6 schema:name doi
85 schema:value 10.1007/s13278-017-0426-5
86 rdf:type schema:PropertyValue
87 N2f416de74c22470f89a45505a53c2a4b schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 N4101968286ef436ea3cf8eea37a5e3a3 rdf:first sg:person.014521212361.49
90 rdf:rest rdf:nil
91 Na5a28840121246719d3839521bf08238 rdf:first sg:person.014363247535.46
92 rdf:rest Na7eff0ce60ef437685a75012303a8d7f
93 Na7eff0ce60ef437685a75012303a8d7f rdf:first sg:person.01324434022.76
94 rdf:rest Ne57208c8fd1d499e81b11b1927e5257a
95 Nd7e45c84b78c4ce8a4fcef4fc421fe47 schema:issueNumber 1
96 rdf:type schema:PublicationIssue
97 Nd9885e2a5e6e462eb03370d983c4bc26 schema:volumeNumber 7
98 rdf:type schema:PublicationVolume
99 Ne57208c8fd1d499e81b11b1927e5257a rdf:first sg:person.014265045367.83
100 rdf:rest N4101968286ef436ea3cf8eea37a5e3a3
101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
102 schema:name Information and Computing Sciences
103 rdf:type schema:DefinedTerm
104 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
105 schema:name Computation Theory and Mathematics
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
108 schema:name Information Systems
109 rdf:type schema:DefinedTerm
110 sg:grant.3850833 http://pending.schema.org/fundedItem sg:pub.10.1007/s13278-017-0426-5
111 rdf:type schema:MonetaryGrant
112 sg:journal.1048971 schema:issn 1869-5450
113 1869-5469
114 schema:name Social Network Analysis and Mining
115 schema:publisher Springer Nature
116 rdf:type schema:Periodical
117 sg:person.01324434022.76 schema:affiliation grid-institutes:grid.265122.0
118 schema:familyName Nguyen
119 schema:givenName Nam P.
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01324434022.76
121 rdf:type schema:Person
122 sg:person.014265045367.83 schema:affiliation grid-institutes:grid.224260.0
123 schema:familyName Dinh
124 schema:givenName Thang N.
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014265045367.83
126 rdf:type schema:Person
127 sg:person.014363247535.46 schema:affiliation grid-institutes:grid.15276.37
128 schema:familyName Kuhnle
129 schema:givenName Alan
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014363247535.46
131 rdf:type schema:Person
132 sg:person.014521212361.49 schema:affiliation grid-institutes:grid.15276.37
133 schema:familyName Thai
134 schema:givenName My T.
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014521212361.49
136 rdf:type schema:Person
137 sg:pub.10.1007/11427186_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013907940
138 https://doi.org/10.1007/11427186_54
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/978-1-4614-0857-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038948493
141 https://doi.org/10.1007/978-1-4614-0857-4_1
142 rdf:type schema:CreativeWork
143 sg:pub.10.1007/s10878-014-9730-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005517416
144 https://doi.org/10.1007/s10878-014-9730-4
145 rdf:type schema:CreativeWork
146 sg:pub.10.1038/30918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041985305
147 https://doi.org/10.1038/30918
148 rdf:type schema:CreativeWork
149 sg:pub.10.1038/35019019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008269744
150 https://doi.org/10.1038/35019019
151 rdf:type schema:CreativeWork
152 sg:pub.10.1186/1471-2458-13-784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053327670
153 https://doi.org/10.1186/1471-2458-13-784
154 rdf:type schema:CreativeWork
155 grid-institutes:grid.15276.37 schema:alternateName Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA
156 schema:name Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USA
157 Division of Algorithms and Technologies for Networks Analysis, Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam
158 rdf:type schema:Organization
159 grid-institutes:grid.224260.0 schema:alternateName Department of Computer Science, Virginia Commonwealth University, Richmond, VA, USA
160 schema:name Department of Computer Science, Virginia Commonwealth University, Richmond, VA, USA
161 rdf:type schema:Organization
162 grid-institutes:grid.265122.0 schema:alternateName Department of Computer and Information Sciences, Towson University, Towson, MD, USA
163 schema:name Department of Computer and Information Sciences, Towson University, Towson, MD, USA
164 rdf:type schema:Organization
 




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


...