Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An empirical comparison of algorithms to findcommunities in directed graphs and theirapplication in Web Data Analytics
Department of Mathematics and Computer Science, Physical Sciences and Earth Sciences, University of Messina.
of Ancient and Modern Civilizations, University of Messina.
Department of Mathematics and Computer Science, Physical Sciences and Earth Sciences, University of Messina.
Department of Mathematics and Computer Science, Physical Sciences and Earth Sciences, University of Messina.
Visa övriga samt affilieringar
2017 (Engelska)Ingår i: IEEE Transactions on Big Data, E-ISSN 2332-7790, Vol. 3, nr 3, s. 289-306Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Detecting communities in graphs is a fundamental tool to understand the structure of Web-based systems and predict their evolution. Many community detection algorithms are designed to process undirected graphs (i.e., graphs with bidirectional edges) but many graphs on the Web - e.g. microblogging Web sites, trust networks or the Web graph itself - are often directed. Few community detection algorithms deal with directed graphs but we lack their experimental comparison. In this paper we evaluated some community detection algorithms across accuracy and scalability. A first group of algorithms (Label Propagation and Infomap) are explicitly designed to manage directed graphs while a second group (e.g., WalkTrap) simply ignores edge directionality; finally, a third group of algorithms (e.g., Eigenvector) maps input graphs onto undirected ones and extracts communities from the symmetrized version of the input graph. We ran our tests on both artificial and real graphs and, on artificial graphs, WalkTrap achieved the highest accuracy, closely followed by other algorithms; Label Propagation has outstanding performance in scalability on both artificial and real graphs. The Infomap algorithm showcased the best trade-off between accuracy and computational performance and, therefore, it has to be considered as a promising tool for Web Data Analytics purposes.

Ort, förlag, år, upplaga, sidor
2017. Vol. 3, nr 3, s. 289-306
Nationell ämneskategori
Medieteknik
Forskningsämne
Distribuerade datorsystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-62866DOI: 10.1109/TBDATA.2016.2631512OAI: oai:DiVA.org:ltu-62866DiVA, id: diva2:1086630
Anmärkning

Validerad;2017;Nivå 1;2017-09-21 (inah)

Tillgänglig från: 2017-04-03 Skapad: 2017-04-03 Senast uppdaterad: 2018-01-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Vasilakos, Athanasios
Av organisationen
Datavetenskap
Medieteknik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 245 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf