mdh.sePublikationer
Ä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
A componentwise PageRank algorithm
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (Mathematics and Applied Mathematics)ORCID-id: 0000-0002-1624-5147
Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, Utbildningsvetenskap och Matematik. (Mathematics and Applied Mathematics)ORCID-id: 0000-0003-4554-6528
2015 (Engelska)Ingår i: ASMDA 2015 Proceedings: 16th Applied Stochastic Models and Data Analysis International Conference with 4th Demographics 2015 Workshop / [ed] Christos H Skiadas, ISAST: International Society for the Advancement of Science and Technology , 2015, s. 185-198Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

In this article we will take a look at a variant of the PageRank algorithminitially used by S. Brinn and L. Page to rank homepages on the Internet. The aim ofthe article is to see how we can use the topological structure of the graph to speed upcalculations of PageRank without doing any additional approximations. We will seethat by considering a non-normalized version of PageRank it is easy to see how wecan handle dierent types of vertices or strongly connected components in the graphmore eciently. Using this we propose two PageRank algorithms, one similar to theLumping algorithm proposed by Qing et al which handles certain types of verticesfaster and last another PageRank algorithm which can handle more types of verticesas well as strongly connected components more eectively. In the last sections we willlook at some specic types of components as well as verifying the time complexity ofthe algorithm.

Ort, förlag, år, upplaga, sidor
ISAST: International Society for the Advancement of Science and Technology , 2015. s. 185-198
Nyckelord [en]
PageRank, strongly connected component, random walk .
Nationell ämneskategori
Matematik Beräkningsmatematik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
URN: urn:nbn:se:mdh:diva-30004ISBN: 978-618-5180-05-8 (tryckt)OAI: oai:DiVA.org:mdh-30004DiVA, id: diva2:885240
Konferens
16th Applied Stochastic Models and Data Analysis International Conference (ASMDA2015) with Demographics 2015 Workshop, 30 June – 4 July 2015, University of Piraeus, Greece
Tillgänglig från: 2015-12-18 Skapad: 2015-12-18 Senast uppdaterad: 2016-10-24Bibliografiskt granskad
Ingår i avhandling
1. PageRank in Evolving Networks and Applications of Graphs in Natural Language Processing and Biology
Öppna denna publikation i ny flik eller fönster >>PageRank in Evolving Networks and Applications of Graphs in Natural Language Processing and Biology
2016 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This thesis is dedicated to the use of graph based methods applied to ranking problems on the Web-graph and applications in natural language processing and biology.

Chapter 2-4 of this thesis is about PageRank and its use in the ranking of home pages on the Internet for use in search engines. PageRank is based on the assumption that a web page should be high ranked if it is linked to by many other pages and/or by other important pages. This is modelled as the stationary distribution of a random walk on the Web-graph.

Due to the large size and quick growth of the Internet it is important to be able to calculate this ranking very efficiently. One of the main topics of this thesis is how this can be made more efficiently, mainly by considering specific types of subgraphs and how PageRank can be calculated or updated for those type of graph structures. In particular we will consider the graph partitioned into strongly connected components and how this partitioning can be utilized.

Chapter 5-7 is dedicated to graph based methods and their application to problems in Natural language processing. Specifically given a collection of texts (corpus) we will compare different clustering methods applied to Pharmacovigilance terms (5), graph based models for the identification of semantic relations between biomedical words (6) and modifications of CValue for the annotation of terms in a corpus.

In Chapter 8-9 we look at biological networks and the application of graph centrality measures for the identification of cancer genes. Specifically in (8) we give a review over different centrality measures and their application to finding cancer genes in biological networks and in (9) we look at how well the centrality of vertices in the true network is preserved in networks generated from experimental data.

Ort, förlag, år, upplaga, sidor
Västerås: Mälardalen University, 2016
Serie
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 217
Nationell ämneskategori
Matematik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
urn:nbn:se:mdh:diva-33459 (URN)978-91-7485-298-1 (ISBN)
Disputation
2016-12-08, Kappa, Mälardalens högskola, Västerås, 13:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2016-10-24 Skapad: 2016-10-24 Senast uppdaterad: 2016-11-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Engström, ChristopherSilvestrov, Sergei

Sök vidare i DiVA

Av författaren/redaktören
Engström, ChristopherSilvestrov, Sergei
Av organisationen
Utbildningsvetenskap och Matematik
MatematikBeräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 223 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