A Comparative Analysis of Community Detection Algorithms on Artificial Networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-11

AUTHORS

Zhao Yang, René Algesheimer, Claudio J. Tessone

ABSTRACT

Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time. More... »

PAGES

30750

References to SciGraph publications

  • 2016-06-16. Structure and inference in annotated networks in NATURE COMMUNICATIONS
  • 2005-06. Uncovering the overlapping community structure of complex networks in nature and society in NATURE
  • 2015-01. Defining and evaluating network communities based on ground-truth in KNOWLEDGE AND INFORMATION SYSTEMS
  • 2005. Computing Communities in Large Networks Using Random Walks in COMPUTER AND INFORMATION SCIENCES - ISCIS 2005
  • 2012-05. Community detection in Social Media in DATA MINING AND KNOWLEDGE DISCOVERY
  • 2009-11. The map equation in THE EUROPEAN PHYSICAL JOURNAL SPECIAL TOPICS
  • 2009. A Comparison of Community Detection Algorithms on Artificial Networks in DISCOVERY SCIENCE
  • 1984-03. Optimization by simulated annealing: Quantitative studies in JOURNAL OF STATISTICAL PHYSICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1038/srep30750

    DOI

    http://dx.doi.org/10.1038/srep30750

    DIMENSIONS

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

    PUBMED

    https://www.ncbi.nlm.nih.gov/pubmed/27476470


    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": "University of Zurich", 
              "id": "https://www.grid.ac/institutes/grid.7400.3", 
              "name": [
                "URPP Social Networks, University of Z\u00fcrich, Andreasstrasse 15, CH-8050 Z\u00fcrich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Zhao", 
            "id": "sg:person.07737724635.10", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07737724635.10"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Zurich", 
              "id": "https://www.grid.ac/institutes/grid.7400.3", 
              "name": [
                "URPP Social Networks, University of Z\u00fcrich, Andreasstrasse 15, CH-8050 Z\u00fcrich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Algesheimer", 
            "givenName": "Ren\u00e9", 
            "id": "sg:person.010553324443.58", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010553324443.58"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Zurich", 
              "id": "https://www.grid.ac/institutes/grid.7400.3", 
              "name": [
                "URPP Social Networks, University of Z\u00fcrich, Andreasstrasse 15, CH-8050 Z\u00fcrich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tessone", 
            "givenName": "Claudio J.", 
            "id": "sg:person.01354675602.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354675602.03"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1103/physreve.90.062805", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000410295"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.90.062805", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000410295"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/ncomms11863", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002100914", 
              "https://doi.org/10.1038/ncomms11863"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.0400054101", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004043513"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11569596_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004698403", 
              "https://doi.org/10.1007/11569596_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11569596_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004698403", 
              "https://doi.org/10.1007/11569596_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.0611034104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006029486"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.physrep.2005.10.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006977567"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-04747-3_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008331848", 
              "https://doi.org/10.1007/978-3-642-04747-3_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.286.5439.509", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010080128"
            ], 
            "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.1103/physreve.68.065103", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012830078"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.68.065103", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012830078"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1371/journal.pone.0002449", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016130068"
            ], 
            "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.1016/0378-8733(78)90021-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016916901"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10618-011-0224-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017664270", 
              "https://doi.org/10.1007/s10618-011-0224-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2005/09/p09008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017878564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2005/09/p09008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017878564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2008/05/p05001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018332663"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.122653799", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018411012"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01009452", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019054075", 
              "https://doi.org/10.1007/bf01009452"
            ], 
            "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": "https://doi.org/10.1103/physreve.74.036104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021120999"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.74.036104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021120999"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2006/11/p11010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025281123"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2015/11/p11006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026947848"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.0605965104", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028061681"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.76.036106", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029327122"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.76.036106", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029327122"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1371/journal.pone.0011976", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030639307"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nature03607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032155732", 
              "https://doi.org/10.1038/nature03607"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nature03607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032155732", 
              "https://doi.org/10.1038/nature03607"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/nature03607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032155732", 
              "https://doi.org/10.1038/nature03607"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.70.066111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035552384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.70.066111", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035552384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.74.016110", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036285600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.74.016110", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036285600"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.056117", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036660715"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.056117", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036660715"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.036115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036854670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.036115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036854670"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/1742-5468/2008/10/p10008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037912856"
            ], 
            "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": "sg:pub.10.1140/epjst/e2010-01179-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041361554", 
              "https://doi.org/10.1140/epjst/e2010-01179-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.016118", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046173962"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.80.016118", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046173962"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1553374.1553511", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048906649"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.3240060204", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051332521"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1086/jar.33.4.3629752", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1058909178"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/revmodphys.54.235", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060839004"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/revmodphys.54.235", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060839004"
            ], 
            "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.1109/nsw.2011.6004645", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094592605"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icif.2010.5712065", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094646785"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/asonam.2010.70", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095560216"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-11", 
        "datePublishedReg": "2016-11-01", 
        "description": "Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1038/srep30750", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1045337", 
            "issn": [
              "2045-2322"
            ], 
            "name": "Scientific Reports", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "name": "A Comparative Analysis of Community Detection Algorithms on Artificial Networks", 
        "pagination": "30750", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6f4ac7401663620d4d81a9a4870d4a75b80173b046e13723db36afe7c69afe32"
            ]
          }, 
          {
            "name": "pubmed_id", 
            "type": "PropertyValue", 
            "value": [
              "27476470"
            ]
          }, 
          {
            "name": "nlm_unique_id", 
            "type": "PropertyValue", 
            "value": [
              "101563288"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1038/srep30750"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1023359647"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1038/srep30750", 
          "https://app.dimensions.ai/details/publication/pub.1023359647"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T23:31", 
        "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/0000000001_0000000264/records_8693_00000550.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://www.nature.com/articles/srep30750"
      }
    ]
     

    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.1038/srep30750'

    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.1038/srep30750'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1038/srep30750'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1038/srep30750'


     

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

    216 TRIPLES      21 PREDICATES      71 URIs      21 LITERALS      9 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1038/srep30750 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N59277a5420c74bfda4bc4454dba871cb
    4 schema:citation sg:pub.10.1007/11569596_31
    5 sg:pub.10.1007/978-3-642-04747-3_20
    6 sg:pub.10.1007/bf01009452
    7 sg:pub.10.1007/s10115-013-0693-z
    8 sg:pub.10.1007/s10618-011-0224-z
    9 sg:pub.10.1038/nature03607
    10 sg:pub.10.1038/ncomms11863
    11 sg:pub.10.1140/epjst/e2010-01179-1
    12 https://doi.org/10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2
    13 https://doi.org/10.1002/rsa.3240060204
    14 https://doi.org/10.1016/0378-8733(78)90021-7
    15 https://doi.org/10.1016/j.physrep.2005.10.009
    16 https://doi.org/10.1016/j.physrep.2009.11.002
    17 https://doi.org/10.1073/pnas.0400054101
    18 https://doi.org/10.1073/pnas.0605965104
    19 https://doi.org/10.1073/pnas.0611034104
    20 https://doi.org/10.1073/pnas.122653799
    21 https://doi.org/10.1086/jar.33.4.3629752
    22 https://doi.org/10.1088/1742-5468/2005/09/p09008
    23 https://doi.org/10.1088/1742-5468/2006/11/p11010
    24 https://doi.org/10.1088/1742-5468/2008/05/p05001
    25 https://doi.org/10.1088/1742-5468/2008/10/p10008
    26 https://doi.org/10.1088/1742-5468/2015/11/p11006
    27 https://doi.org/10.1103/physreve.68.065103
    28 https://doi.org/10.1103/physreve.70.066111
    29 https://doi.org/10.1103/physreve.74.016110
    30 https://doi.org/10.1103/physreve.74.036104
    31 https://doi.org/10.1103/physreve.76.036106
    32 https://doi.org/10.1103/physreve.78.046110
    33 https://doi.org/10.1103/physreve.80.016118
    34 https://doi.org/10.1103/physreve.80.036115
    35 https://doi.org/10.1103/physreve.80.056117
    36 https://doi.org/10.1103/physreve.90.062805
    37 https://doi.org/10.1103/revmodphys.54.235
    38 https://doi.org/10.1109/asonam.2010.70
    39 https://doi.org/10.1109/icif.2010.5712065
    40 https://doi.org/10.1109/nsw.2011.6004645
    41 https://doi.org/10.1126/science.286.5439.509
    42 https://doi.org/10.1137/s003614450342480
    43 https://doi.org/10.1145/1553374.1553511
    44 https://doi.org/10.1371/journal.pone.0002449
    45 https://doi.org/10.1371/journal.pone.0011976
    46 schema:datePublished 2016-11
    47 schema:datePublishedReg 2016-11-01
    48 schema:description Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.
    49 schema:genre research_article
    50 schema:inLanguage en
    51 schema:isAccessibleForFree true
    52 schema:isPartOf N7557c326e34d4980baa521f57c6a21b0
    53 N9b2d56a71ed74b7a8974c6d325041581
    54 sg:journal.1045337
    55 schema:name A Comparative Analysis of Community Detection Algorithms on Artificial Networks
    56 schema:pagination 30750
    57 schema:productId N3b1e65faeee24421a4c392da97deffff
    58 N3f9ea9bdb22b489eade7cdbd93dff6da
    59 N9c9ca1dc914e4f06a5de43018cc65958
    60 Nc499dfe0da7f417a896583555f8d9789
    61 Nf593af6c7877458a98a84501296e6da2
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023359647
    63 https://doi.org/10.1038/srep30750
    64 schema:sdDatePublished 2019-04-10T23:31
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher N58131a11303d49008d96e16d94c9332b
    67 schema:url http://www.nature.com/articles/srep30750
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N3b1e65faeee24421a4c392da97deffff schema:name nlm_unique_id
    72 schema:value 101563288
    73 rdf:type schema:PropertyValue
    74 N3f9ea9bdb22b489eade7cdbd93dff6da schema:name doi
    75 schema:value 10.1038/srep30750
    76 rdf:type schema:PropertyValue
    77 N58131a11303d49008d96e16d94c9332b schema:name Springer Nature - SN SciGraph project
    78 rdf:type schema:Organization
    79 N59277a5420c74bfda4bc4454dba871cb rdf:first sg:person.07737724635.10
    80 rdf:rest Nb4b564fb20b246a8a4d94df535800887
    81 N7557c326e34d4980baa521f57c6a21b0 schema:volumeNumber 6
    82 rdf:type schema:PublicationVolume
    83 N9b2d56a71ed74b7a8974c6d325041581 schema:issueNumber 1
    84 rdf:type schema:PublicationIssue
    85 N9c9ca1dc914e4f06a5de43018cc65958 schema:name readcube_id
    86 schema:value 6f4ac7401663620d4d81a9a4870d4a75b80173b046e13723db36afe7c69afe32
    87 rdf:type schema:PropertyValue
    88 Nb4b564fb20b246a8a4d94df535800887 rdf:first sg:person.010553324443.58
    89 rdf:rest Nf1050b72b97e4871b283b2f814c801fa
    90 Nc499dfe0da7f417a896583555f8d9789 schema:name pubmed_id
    91 schema:value 27476470
    92 rdf:type schema:PropertyValue
    93 Nf1050b72b97e4871b283b2f814c801fa rdf:first sg:person.01354675602.03
    94 rdf:rest rdf:nil
    95 Nf593af6c7877458a98a84501296e6da2 schema:name dimensions_id
    96 schema:value pub.1023359647
    97 rdf:type schema:PropertyValue
    98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Information and Computing Sciences
    100 rdf:type schema:DefinedTerm
    101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    102 schema:name Computation Theory and Mathematics
    103 rdf:type schema:DefinedTerm
    104 sg:journal.1045337 schema:issn 2045-2322
    105 schema:name Scientific Reports
    106 rdf:type schema:Periodical
    107 sg:person.010553324443.58 schema:affiliation https://www.grid.ac/institutes/grid.7400.3
    108 schema:familyName Algesheimer
    109 schema:givenName René
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010553324443.58
    111 rdf:type schema:Person
    112 sg:person.01354675602.03 schema:affiliation https://www.grid.ac/institutes/grid.7400.3
    113 schema:familyName Tessone
    114 schema:givenName Claudio J.
    115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01354675602.03
    116 rdf:type schema:Person
    117 sg:person.07737724635.10 schema:affiliation https://www.grid.ac/institutes/grid.7400.3
    118 schema:familyName Yang
    119 schema:givenName Zhao
    120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07737724635.10
    121 rdf:type schema:Person
    122 sg:pub.10.1007/11569596_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004698403
    123 https://doi.org/10.1007/11569596_31
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-642-04747-3_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008331848
    126 https://doi.org/10.1007/978-3-642-04747-3_20
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/bf01009452 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019054075
    129 https://doi.org/10.1007/bf01009452
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/s10115-013-0693-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1041186630
    132 https://doi.org/10.1007/s10115-013-0693-z
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/s10618-011-0224-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1017664270
    135 https://doi.org/10.1007/s10618-011-0224-z
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1038/nature03607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032155732
    138 https://doi.org/10.1038/nature03607
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1038/ncomms11863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002100914
    141 https://doi.org/10.1038/ncomms11863
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1140/epjst/e2010-01179-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041361554
    144 https://doi.org/10.1140/epjst/e2010-01179-1
    145 rdf:type schema:CreativeWork
    146 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
    147 rdf:type schema:CreativeWork
    148 https://doi.org/10.1002/rsa.3240060204 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051332521
    149 rdf:type schema:CreativeWork
    150 https://doi.org/10.1016/0378-8733(78)90021-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016916901
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1016/j.physrep.2005.10.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006977567
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1016/j.physrep.2009.11.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020482279
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1073/pnas.0400054101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004043513
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1073/pnas.0605965104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028061681
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1073/pnas.0611034104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006029486
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1073/pnas.122653799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018411012
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1086/jar.33.4.3629752 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058909178
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1088/1742-5468/2005/09/p09008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017878564
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1088/1742-5468/2006/11/p11010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025281123
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1088/1742-5468/2008/05/p05001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018332663
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1088/1742-5468/2008/10/p10008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037912856
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1088/1742-5468/2015/11/p11006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026947848
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1103/physreve.68.065103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012830078
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1103/physreve.70.066111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035552384
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1103/physreve.74.016110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036285600
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1103/physreve.74.036104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021120999
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1103/physreve.76.036106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029327122
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1103/physreve.78.046110 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016699541
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1103/physreve.80.016118 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046173962
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1103/physreve.80.036115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036854670
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1103/physreve.80.056117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036660715
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1103/physreve.90.062805 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000410295
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1103/revmodphys.54.235 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060839004
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1109/asonam.2010.70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095560216
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1109/icif.2010.5712065 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094646785
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1109/nsw.2011.6004645 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094592605
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1137/s003614450342480 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062877811
    207 rdf:type schema:CreativeWork
    208 https://doi.org/10.1145/1553374.1553511 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048906649
    209 rdf:type schema:CreativeWork
    210 https://doi.org/10.1371/journal.pone.0002449 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016130068
    211 rdf:type schema:CreativeWork
    212 https://doi.org/10.1371/journal.pone.0011976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030639307
    213 rdf:type schema:CreativeWork
    214 https://www.grid.ac/institutes/grid.7400.3 schema:alternateName University of Zurich
    215 schema:name URPP Social Networks, University of Zürich, Andreasstrasse 15, CH-8050 Zürich, Switzerland
    216 rdf:type schema:Organization
     




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


    ...