Complex Network Hierarchical Sampling Method Combining Node Neighborhood Clustering Coefficient with Random Walk View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-07-10

AUTHORS

Xiaoyang Liu, Mengyao Zhang, Giacomo Fiumara, Pasquale De Meo

ABSTRACT

Aiming at the problem of over-sampling for high-degree nodes and low-degree nodes in current sampling algorithms, a node Neighborhood Clustering coefficient Hierarchical Random Walk (NCHRW) sampling method is proposed. Firstly, the idea of hierarchy and degree distribution are adopted, and the k-means clustering algorithm is used to determine the value of the number of layers; secondly, combining the accuracy degree distribution to determine the boundary value between each hierarchical network; thirdly, sampling is carried out not only by taking the degree of the current node, the number of common neighbors between the current node and its neighbors, but the clustering coefficient of these neighbors into consideration at each layer. Finally, on eight real networks and one synthetic network, NCHRW and existing algorithms are compared from six aspects of degree distribution, density, average degree, average clustering coefficient, transitivity and sampling network visualization. The results show that the proposed NCHRW method is significantly better than other nine traditional sampling algorithms in terms of degree distribution, density and average degree, the topology properties of the network can be preserved very well. More... »

PAGES

765-807

References to SciGraph publications

  • 2019-12-09. GL2vec: Graph Embedding Enriched by Line Graphs with Edge Features in NEURAL INFORMATION PROCESSING
  • 2019. Learning Automata Approach for Social Networks in NONE
  • 2018-08-30. Sampling online social networks by random walk with indirect jumps in DATA MINING AND KNOWLEDGE DISCOVERY
  • 2004-09. Problems with fitting to the power-law distribution in THE EUROPEAN PHYSICAL JOURNAL B
  • 2015-03-02. Understanding the influence of all nodes in a network in SCIENTIFIC REPORTS
  • 2005. Reducing Large Internet Topologies for Faster Simulations in NETWORKING 2005. NETWORKING TECHNOLOGIES, SERVICES, AND PROTOCOLS; PERFORMANCE OF COMPUTER AND COMMUNICATION NETWORKS; MOBILE AND WIRELESS COMMUNICATIONS SYSTEMS
  • 2016-08-13. Sampling algorithms for weighted networks in SOCIAL NETWORK ANALYSIS AND MINING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00354-022-00179-x

    DOI

    http://dx.doi.org/10.1007/s00354-022-00179-x

    DIMENSIONS

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


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China", 
              "id": "http://www.grid.ac/institutes/grid.411594.c", 
              "name": [
                "School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Liu", 
            "givenName": "Xiaoyang", 
            "id": "sg:person.012552614265.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012552614265.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China", 
              "id": "http://www.grid.ac/institutes/grid.411594.c", 
              "name": [
                "School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Mengyao", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "MIFT Department, University of Messina, V.Le F. Stagno D\u2019Alcontres, 31, 98166, Messina, Italy", 
              "id": "http://www.grid.ac/institutes/grid.10438.3e", 
              "name": [
                "MIFT Department, University of Messina, V.Le F. Stagno D\u2019Alcontres, 31, 98166, Messina, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fiumara", 
            "givenName": "Giacomo", 
            "id": "sg:person.012703226440.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012703226440.09"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Ancient and Modern Civilizations, University of Messina, V.Le G. Palatucci, 25, 98166, Messina, Italy", 
              "id": "http://www.grid.ac/institutes/grid.10438.3e", 
              "name": [
                "Department of Ancient and Modern Civilizations, University of Messina, V.Le G. Palatucci, 25, 98166, Messina, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "De Meo", 
            "givenName": "Pasquale", 
            "id": "sg:person.016710177037.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016710177037.82"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1140/epjb/e2004-00316-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007936830", 
              "https://doi.org/10.1140/epjb/e2004-00316-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11422778_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012664505", 
              "https://doi.org/10.1007/11422778_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10618-018-0587-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1106430478", 
              "https://doi.org/10.1007/s10618-018-0587-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/srep08665", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021419058", 
              "https://doi.org/10.1038/srep08665"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-10767-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1111703242", 
              "https://doi.org/10.1007/978-3-030-10767-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-030-36718-3_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1123259327", 
              "https://doi.org/10.1007/978-3-030-36718-3_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s13278-016-0371-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051247403", 
              "https://doi.org/10.1007/s13278-016-0371-8"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-07-10", 
        "datePublishedReg": "2022-07-10", 
        "description": "Aiming at the problem of over-sampling for high-degree nodes and low-degree nodes in current sampling algorithms, a node Neighborhood Clustering coefficient Hierarchical Random Walk (NCHRW) sampling method is proposed. Firstly, the idea of hierarchy and degree distribution are adopted, and the k-means clustering algorithm is used to determine the value of the number of layers; secondly, combining the accuracy degree distribution to determine the boundary value between each hierarchical network; thirdly, sampling is carried out not only by taking the degree of the current node, the number of common neighbors between the current node and its neighbors, but the clustering coefficient of these neighbors into consideration at each layer. Finally, on eight real networks and one synthetic network, NCHRW and existing algorithms are compared from six aspects of degree distribution, density, average degree, average clustering coefficient, transitivity and sampling network visualization. The results show that the proposed NCHRW method is significantly better than other nine traditional sampling algorithms in terms of degree distribution, density and average degree, the topology properties of the network can be preserved very well.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00354-022-00179-x", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053619", 
            "issn": [
              "0288-3635", 
              "1882-7055"
            ], 
            "name": "New Generation Computing", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "40"
          }
        ], 
        "keywords": [
          "degree distribution", 
          "clustering coefficient", 
          "traditional sampling algorithms", 
          "random walk", 
          "low-degree nodes", 
          "topology properties", 
          "average clustering coefficient", 
          "sampling algorithm", 
          "high-degree nodes", 
          "boundary values", 
          "average degree", 
          "real networks", 
          "synthetic networks", 
          "number of layers", 
          "hierarchical network", 
          "common neighbors", 
          "algorithm", 
          "k-means clustering algorithm", 
          "clustering algorithm", 
          "current node", 
          "idea of hierarchy", 
          "neighbors", 
          "coefficient", 
          "distribution", 
          "network", 
          "walk", 
          "nodes", 
          "sampling method", 
          "problem", 
          "sampling", 
          "density", 
          "network visualization", 
          "number", 
          "transitivity", 
          "terms", 
          "properties", 
          "layer", 
          "hierarchy", 
          "values", 
          "idea", 
          "degree", 
          "consideration", 
          "results", 
          "aspects", 
          "visualization", 
          "method"
        ], 
        "name": "Complex Network Hierarchical Sampling Method Combining Node Neighborhood Clustering Coefficient with Random Walk", 
        "pagination": "765-807", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1149412255"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00354-022-00179-x"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00354-022-00179-x", 
          "https://app.dimensions.ai/details/publication/pub.1149412255"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-12-01T06:44", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_936.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00354-022-00179-x"
      }
    ]
     

    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/s00354-022-00179-x'

    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/s00354-022-00179-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00354-022-00179-x'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00354-022-00179-x'


     

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

    156 TRIPLES      21 PREDICATES      77 URIs      62 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00354-022-00179-x schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nb03f22fa611d4ac18b8476882699a4c7
    4 schema:citation sg:pub.10.1007/11422778_27
    5 sg:pub.10.1007/978-3-030-10767-3
    6 sg:pub.10.1007/978-3-030-36718-3_1
    7 sg:pub.10.1007/s10618-018-0587-5
    8 sg:pub.10.1007/s13278-016-0371-8
    9 sg:pub.10.1038/srep08665
    10 sg:pub.10.1140/epjb/e2004-00316-5
    11 schema:datePublished 2022-07-10
    12 schema:datePublishedReg 2022-07-10
    13 schema:description Aiming at the problem of over-sampling for high-degree nodes and low-degree nodes in current sampling algorithms, a node Neighborhood Clustering coefficient Hierarchical Random Walk (NCHRW) sampling method is proposed. Firstly, the idea of hierarchy and degree distribution are adopted, and the k-means clustering algorithm is used to determine the value of the number of layers; secondly, combining the accuracy degree distribution to determine the boundary value between each hierarchical network; thirdly, sampling is carried out not only by taking the degree of the current node, the number of common neighbors between the current node and its neighbors, but the clustering coefficient of these neighbors into consideration at each layer. Finally, on eight real networks and one synthetic network, NCHRW and existing algorithms are compared from six aspects of degree distribution, density, average degree, average clustering coefficient, transitivity and sampling network visualization. The results show that the proposed NCHRW method is significantly better than other nine traditional sampling algorithms in terms of degree distribution, density and average degree, the topology properties of the network can be preserved very well.
    14 schema:genre article
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N11bd6ee818b144059307304b547904b0
    17 Ndb4156cf1aae4f7fb70667acc9b0ab22
    18 sg:journal.1053619
    19 schema:keywords algorithm
    20 aspects
    21 average clustering coefficient
    22 average degree
    23 boundary values
    24 clustering algorithm
    25 clustering coefficient
    26 coefficient
    27 common neighbors
    28 consideration
    29 current node
    30 degree
    31 degree distribution
    32 density
    33 distribution
    34 hierarchical network
    35 hierarchy
    36 high-degree nodes
    37 idea
    38 idea of hierarchy
    39 k-means clustering algorithm
    40 layer
    41 low-degree nodes
    42 method
    43 neighbors
    44 network
    45 network visualization
    46 nodes
    47 number
    48 number of layers
    49 problem
    50 properties
    51 random walk
    52 real networks
    53 results
    54 sampling
    55 sampling algorithm
    56 sampling method
    57 synthetic networks
    58 terms
    59 topology properties
    60 traditional sampling algorithms
    61 transitivity
    62 values
    63 visualization
    64 walk
    65 schema:name Complex Network Hierarchical Sampling Method Combining Node Neighborhood Clustering Coefficient with Random Walk
    66 schema:pagination 765-807
    67 schema:productId N8ecc9d6155684b989037c0974c665463
    68 Nc129f668119848f4a861371e7308fbec
    69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149412255
    70 https://doi.org/10.1007/s00354-022-00179-x
    71 schema:sdDatePublished 2022-12-01T06:44
    72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    73 schema:sdPublisher Nfb4b25148968431ab15552c55ee31da3
    74 schema:url https://doi.org/10.1007/s00354-022-00179-x
    75 sgo:license sg:explorer/license/
    76 sgo:sdDataset articles
    77 rdf:type schema:ScholarlyArticle
    78 N11bd6ee818b144059307304b547904b0 schema:volumeNumber 40
    79 rdf:type schema:PublicationVolume
    80 N6a16a9ef27834d4390a65aef7f26bb7a rdf:first N8d4136638de5457cb1ec25f72a32f8ac
    81 rdf:rest N9c62db1c813645c5a4a011195a7cc92d
    82 N8d4136638de5457cb1ec25f72a32f8ac schema:affiliation grid-institutes:grid.411594.c
    83 schema:familyName Zhang
    84 schema:givenName Mengyao
    85 rdf:type schema:Person
    86 N8ecc9d6155684b989037c0974c665463 schema:name dimensions_id
    87 schema:value pub.1149412255
    88 rdf:type schema:PropertyValue
    89 N9c62db1c813645c5a4a011195a7cc92d rdf:first sg:person.012703226440.09
    90 rdf:rest Nc9db766d4d49410a867b608c6b7f5ea6
    91 Nb03f22fa611d4ac18b8476882699a4c7 rdf:first sg:person.012552614265.22
    92 rdf:rest N6a16a9ef27834d4390a65aef7f26bb7a
    93 Nc129f668119848f4a861371e7308fbec schema:name doi
    94 schema:value 10.1007/s00354-022-00179-x
    95 rdf:type schema:PropertyValue
    96 Nc9db766d4d49410a867b608c6b7f5ea6 rdf:first sg:person.016710177037.82
    97 rdf:rest rdf:nil
    98 Ndb4156cf1aae4f7fb70667acc9b0ab22 schema:issueNumber 3
    99 rdf:type schema:PublicationIssue
    100 Nfb4b25148968431ab15552c55ee31da3 schema:name Springer Nature - SN SciGraph project
    101 rdf:type schema:Organization
    102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Information and Computing Sciences
    104 rdf:type schema:DefinedTerm
    105 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Computation Theory and Mathematics
    107 rdf:type schema:DefinedTerm
    108 sg:journal.1053619 schema:issn 0288-3635
    109 1882-7055
    110 schema:name New Generation Computing
    111 schema:publisher Springer Nature
    112 rdf:type schema:Periodical
    113 sg:person.012552614265.22 schema:affiliation grid-institutes:grid.411594.c
    114 schema:familyName Liu
    115 schema:givenName Xiaoyang
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012552614265.22
    117 rdf:type schema:Person
    118 sg:person.012703226440.09 schema:affiliation grid-institutes:grid.10438.3e
    119 schema:familyName Fiumara
    120 schema:givenName Giacomo
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012703226440.09
    122 rdf:type schema:Person
    123 sg:person.016710177037.82 schema:affiliation grid-institutes:grid.10438.3e
    124 schema:familyName De Meo
    125 schema:givenName Pasquale
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016710177037.82
    127 rdf:type schema:Person
    128 sg:pub.10.1007/11422778_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012664505
    129 https://doi.org/10.1007/11422778_27
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-030-10767-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111703242
    132 https://doi.org/10.1007/978-3-030-10767-3
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-030-36718-3_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1123259327
    135 https://doi.org/10.1007/978-3-030-36718-3_1
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/s10618-018-0587-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106430478
    138 https://doi.org/10.1007/s10618-018-0587-5
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/s13278-016-0371-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051247403
    141 https://doi.org/10.1007/s13278-016-0371-8
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1038/srep08665 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021419058
    144 https://doi.org/10.1038/srep08665
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1140/epjb/e2004-00316-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007936830
    147 https://doi.org/10.1140/epjb/e2004-00316-5
    148 rdf:type schema:CreativeWork
    149 grid-institutes:grid.10438.3e schema:alternateName Department of Ancient and Modern Civilizations, University of Messina, V.Le G. Palatucci, 25, 98166, Messina, Italy
    150 MIFT Department, University of Messina, V.Le F. Stagno D’Alcontres, 31, 98166, Messina, Italy
    151 schema:name Department of Ancient and Modern Civilizations, University of Messina, V.Le G. Palatucci, 25, 98166, Messina, Italy
    152 MIFT Department, University of Messina, V.Le F. Stagno D’Alcontres, 31, 98166, Messina, Italy
    153 rdf:type schema:Organization
    154 grid-institutes:grid.411594.c schema:alternateName School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China
    155 schema:name School of Computer Science and Engineering, Chongqing University of Technology, 400054, Chongqing, China
    156 rdf:type schema:Organization
     




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


    ...