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

  • 2018. Information Diffusion in Complex Networks: The Active/Passive Conundrum in COMPLEX NETWORKS & THEIR APPLICATIONS VI
  • 2018. Identifying Top-K Important Nodes Based on Probabilistic-Jumping Random Walk in Complex Networks in COMPLEX NETWORKS & THEIR APPLICATIONS VI
  • 2011-05-12. Controllability of complex networks in NATURE
  • 2007. Approximating Betweenness Centrality in ALGORITHMS AND MODELS FOR THE WEB-GRAPH
  • 2003. Experiments on Graph Clustering Algorithms in ALGORITHMS - ESA 2003
  • 2011-12. Fast network centrality analysis using GPUs in BMC BIOINFORMATICS
  • 2013-12. Identifying high betweenness centrality nodes in large social networks in SOCIAL NETWORK ANALYSIS AND MINING
  • 2011. Social Networks: Prestige, Centrality, and Influence in RELATIONAL AND ALGEBRAIC METHODS IN COMPUTER SCIENCE
  • 2018. A Comparison of Approaches to Computing Betweenness Centrality for Large Graphs in COMPLEX NETWORKS & THEIR APPLICATIONS VI
  • 2017-11-28. A Betweenness Centrality Guided Clustering Algorithm and Its Applications to Cancer Diagnosis in MINING INTELLIGENCE AND KNOWLEDGE EXPLORATION
  • 2017-12. Hierarchical Decomposition for Betweenness Centrality Measure of Complex Networks in SCIENTIFIC REPORTS
  • 2016-03. Fast approximation of betweenness centrality through sampling in DATA MINING AND KNOWLEDGE DISCOVERY
  • 2018. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs in ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING
  • 2018. An Opportunistic Network Approach Towards Disease Spreading in COMPLEX NETWORKS & THEIR APPLICATIONS VI
  • 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 N0bd73fa7bded4675ab648f3dde3a4d76
    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 N4afc9cb977ca41878e2c7de60a20d223
    69 Nd2bcd68dad28473698aeae900e504e77
    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 N6d3c1b3aedd648d0a96d4df2aab5caf5
    74 Nc0dcc36c55bc4f2c9c6eb1677cf59427
    75 Ncbe9c0cf870a4ef5915a46cbf93893cd
    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 N42ada0b1a1434ea0b48d61393281cacc
    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 N06ad90cd01aa4f5d869099c59c769032 schema:affiliation https://www.grid.ac/institutes/grid.263856.c
    86 schema:familyName Sinha
    87 schema:givenName Koushik
    88 rdf:type schema:Person
    89 N0bd73fa7bded4675ab648f3dde3a4d76 rdf:first N959f45efdb4541d1b15cf53e94c08b8c
    90 rdf:rest Ndd79cd207c19437cb6174bdaa5b2c927
    91 N2f75406b08e849498debd8be234f9d2d rdf:first N06ad90cd01aa4f5d869099c59c769032
    92 rdf:rest rdf:nil
    93 N42ada0b1a1434ea0b48d61393281cacc schema:name Springer Nature - SN SciGraph project
    94 rdf:type schema:Organization
    95 N4afc9cb977ca41878e2c7de60a20d223 schema:volumeNumber 6
    96 rdf:type schema:PublicationVolume
    97 N6d3c1b3aedd648d0a96d4df2aab5caf5 schema:name dimensions_id
    98 schema:value pub.1112040389
    99 rdf:type schema:PropertyValue
    100 N817eabf6b8c3484fa78fa866afd9f539 schema:affiliation https://www.grid.ac/institutes/grid.263857.d
    101 schema:familyName Ercal
    102 schema:givenName Gunes
    103 rdf:type schema:Person
    104 N959f45efdb4541d1b15cf53e94c08b8c schema:affiliation https://www.grid.ac/institutes/grid.263857.d
    105 schema:familyName Matta
    106 schema:givenName John
    107 rdf:type schema:Person
    108 Nc0dcc36c55bc4f2c9c6eb1677cf59427 schema:name readcube_id
    109 schema:value a103ebea97bb579d101a31b511898d577a065762c76eb98e31485b53094d27bf
    110 rdf:type schema:PropertyValue
    111 Ncbe9c0cf870a4ef5915a46cbf93893cd schema:name doi
    112 schema:value 10.1186/s40649-019-0062-5
    113 rdf:type schema:PropertyValue
    114 Nd2bcd68dad28473698aeae900e504e77 schema:issueNumber 1
    115 rdf:type schema:PublicationIssue
    116 Ndd79cd207c19437cb6174bdaa5b2c927 rdf:first N817eabf6b8c3484fa78fa866afd9f539
    117 rdf:rest N2f75406b08e849498debd8be234f9d2d
    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)


    ...