A heuristic approach to estimate nodes’ closeness rank using the properties of real world networks View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-12

AUTHORS

Akrati Saxena, Ralucca Gera, S. R. S. Iyengar

ABSTRACT

Centrality measures capture the intuitive notion of the importance of a node in a network. Importance of a node can be a very subjective term and is defined based on the context and the application. Closeness centrality is one of the most popular centrality measures which quantifies how close a node is to every other node in the network. It considers the average distance of a given node to all the other nodes in a network and requires one to know the complete information of the network. To compute the closeness rank of a node, we first need to compute the closeness value of all the nodes, and then compare them to get the rank of the node. In this work, we address the problem of estimating the closeness centrality rank of a node without computing the closeness centrality values of all the nodes in the network. We provide linear time heuristic algorithms which run in O(m), versus the classical algorithm which runs in time O(m·n), where m is the number of edges and n is the number of nodes in the network. The proposed methods are applied to real-world networks, and their accuracy is measured using absolute and weighted error functions. More... »

PAGES

3

References to SciGraph publications

  • 2003. Trust Management for the Semantic Web in THE SEMANTIC WEB - ISWC 2003
  • 2004. The Enron Corpus: A New Dataset for Email Classification Research in MACHINE LEARNING: ECML 2004
  • 1978. The Levenberg-Marquardt algorithm: Implementation and theory in NUMERICAL ANALYSIS
  • 1966-12. The centrality index of a graph in PSYCHOMETRIKA
  • 2015-01. Defining and evaluating network communities based on ground-truth in KNOWLEDGE AND INFORMATION SYSTEMS
  • 2008. Ranking of Closeness Centrality for Large-Scale Social Networks in FRONTIERS IN ALGORITHMICS
  • 1953-03. A new status index derived from sociometric analysis in PSYCHOMETRIKA
  • 2012-12. Social dynamics of Digg in EPJ DATA SCIENCE
  • 2001-05. Lethality and centrality in protein networks in NATURE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s13278-018-0545-7

    DOI

    http://dx.doi.org/10.1007/s13278-018-0545-7

    DIMENSIONS

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


    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": "Indian Institute of Technology Ropar", 
              "id": "https://www.grid.ac/institutes/grid.462391.b", 
              "name": [
                "Department of CSE, Indian Institute of Technology Ropar, Rupnagar, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saxena", 
            "givenName": "Akrati", 
            "id": "sg:person.011572412354.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011572412354.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Naval Postgraduate School", 
              "id": "https://www.grid.ac/institutes/grid.1108.8", 
              "name": [
                "Department of Applied Mathematics, Naval Postgraduate School, 93943, Monterey, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gera", 
            "givenName": "Ralucca", 
            "id": "sg:person.012175537466.96", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012175537466.96"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Indian Institute of Technology Ropar", 
              "id": "https://www.grid.ac/institutes/grid.462391.b", 
              "name": [
                "Department of CSE, Indian Institute of Technology Ropar, Rupnagar, India"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Iyengar", 
            "givenName": "S. R. S.", 
            "id": "sg:person.015570646023.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015570646023.98"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/1150402.1150443", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003421913"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1371/journal.pcbi.0020095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004580600"
            ], 
            "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.1109/icde.2014.6816651", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010019174"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.286.5439.509", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010080128"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-69311-6_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010551163", 
              "https://doi.org/10.1007/978-3-540-69311-6_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1052812.1052825", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011537260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.64.016132", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013982839"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.64.016132", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013982839"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1155/2014/202350", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014532907"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-8733(78)90021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016916901"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1592665.1592675", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023647599"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0067700", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024612844", 
              "https://doi.org/10.1007/bfb0067700"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289527", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025048784", 
              "https://doi.org/10.1007/bf02289527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289527", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025048784", 
              "https://doi.org/10.1007/bf02289527"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1753326.1753532", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027142118"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1756-8765.2011.01178.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028529814"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1140/epjds5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029110460", 
              "https://doi.org/10.1140/epjds5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1037/h0053638", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030564722"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1651274.1651282", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032364805"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.physa.2011.09.017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032430529"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/asi.21128", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033394264"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/asi.21128", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033394264"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0169-7552(98)00110-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035913093"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/nar/gki072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037000820"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/35075138", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038990326", 
              "https://doi.org/10.1038/35075138"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/35075138", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038990326", 
              "https://doi.org/10.1038/35075138"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2492517.2492533", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039199677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2020408.2020579", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040445944"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10115-013-0693-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041186630", 
              "https://doi.org/10.1007/s10115-013-0693-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1371/journal.pone.0001049", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042196054"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39718-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043116599", 
              "https://doi.org/10.1007/978-3-540-39718-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39718-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043116599", 
              "https://doi.org/10.1007/978-3-540-39718-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30115-8_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044538060", 
              "https://doi.org/10.1007/978-3-540-30115-8_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30115-8_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044538060", 
              "https://doi.org/10.1007/978-3-540-30115-8_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1217299.1217301", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045616655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0378-8733(89)90016-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045651165"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1527/tjsai.29.234", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045709942"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2184356.2184368", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050440762"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/280765.280786", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050615341"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051171362", 
              "https://doi.org/10.1007/bf02289026"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02289026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051171362", 
              "https://doi.org/10.1007/bf02289026"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.socnet.2015.08.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051223077"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2660460.2660465", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052591490"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/01621459.1972.10481251", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1058300899"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/biomet/33.3.239", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059415966"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s003614450342480", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062877811"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s003614450342480", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062877811"
            ], 
            "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.3837/tiis.2016.03.031", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1071450620"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.7155/jgaa.00081", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1073626367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3110025.3110064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1092751288"
            ], 
            "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/icdm.2013.135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094510429"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wisa.2012.52", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095041407"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/cdc.2015.7402978", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095791566"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3110025.3110063", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095873349"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1063/1.4937104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1096192247"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611974317.6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557468"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/3033543", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1102895783"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-12", 
        "datePublishedReg": "2019-12-01", 
        "description": "Centrality measures capture the intuitive notion of the importance of a node in a network. Importance of a node can be a very subjective term and is defined based on the context and the application. Closeness centrality is one of the most popular centrality measures which quantifies how close a node is to every other node in the network. It considers the average distance of a given node to all the other nodes in a network and requires one to know the complete information of the network. To compute the closeness rank of a node, we first need to compute the closeness value of all the nodes, and then compare them to get the rank of the node. In this work, we address the problem of estimating the closeness centrality rank of a node without computing the closeness centrality values of all the nodes in the network. We provide linear time heuristic algorithms which run in O(m), versus the classical algorithm which runs in time O(m\u00b7n), where m is the number of edges and n is the number of nodes in the network. The proposed methods are applied to real-world networks, and their accuracy is measured using absolute and weighted error functions.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s13278-018-0545-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1048971", 
            "issn": [
              "1869-5450", 
              "1869-5469"
            ], 
            "name": "Social Network Analysis and Mining", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "name": "A heuristic approach to estimate nodes\u2019 closeness rank using the properties of real world networks", 
        "pagination": "3", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b31f6ee19c8273c8af01d89557b000aa692a0f68efc771cbd8e22ea7bf5eeaed"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s13278-018-0545-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1110401631"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s13278-018-0545-7", 
          "https://app.dimensions.ai/details/publication/pub.1110401631"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T08:19", 
        "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/0000000282_0000000282/records_78266_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs13278-018-0545-7"
      }
    ]
     

    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-018-0545-7'

    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-018-0545-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s13278-018-0545-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s13278-018-0545-7'


     

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

    243 TRIPLES      21 PREDICATES      79 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s13278-018-0545-7 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Na196d01205e34f7a8dd7e512612a2c77
    4 schema:citation sg:pub.10.1007/978-3-540-30115-8_22
    5 sg:pub.10.1007/978-3-540-39718-2_23
    6 sg:pub.10.1007/978-3-540-69311-6_21
    7 sg:pub.10.1007/bf02289026
    8 sg:pub.10.1007/bf02289527
    9 sg:pub.10.1007/bfb0067700
    10 sg:pub.10.1007/s10115-013-0693-z
    11 sg:pub.10.1038/35075138
    12 sg:pub.10.1140/epjds5
    13 https://doi.org/10.1002/asi.21128
    14 https://doi.org/10.1016/0378-8733(78)90021-7
    15 https://doi.org/10.1016/0378-8733(89)90016-6
    16 https://doi.org/10.1016/j.physa.2011.09.017
    17 https://doi.org/10.1016/j.socnet.2015.08.003
    18 https://doi.org/10.1016/s0169-7552(98)00110-x
    19 https://doi.org/10.1037/h0053638
    20 https://doi.org/10.1063/1.4937104
    21 https://doi.org/10.1080/01621459.1972.10481251
    22 https://doi.org/10.1093/biomet/33.3.239
    23 https://doi.org/10.1093/nar/gki072
    24 https://doi.org/10.1103/physreve.64.016132
    25 https://doi.org/10.1109/cdc.2015.7402978
    26 https://doi.org/10.1109/icde.2014.6816651
    27 https://doi.org/10.1109/icdm.2013.135
    28 https://doi.org/10.1109/icpp.2006.57
    29 https://doi.org/10.1109/wisa.2012.52
    30 https://doi.org/10.1111/j.1756-8765.2011.01178.x
    31 https://doi.org/10.1126/science.286.5439.509
    32 https://doi.org/10.1137/1.9781611974317.6
    33 https://doi.org/10.1137/s003614450342480
    34 https://doi.org/10.1142/s0218127407018403
    35 https://doi.org/10.1145/1052812.1052825
    36 https://doi.org/10.1145/1150402.1150443
    37 https://doi.org/10.1145/1217299.1217301
    38 https://doi.org/10.1145/1592665.1592675
    39 https://doi.org/10.1145/1651274.1651282
    40 https://doi.org/10.1145/1753326.1753532
    41 https://doi.org/10.1145/2020408.2020579
    42 https://doi.org/10.1145/2184356.2184368
    43 https://doi.org/10.1145/2187980.2188239
    44 https://doi.org/10.1145/2492517.2492533
    45 https://doi.org/10.1145/2660460.2660465
    46 https://doi.org/10.1145/280765.280786
    47 https://doi.org/10.1145/3110025.3110063
    48 https://doi.org/10.1145/3110025.3110064
    49 https://doi.org/10.1155/2014/202350
    50 https://doi.org/10.1371/journal.pcbi.0020095
    51 https://doi.org/10.1371/journal.pone.0001049
    52 https://doi.org/10.1527/tjsai.29.234
    53 https://doi.org/10.2307/3033543
    54 https://doi.org/10.3837/tiis.2016.03.031
    55 https://doi.org/10.7155/jgaa.00081
    56 schema:datePublished 2019-12
    57 schema:datePublishedReg 2019-12-01
    58 schema:description Centrality measures capture the intuitive notion of the importance of a node in a network. Importance of a node can be a very subjective term and is defined based on the context and the application. Closeness centrality is one of the most popular centrality measures which quantifies how close a node is to every other node in the network. It considers the average distance of a given node to all the other nodes in a network and requires one to know the complete information of the network. To compute the closeness rank of a node, we first need to compute the closeness value of all the nodes, and then compare them to get the rank of the node. In this work, we address the problem of estimating the closeness centrality rank of a node without computing the closeness centrality values of all the nodes in the network. We provide linear time heuristic algorithms which run in O(m), versus the classical algorithm which runs in time O(m·n), where m is the number of edges and n is the number of nodes in the network. The proposed methods are applied to real-world networks, and their accuracy is measured using absolute and weighted error functions.
    59 schema:genre research_article
    60 schema:inLanguage en
    61 schema:isAccessibleForFree false
    62 schema:isPartOf N8e448726538a46649e9c093a8c434f4b
    63 N9f484bb4ff5747699aff9b7f6a238f6e
    64 sg:journal.1048971
    65 schema:name A heuristic approach to estimate nodes’ closeness rank using the properties of real world networks
    66 schema:pagination 3
    67 schema:productId N415af37548f34a57b6c823d2f28c24c4
    68 N44c45880d80e46d4a3ce9400e7bc56e9
    69 Ne9d54a81eec84c009f2de7a91002e02e
    70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110401631
    71 https://doi.org/10.1007/s13278-018-0545-7
    72 schema:sdDatePublished 2019-04-11T08:19
    73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    74 schema:sdPublisher N2fcc6372388d4abfab671687e3b2d6fd
    75 schema:url https://link.springer.com/10.1007%2Fs13278-018-0545-7
    76 sgo:license sg:explorer/license/
    77 sgo:sdDataset articles
    78 rdf:type schema:ScholarlyArticle
    79 N126ae8decdad4ea3b7864aba39ff8e44 rdf:first sg:person.015570646023.98
    80 rdf:rest rdf:nil
    81 N2fcc6372388d4abfab671687e3b2d6fd schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 N3cbce3831d28495886fc7d7445a82168 rdf:first sg:person.012175537466.96
    84 rdf:rest N126ae8decdad4ea3b7864aba39ff8e44
    85 N415af37548f34a57b6c823d2f28c24c4 schema:name dimensions_id
    86 schema:value pub.1110401631
    87 rdf:type schema:PropertyValue
    88 N44c45880d80e46d4a3ce9400e7bc56e9 schema:name doi
    89 schema:value 10.1007/s13278-018-0545-7
    90 rdf:type schema:PropertyValue
    91 N8e448726538a46649e9c093a8c434f4b schema:issueNumber 1
    92 rdf:type schema:PublicationIssue
    93 N9f484bb4ff5747699aff9b7f6a238f6e schema:volumeNumber 9
    94 rdf:type schema:PublicationVolume
    95 Na196d01205e34f7a8dd7e512612a2c77 rdf:first sg:person.011572412354.16
    96 rdf:rest N3cbce3831d28495886fc7d7445a82168
    97 Ne9d54a81eec84c009f2de7a91002e02e schema:name readcube_id
    98 schema:value b31f6ee19c8273c8af01d89557b000aa692a0f68efc771cbd8e22ea7bf5eeaed
    99 rdf:type schema:PropertyValue
    100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Information and Computing Sciences
    102 rdf:type schema:DefinedTerm
    103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    104 schema:name Computation Theory and Mathematics
    105 rdf:type schema:DefinedTerm
    106 sg:journal.1048971 schema:issn 1869-5450
    107 1869-5469
    108 schema:name Social Network Analysis and Mining
    109 rdf:type schema:Periodical
    110 sg:person.011572412354.16 schema:affiliation https://www.grid.ac/institutes/grid.462391.b
    111 schema:familyName Saxena
    112 schema:givenName Akrati
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011572412354.16
    114 rdf:type schema:Person
    115 sg:person.012175537466.96 schema:affiliation https://www.grid.ac/institutes/grid.1108.8
    116 schema:familyName Gera
    117 schema:givenName Ralucca
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012175537466.96
    119 rdf:type schema:Person
    120 sg:person.015570646023.98 schema:affiliation https://www.grid.ac/institutes/grid.462391.b
    121 schema:familyName Iyengar
    122 schema:givenName S. R. S.
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015570646023.98
    124 rdf:type schema:Person
    125 sg:pub.10.1007/978-3-540-30115-8_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044538060
    126 https://doi.org/10.1007/978-3-540-30115-8_22
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-540-39718-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043116599
    129 https://doi.org/10.1007/978-3-540-39718-2_23
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-540-69311-6_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010551163
    132 https://doi.org/10.1007/978-3-540-69311-6_21
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/bf02289026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051171362
    135 https://doi.org/10.1007/bf02289026
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/bf02289527 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025048784
    138 https://doi.org/10.1007/bf02289527
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/bfb0067700 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024612844
    141 https://doi.org/10.1007/bfb0067700
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/s10115-013-0693-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1041186630
    144 https://doi.org/10.1007/s10115-013-0693-z
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1038/35075138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038990326
    147 https://doi.org/10.1038/35075138
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1140/epjds5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029110460
    150 https://doi.org/10.1140/epjds5
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1002/asi.21128 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033394264
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1016/0378-8733(78)90021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016916901
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1016/0378-8733(89)90016-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045651165
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.physa.2011.09.017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032430529
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/j.socnet.2015.08.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051223077
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/s0169-7552(98)00110-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1035913093
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1037/h0053638 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030564722
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1063/1.4937104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096192247
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1080/01621459.1972.10481251 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058300899
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1093/biomet/33.3.239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059415966
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1093/nar/gki072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037000820
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1103/physreve.64.016132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013982839
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1109/cdc.2015.7402978 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095791566
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1109/icde.2014.6816651 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010019174
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1109/icdm.2013.135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094510429
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1109/icpp.2006.57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093691855
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1109/wisa.2012.52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095041407
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1111/j.1756-8765.2011.01178.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1028529814
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1137/1.9781611974317.6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557468
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1137/s003614450342480 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062877811
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1142/s0218127407018403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062955118
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1145/1052812.1052825 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011537260
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1145/1150402.1150443 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003421913
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1145/1217299.1217301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045616655
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1145/1592665.1592675 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023647599
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1145/1651274.1651282 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032364805
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1145/1753326.1753532 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027142118
    207 rdf:type schema:CreativeWork
    208 https://doi.org/10.1145/2020408.2020579 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040445944
    209 rdf:type schema:CreativeWork
    210 https://doi.org/10.1145/2184356.2184368 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050440762
    211 rdf:type schema:CreativeWork
    212 https://doi.org/10.1145/2187980.2188239 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007227944
    213 rdf:type schema:CreativeWork
    214 https://doi.org/10.1145/2492517.2492533 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039199677
    215 rdf:type schema:CreativeWork
    216 https://doi.org/10.1145/2660460.2660465 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052591490
    217 rdf:type schema:CreativeWork
    218 https://doi.org/10.1145/280765.280786 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050615341
    219 rdf:type schema:CreativeWork
    220 https://doi.org/10.1145/3110025.3110063 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095873349
    221 rdf:type schema:CreativeWork
    222 https://doi.org/10.1145/3110025.3110064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092751288
    223 rdf:type schema:CreativeWork
    224 https://doi.org/10.1155/2014/202350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014532907
    225 rdf:type schema:CreativeWork
    226 https://doi.org/10.1371/journal.pcbi.0020095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004580600
    227 rdf:type schema:CreativeWork
    228 https://doi.org/10.1371/journal.pone.0001049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042196054
    229 rdf:type schema:CreativeWork
    230 https://doi.org/10.1527/tjsai.29.234 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045709942
    231 rdf:type schema:CreativeWork
    232 https://doi.org/10.2307/3033543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1102895783
    233 rdf:type schema:CreativeWork
    234 https://doi.org/10.3837/tiis.2016.03.031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1071450620
    235 rdf:type schema:CreativeWork
    236 https://doi.org/10.7155/jgaa.00081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073626367
    237 rdf:type schema:CreativeWork
    238 https://www.grid.ac/institutes/grid.1108.8 schema:alternateName Naval Postgraduate School
    239 schema:name Department of Applied Mathematics, Naval Postgraduate School, 93943, Monterey, CA, USA
    240 rdf:type schema:Organization
    241 https://www.grid.ac/institutes/grid.462391.b schema:alternateName Indian Institute of Technology Ropar
    242 schema:name Department of CSE, Indian Institute of Technology Ropar, Rupnagar, India
    243 rdf:type schema:Organization
     




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


    ...