Patterns and anomalies in k-cores of real-world graphs with applications

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 63
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorShin, Kijungko
dc.contributor.authorEliassi-Rad, Tinako
dc.contributor.authorFaloutsos, Christosko
dc.date.accessioned2019-03-04T10:55:45Z-
dc.date.available2019-03-04T10:55:45Z-
dc.date.created2019-03-04-
dc.date.issued2018-03-
dc.identifier.citationKNOWLEDGE AND INFORMATION SYSTEMS, v.54, no.3, pp.677 - 710-
dc.identifier.issn0219-1377-
dc.identifier.urihttp://hdl.handle.net/10203/250513-
dc.description.abstractHow do the k-core structures of real-world graphs look like? What are the common patterns and the anomalies? How can we exploit them for applications? A k-core is the maximal subgraph in which all vertices have degree at least k. This concept has been applied to such diverse areas as hierarchical structure analysis, graph visualization, and graph clustering. Here, we explore pervasive patterns related to k-cores and emerging in graphs from diverse domains. Our discoveries are: (1) Mirror Pattern: coreness (i.e., maximum k such that each vertex belongs to the k-core) is strongly correlated with degree. (2) Core-Triangle Pattern: degeneracy (i.e., maximum k such that the k-core exists) obeys a 3-to-1 power-law with respect to the count of triangles. (3) Structured Core Pattern: degeneracy-cores are not cliques but have non-trivial structures such as core-periphery and communities. Our algorithmic contributions show the usefulness of these patterns. (1) Core-A, which measures the deviation from Mirror Pattern, successfully spots anomalies in real-world graphs, (2) Core-D, a single-pass streaming algorithm based on Core-Triangle Pattern, accurately estimates degeneracy up to 12 faster than its competitor. (3) Core-S, inspired by Structured Core Pattern, identifies influential spreaders up to 17 faster than its competitors with comparable accuracy.-
dc.languageEnglish-
dc.publisherSPRINGER LONDON LTD-
dc.titlePatterns and anomalies in k-cores of real-world graphs with applications-
dc.typeArticle-
dc.identifier.wosid000425010800008-
dc.identifier.scopusid2-s2.0-85025083406-
dc.type.rimsART-
dc.citation.volume54-
dc.citation.issue3-
dc.citation.beginningpage677-
dc.citation.endingpage710-
dc.citation.publicationnameKNOWLEDGE AND INFORMATION SYSTEMS-
dc.identifier.doi10.1007/s10115-017-1077-6-
dc.contributor.localauthorShin, Kijung-
dc.contributor.nonIdAuthorEliassi-Rad, Tina-
dc.contributor.nonIdAuthorFaloutsos, Christos-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorGraph-
dc.subject.keywordAuthork-core-
dc.subject.keywordAuthorDegeneracy-
dc.subject.keywordAuthorInfluential node-
dc.subject.keywordAuthorAnomaly detection-
dc.subject.keywordAuthork-truss-
dc.subject.keywordPlusCOMMUNITY STRUCTURE-
dc.subject.keywordPlusDECOMPOSITION-
dc.subject.keywordPlusNETWORKS-
dc.subject.keywordPlusALGORITHMS-
dc.subject.keywordPlusINTERNET-
dc.subject.keywordPlusCLIQUES-
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0