Comparing the speed and accuracy of approaches to betweenness centrality approximation View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-12

AUTHORS

John Matta, Gunes Ercal, Koushik Sinha

ABSTRACT

Many algorithms require doing a large number of betweenness centrality calculations quickly, and accommodating this need is an active open research area. There are many different ideas and approaches to speeding up these calculations, and it is difficult to know which approach will work best in practical situations. The current study attempts to judge performance of betweenness centrality approximation algorithms by running them under conditions that practitioners are likely to experience. For several approaches to approximation, we run two tests, clustering and immunization, on identical hardware, along with a process to determine appropriate parameters. This allows an across-the-board comparison of techniques based on the dimensions of speed and accuracy of results. Overall, the speed of betweenness centrality can be reduced several orders of magnitude by using approximation algorithms. We find that the speeds of individual algorithms can vary widely based on input parameters. The fastest algorithms utilize parallelism, either in the form of multi-core processing or GPUs. Interestingly, getting fast results does not require an expensive GPU. The methodology presented here can guide the selection of a betweenness centrality approximation algorithm depending on a practitioner’s needs and can also be used to compare new methods to existing ones. More... »

PAGES

2

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1186/s40649-019-0062-5

DOI

http://dx.doi.org/10.1186/s40649-019-0062-5

DIMENSIONS

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


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": "Southern Illinois University Edwardsville", 
          "id": "https://www.grid.ac/institutes/grid.263857.d", 
          "name": [
            "Southern Illinois University Edwardsville, Edwardsville, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Matta", 
        "givenName": "John", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Southern Illinois University Edwardsville", 
          "id": "https://www.grid.ac/institutes/grid.263857.d", 
          "name": [
            "Southern Illinois University Edwardsville, Edwardsville, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ercal", 
        "givenName": "Gunes", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Southern Illinois University Carbondale", 
          "id": "https://www.grid.ac/institutes/grid.263856.c", 
          "name": [
            "Southern Illinois University Carbondale, Carbondale, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sinha", 
        "givenName": "Koushik", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/j.socnet.2007.11.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003001403"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.73.046108", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004812402"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.73.046108", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004812402"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2187980.2188239", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007227944"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.65.056109", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008383012"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.65.056109", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008383012"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1371/journal.pone.0044459", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010065340"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.21832", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010996235"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011636557"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.socnet.2004.11.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014695373"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2939672.2939869", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014704024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.78.046110", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016699541"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physreve.78.046110", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016699541"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.122653799", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018411012"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2903150.2903153", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020045669"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.physrep.2009.11.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020482279"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39658-1_52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021538962", 
          "https://doi.org/10.1007/978-3-540-39658-1_52"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39658-1_52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021538962", 
          "https://doi.org/10.1007/978-3-540-39658-1_52"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s13278-012-0076-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024735122", 
          "https://doi.org/10.1007/s13278-012-0076-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2006.03.011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027350779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-21070-9_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028761167", 
          "https://doi.org/10.1007/978-3-642-21070-9_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-21070-9_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028761167", 
          "https://doi.org/10.1007/978-3-642-21070-9_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/nws.2016.20", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029856687"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2898361", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030283266"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/15427951.2016.1177802", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032135838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/0022250x.2001.9990249", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032164704"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.physrep.2016.06.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033168473"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.physrep.2016.06.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033168473"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2872518.2891063", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037496959"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.socnet.2004.11.008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038531493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1734213.1734219", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044467886"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/nature10011", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045479836", 
          "https://doi.org/10.1038/nature10011"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.procs.2013.09.311", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045577209"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2458523.2458531", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045765726"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2623330.2623626", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047811509"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2105-12-149", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047965046", 
          "https://doi.org/10.1186/1471-2105-12-149"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77004-6_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049744585", 
          "https://doi.org/10.1007/978-3-540-77004-6_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-77004-6_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049744585", 
          "https://doi.org/10.1007/978-3-540-77004-6_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10618-015-0423-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049780918", 
          "https://doi.org/10.1007/s10618-015-0423-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/comjnl/bxu003", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059480638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218127407018403", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062955118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4204/eptcs.220.4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072355881"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ro/2017008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083427310"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3022668", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084227958"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/srep46491", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084980512", 
          "https://doi.org/10.1038/srep46491"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611974010.49", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088797458"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611972832.76", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088800770"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611972887.9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088800833"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3132847.3133126", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1092634348"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-72150-7_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093022510", 
          "https://doi.org/10.1007/978-3-319-72150-7_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-72150-7_25", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093022531", 
          "https://doi.org/10.1007/978-3-319-72150-7_25"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-72150-7_26", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093022532", 
          "https://doi.org/10.1007/978-3-319-72150-7_26"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-72150-7_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093022533", 
          "https://doi.org/10.1007/978-3-319-72150-7_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-71928-3_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093028984", 
          "https://doi.org/10.1007/978-3-319-71928-3_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-71928-3_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093028984", 
          "https://doi.org/10.1007/978-3-319-71928-3_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sc.2014.52", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093201880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icpp.2006.57", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093691855"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/asonam.2010.31", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093709456"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icosc.2015.7050857", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093720692"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icdm.2016.0043", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094394929"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/asonam.2012.79", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095280540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/allerton.2015.7447012", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095755292"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3085504.3085510", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096890530"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3085504.3085510", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1096890530"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tmscs.2018.2797195", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1100609919"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/3033543", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1102895783"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-93040-4_59", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1104694640", 
          "https://doi.org/10.1007/978-3-319-93040-4_59"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-12", 
    "datePublishedReg": "2019-12-01", 
    "description": "Many algorithms require doing a large number of betweenness centrality calculations quickly, and accommodating this need is an active open research area. There are many different ideas and approaches to speeding up these calculations, and it is difficult to know which approach will work best in practical situations. The current study attempts to judge performance of betweenness centrality approximation algorithms by running them under conditions that practitioners are likely to experience. For several approaches to approximation, we run two tests, clustering and immunization, on identical hardware, along with a process to determine appropriate parameters. This allows an across-the-board comparison of techniques based on the dimensions of speed and accuracy of results. Overall, the speed of betweenness centrality can be reduced several orders of magnitude by using approximation algorithms. We find that the speeds of individual algorithms can vary widely based on input parameters. The fastest algorithms utilize parallelism, either in the form of multi-core processing or GPUs. Interestingly, getting fast results does not require an expensive GPU. The methodology presented here can guide the selection of a betweenness centrality approximation algorithm depending on a practitioner\u2019s needs and can also be used to compare new methods to existing ones.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1186/s40649-019-0062-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136872", 
        "issn": [
          "2197-4314"
        ], 
        "name": "Computational Social Networks", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "6"
      }
    ], 
    "name": "Comparing the speed and accuracy of approaches to betweenness centrality approximation", 
    "pagination": "2", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a103ebea97bb579d101a31b511898d577a065762c76eb98e31485b53094d27bf"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1186/s40649-019-0062-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112040389"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1186/s40649-019-0062-5", 
      "https://app.dimensions.ai/details/publication/pub.1112040389"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T09:03", 
    "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/0000000333_0000000333/records_41724_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1186%2Fs40649-019-0062-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.1186/s40649-019-0062-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.1186/s40649-019-0062-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1186/s40649-019-0062-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1186/s40649-019-0062-5'


 

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

262 TRIPLES      21 PREDICATES      85 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1186/s40649-019-0062-5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ndead36ac87d54dcb9b78bbfc2c17f66d
4 schema:citation sg:pub.10.1007/978-3-319-71928-3_4
5 sg:pub.10.1007/978-3-319-72150-7_1
6 sg:pub.10.1007/978-3-319-72150-7_25
7 sg:pub.10.1007/978-3-319-72150-7_26
8 sg:pub.10.1007/978-3-319-72150-7_27
9 sg:pub.10.1007/978-3-319-93040-4_59
10 sg:pub.10.1007/978-3-540-39658-1_52
11 sg:pub.10.1007/978-3-540-77004-6_10
12 sg:pub.10.1007/978-3-642-21070-9_2
13 sg:pub.10.1007/s10618-015-0423-0
14 sg:pub.10.1007/s13278-012-0076-6
15 sg:pub.10.1038/nature10011
16 sg:pub.10.1038/srep46491
17 sg:pub.10.1186/1471-2105-12-149
18 https://doi.org/10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2
19 https://doi.org/10.1002/jgt.21832
20 https://doi.org/10.1016/j.disc.2006.03.011
21 https://doi.org/10.1016/j.physrep.2009.11.002
22 https://doi.org/10.1016/j.physrep.2016.06.007
23 https://doi.org/10.1016/j.procs.2013.09.311
24 https://doi.org/10.1016/j.socnet.2004.11.007
25 https://doi.org/10.1016/j.socnet.2004.11.008
26 https://doi.org/10.1016/j.socnet.2007.11.001
27 https://doi.org/10.1017/nws.2016.20
28 https://doi.org/10.1051/ro/2017008
29 https://doi.org/10.1073/pnas.122653799
30 https://doi.org/10.1080/0022250x.2001.9990249
31 https://doi.org/10.1080/15427951.2016.1177802
32 https://doi.org/10.1093/comjnl/bxu003
33 https://doi.org/10.1103/physreve.65.056109
34 https://doi.org/10.1103/physreve.73.046108
35 https://doi.org/10.1103/physreve.78.046110
36 https://doi.org/10.1109/allerton.2015.7447012
37 https://doi.org/10.1109/asonam.2010.31
38 https://doi.org/10.1109/asonam.2012.79
39 https://doi.org/10.1109/icdm.2016.0043
40 https://doi.org/10.1109/icosc.2015.7050857
41 https://doi.org/10.1109/icpp.2006.57
42 https://doi.org/10.1109/sc.2014.52
43 https://doi.org/10.1109/tmscs.2018.2797195
44 https://doi.org/10.1137/1.9781611972832.76
45 https://doi.org/10.1137/1.9781611972887.9
46 https://doi.org/10.1137/1.9781611974010.49
47 https://doi.org/10.1142/s0218127407018403
48 https://doi.org/10.1145/1734213.1734219
49 https://doi.org/10.1145/2187980.2188239
50 https://doi.org/10.1145/2458523.2458531
51 https://doi.org/10.1145/2623330.2623626
52 https://doi.org/10.1145/2872518.2891063
53 https://doi.org/10.1145/2898361
54 https://doi.org/10.1145/2903150.2903153
55 https://doi.org/10.1145/2939672.2939869
56 https://doi.org/10.1145/3022668
57 https://doi.org/10.1145/3085504.3085510
58 https://doi.org/10.1145/3132847.3133126
59 https://doi.org/10.1371/journal.pone.0044459
60 https://doi.org/10.2307/3033543
61 https://doi.org/10.4204/eptcs.220.4
62 schema:datePublished 2019-12
63 schema:datePublishedReg 2019-12-01
64 schema:description Many algorithms require doing a large number of betweenness centrality calculations quickly, and accommodating this need is an active open research area. There are many different ideas and approaches to speeding up these calculations, and it is difficult to know which approach will work best in practical situations. The current study attempts to judge performance of betweenness centrality approximation algorithms by running them under conditions that practitioners are likely to experience. For several approaches to approximation, we run two tests, clustering and immunization, on identical hardware, along with a process to determine appropriate parameters. This allows an across-the-board comparison of techniques based on the dimensions of speed and accuracy of results. Overall, the speed of betweenness centrality can be reduced several orders of magnitude by using approximation algorithms. We find that the speeds of individual algorithms can vary widely based on input parameters. The fastest algorithms utilize parallelism, either in the form of multi-core processing or GPUs. Interestingly, getting fast results does not require an expensive GPU. The methodology presented here can guide the selection of a betweenness centrality approximation algorithm depending on a practitioner’s needs and can also be used to compare new methods to existing ones.
65 schema:genre research_article
66 schema:inLanguage en
67 schema:isAccessibleForFree false
68 schema:isPartOf N8fd29effb185404aafae3416914adafa
69 Na362cfa8c8cb42778e5e8a53df55dcda
70 sg:journal.1136872
71 schema:name Comparing the speed and accuracy of approaches to betweenness centrality approximation
72 schema:pagination 2
73 schema:productId N311918d2cf034b24aa09faf49d5351a5
74 Na44bb07c609745a5ba7b815b0ade7a02
75 Nedae96fbae4b4c71822855761df3e3a9
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112040389
77 https://doi.org/10.1186/s40649-019-0062-5
78 schema:sdDatePublished 2019-04-11T09:03
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher N50534afbbbf64aaf81b5e8587930eef1
81 schema:url https://link.springer.com/10.1186%2Fs40649-019-0062-5
82 sgo:license sg:explorer/license/
83 sgo:sdDataset articles
84 rdf:type schema:ScholarlyArticle
85 N070f9a9df0814409ba5ed8fa65bf7c98 rdf:first Nff68941251b544ec93e65575617b48ef
86 rdf:rest Ndeab59938aa34a359631388d4deffa48
87 N14af514ba49242f5af85df840771255b schema:affiliation https://www.grid.ac/institutes/grid.263857.d
88 schema:familyName Matta
89 schema:givenName John
90 rdf:type schema:Person
91 N311918d2cf034b24aa09faf49d5351a5 schema:name doi
92 schema:value 10.1186/s40649-019-0062-5
93 rdf:type schema:PropertyValue
94 N50534afbbbf64aaf81b5e8587930eef1 schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N5719453735e341acb2ae11574a86568a schema:affiliation https://www.grid.ac/institutes/grid.263856.c
97 schema:familyName Sinha
98 schema:givenName Koushik
99 rdf:type schema:Person
100 N8fd29effb185404aafae3416914adafa schema:volumeNumber 6
101 rdf:type schema:PublicationVolume
102 Na362cfa8c8cb42778e5e8a53df55dcda schema:issueNumber 1
103 rdf:type schema:PublicationIssue
104 Na44bb07c609745a5ba7b815b0ade7a02 schema:name readcube_id
105 schema:value a103ebea97bb579d101a31b511898d577a065762c76eb98e31485b53094d27bf
106 rdf:type schema:PropertyValue
107 Ndeab59938aa34a359631388d4deffa48 rdf:first N5719453735e341acb2ae11574a86568a
108 rdf:rest rdf:nil
109 Ndead36ac87d54dcb9b78bbfc2c17f66d rdf:first N14af514ba49242f5af85df840771255b
110 rdf:rest N070f9a9df0814409ba5ed8fa65bf7c98
111 Nedae96fbae4b4c71822855761df3e3a9 schema:name dimensions_id
112 schema:value pub.1112040389
113 rdf:type schema:PropertyValue
114 Nff68941251b544ec93e65575617b48ef schema:affiliation https://www.grid.ac/institutes/grid.263857.d
115 schema:familyName Ercal
116 schema:givenName Gunes
117 rdf:type schema:Person
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
122 schema:name Computation Theory and Mathematics
123 rdf:type schema:DefinedTerm
124 sg:journal.1136872 schema:issn 2197-4314
125 schema:name Computational Social Networks
126 rdf:type schema:Periodical
127 sg:pub.10.1007/978-3-319-71928-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093028984
128 https://doi.org/10.1007/978-3-319-71928-3_4
129 rdf:type schema:CreativeWork
130 sg:pub.10.1007/978-3-319-72150-7_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093022510
131 https://doi.org/10.1007/978-3-319-72150-7_1
132 rdf:type schema:CreativeWork
133 sg:pub.10.1007/978-3-319-72150-7_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093022531
134 https://doi.org/10.1007/978-3-319-72150-7_25
135 rdf:type schema:CreativeWork
136 sg:pub.10.1007/978-3-319-72150-7_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093022532
137 https://doi.org/10.1007/978-3-319-72150-7_26
138 rdf:type schema:CreativeWork
139 sg:pub.10.1007/978-3-319-72150-7_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093022533
140 https://doi.org/10.1007/978-3-319-72150-7_27
141 rdf:type schema:CreativeWork
142 sg:pub.10.1007/978-3-319-93040-4_59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1104694640
143 https://doi.org/10.1007/978-3-319-93040-4_59
144 rdf:type schema:CreativeWork
145 sg:pub.10.1007/978-3-540-39658-1_52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021538962
146 https://doi.org/10.1007/978-3-540-39658-1_52
147 rdf:type schema:CreativeWork
148 sg:pub.10.1007/978-3-540-77004-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049744585
149 https://doi.org/10.1007/978-3-540-77004-6_10
150 rdf:type schema:CreativeWork
151 sg:pub.10.1007/978-3-642-21070-9_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028761167
152 https://doi.org/10.1007/978-3-642-21070-9_2
153 rdf:type schema:CreativeWork
154 sg:pub.10.1007/s10618-015-0423-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049780918
155 https://doi.org/10.1007/s10618-015-0423-0
156 rdf:type schema:CreativeWork
157 sg:pub.10.1007/s13278-012-0076-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024735122
158 https://doi.org/10.1007/s13278-012-0076-6
159 rdf:type schema:CreativeWork
160 sg:pub.10.1038/nature10011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045479836
161 https://doi.org/10.1038/nature10011
162 rdf:type schema:CreativeWork
163 sg:pub.10.1038/srep46491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084980512
164 https://doi.org/10.1038/srep46491
165 rdf:type schema:CreativeWork
166 sg:pub.10.1186/1471-2105-12-149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047965046
167 https://doi.org/10.1186/1471-2105-12-149
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011636557
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1002/jgt.21832 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010996235
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1016/j.disc.2006.03.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027350779
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1016/j.physrep.2009.11.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020482279
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1016/j.physrep.2016.06.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033168473
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1016/j.procs.2013.09.311 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045577209
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1016/j.socnet.2004.11.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014695373
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1016/j.socnet.2004.11.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038531493
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1016/j.socnet.2007.11.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003001403
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1017/nws.2016.20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029856687
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1051/ro/2017008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083427310
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1073/pnas.122653799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018411012
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1080/0022250x.2001.9990249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032164704
194 rdf:type schema:CreativeWork
195 https://doi.org/10.1080/15427951.2016.1177802 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032135838
196 rdf:type schema:CreativeWork
197 https://doi.org/10.1093/comjnl/bxu003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059480638
198 rdf:type schema:CreativeWork
199 https://doi.org/10.1103/physreve.65.056109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008383012
200 rdf:type schema:CreativeWork
201 https://doi.org/10.1103/physreve.73.046108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004812402
202 rdf:type schema:CreativeWork
203 https://doi.org/10.1103/physreve.78.046110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016699541
204 rdf:type schema:CreativeWork
205 https://doi.org/10.1109/allerton.2015.7447012 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095755292
206 rdf:type schema:CreativeWork
207 https://doi.org/10.1109/asonam.2010.31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093709456
208 rdf:type schema:CreativeWork
209 https://doi.org/10.1109/asonam.2012.79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095280540
210 rdf:type schema:CreativeWork
211 https://doi.org/10.1109/icdm.2016.0043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094394929
212 rdf:type schema:CreativeWork
213 https://doi.org/10.1109/icosc.2015.7050857 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093720692
214 rdf:type schema:CreativeWork
215 https://doi.org/10.1109/icpp.2006.57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093691855
216 rdf:type schema:CreativeWork
217 https://doi.org/10.1109/sc.2014.52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093201880
218 rdf:type schema:CreativeWork
219 https://doi.org/10.1109/tmscs.2018.2797195 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100609919
220 rdf:type schema:CreativeWork
221 https://doi.org/10.1137/1.9781611972832.76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088800770
222 rdf:type schema:CreativeWork
223 https://doi.org/10.1137/1.9781611972887.9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088800833
224 rdf:type schema:CreativeWork
225 https://doi.org/10.1137/1.9781611974010.49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088797458
226 rdf:type schema:CreativeWork
227 https://doi.org/10.1142/s0218127407018403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062955118
228 rdf:type schema:CreativeWork
229 https://doi.org/10.1145/1734213.1734219 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044467886
230 rdf:type schema:CreativeWork
231 https://doi.org/10.1145/2187980.2188239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007227944
232 rdf:type schema:CreativeWork
233 https://doi.org/10.1145/2458523.2458531 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045765726
234 rdf:type schema:CreativeWork
235 https://doi.org/10.1145/2623330.2623626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047811509
236 rdf:type schema:CreativeWork
237 https://doi.org/10.1145/2872518.2891063 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037496959
238 rdf:type schema:CreativeWork
239 https://doi.org/10.1145/2898361 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030283266
240 rdf:type schema:CreativeWork
241 https://doi.org/10.1145/2903150.2903153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020045669
242 rdf:type schema:CreativeWork
243 https://doi.org/10.1145/2939672.2939869 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014704024
244 rdf:type schema:CreativeWork
245 https://doi.org/10.1145/3022668 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084227958
246 rdf:type schema:CreativeWork
247 https://doi.org/10.1145/3085504.3085510 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096890530
248 rdf:type schema:CreativeWork
249 https://doi.org/10.1145/3132847.3133126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092634348
250 rdf:type schema:CreativeWork
251 https://doi.org/10.1371/journal.pone.0044459 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010065340
252 rdf:type schema:CreativeWork
253 https://doi.org/10.2307/3033543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1102895783
254 rdf:type schema:CreativeWork
255 https://doi.org/10.4204/eptcs.220.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072355881
256 rdf:type schema:CreativeWork
257 https://www.grid.ac/institutes/grid.263856.c schema:alternateName Southern Illinois University Carbondale
258 schema:name Southern Illinois University Carbondale, Carbondale, IL, USA
259 rdf:type schema:Organization
260 https://www.grid.ac/institutes/grid.263857.d schema:alternateName Southern Illinois University Edwardsville
261 schema:name Southern Illinois University Edwardsville, Edwardsville, IL, USA
262 rdf:type schema:Organization
 




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


...