mdh.sePublikationer
Ändra sökning
Länk till posten
Permanent länk

Direktlänk
BETA
Abola, Benard
Publikationer (4 of 4) Visa alla publikationer
Abola, B., Biganda, P., Engström, C., Anguzu, C., Mango, J. M., Kakuba, G. & Silvestrov, S. (2019). A Variant of Updating Page Rank in Evolving Tree graphs. In: Christos H. Skiadas (Ed.), Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019: . Paper presented at ASMDA2019, 18th Applied Stochastic Models and Data Analysis International Conference (pp. 31-49). ISAST: International Society for the Advancement of Science and Technology
Öppna denna publikation i ny flik eller fönster >>A Variant of Updating Page Rank in Evolving Tree graphs
Visa övriga...
2019 (Engelska)Ingår i: Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019 / [ed] Christos H. Skiadas, ISAST: International Society for the Advancement of Science and Technology , 2019, s. 31-49Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

PageRank update refers to the process of computing new PageRank values after change(s) (addition or removal of links/vertices) has occurred in real life networks. The purpose of the updating is to avoid recalculating the values from scratch. To efficiently carry out the update, we consider PageRank as the expected number of visits to target vertex if multiple random walks are performed, starting at each vertex once and weighing each of these walks by a weight value. Hence, it might be looked at as updating non-normalised PageRank. In the proposed approach, a scaled adjacency matrix is sequentially updated after every change and the levels of the vertices being updated as well. This enables sets of internal and sink vertices dependent on their roots or parents, thus vector-vector product can be performed sequentially since there are no infinite steps from one vertex to the other.

Ort, förlag, år, upplaga, sidor
ISAST: International Society for the Advancement of Science and Technology, 2019
Nyckelord
PageRank, randomwalk, graph, networks.
Nationell ämneskategori
Sannolikhetsteori och statistik Beräkningsmatematik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
urn:nbn:se:mdh:diva-47083 (URN)978-618-5180-33-1 (ISBN)
Konferens
ASMDA2019, 18th Applied Stochastic Models and Data Analysis International Conference
Forskningsfinansiär
Sida - Styrelsen för internationellt utvecklingssamarbete
Tillgänglig från: 2020-02-20 Skapad: 2020-02-20 Senast uppdaterad: 2020-02-24Bibliografiskt granskad
Abola, B., Biganda, P., Silvestrov, D., Silvestrov, S., Mango, J. & Kakuba, G. (2019). Nonlinearly  Perturbed Markov Chains  and  Information Networks. In: Christos H. Skiadas (Ed.), Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019: . Paper presented at ASMDA2019, 18th Applied Stochastic Models and Data Analysis International Conference (pp. 51-79). ISAST: International Society for the Advancement of Science and Technology
Öppna denna publikation i ny flik eller fönster >>Nonlinearly  Perturbed Markov Chains  and  Information Networks
Visa övriga...
2019 (Engelska)Ingår i: Proceedings of 18th Applied Stochastic Models and Data Analysis International Conference with the Demographics 2019 Workshop, Florence, Italy: 11-14 June, 2019 / [ed] Christos H. Skiadas, ISAST: International Society for the Advancement of Science and Technology , 2019, s. 51-79Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

The paper is devoted to studies of perturbed Markov chains commonly used for description of information networks. In such models, the matrix of transition probabilities for the corresponding Markov chain is usually regularised by adding  a special damping matrix multiplied by a small damping (perturbation) parameter ε. In this paper, we present results of the detailed perturbation analysis of Markov chains with damping component and numerical experiments supporting and illustrating the results of this perturbation analysis.

Ort, förlag, år, upplaga, sidor
ISAST: International Society for the Advancement of Science and Technology, 2019
Nyckelord
Markov chain, Damping component, Information network, Regular perturbation, Singular perturbation, Stationary distribution, Asymptotic expansion, Rate of convergence, Coupling, Ergodic theorem, Triangular array mode
Nationell ämneskategori
Sannolikhetsteori och statistik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
urn:nbn:se:mdh:diva-47082 (URN)978-618-5180-33-1 (ISBN)
Konferens
ASMDA2019, 18th Applied Stochastic Models and Data Analysis International Conference
Forskningsfinansiär
Sida - Styrelsen för internationellt utvecklingssamarbete
Tillgänglig från: 2020-02-20 Skapad: 2020-02-20 Senast uppdaterad: 2020-02-24Bibliografiskt granskad
Abola, B., Biganda, P., Engström, C., Mango, J. M., Kakuba, G. & Silvestrov, S. (2018). PageRank in evolving tree graphs. In: Sergei Silvestrov, Anatoliy Malyarenko, Milica Rančić (Ed.), Stochastic Processes and Applications: SPAS2017, Västerås and Stockholm, Sweden, October 4-6, 2017. Paper presented at International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789 (pp. 375-390). Paper presented at International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789. Springer, 271
Öppna denna publikation i ny flik eller fönster >>PageRank in evolving tree graphs
Visa övriga...
2018 (Engelska)Ingår i: Stochastic Processes and Applications: SPAS2017, Västerås and Stockholm, Sweden, October 4-6, 2017 / [ed] Sergei Silvestrov, Anatoliy Malyarenko, Milica Rančić, Springer, 2018, Vol. 271, s. 375-390Kapitel i bok, del av antologi (Refereegranskat)
Abstract [en]

In this article, we study how PageRank can be updated in an evolving tree graph. We are interested in finding how ranks of the graph can be updated simultaneously and effectively using previous ranks without resorting to iterative methods such as the Jacobi or Power method. We demonstrate and discuss how PageRank can be updated when a leaf is added to a tree, at least one leaf is added to a vertex with at least one outgoing edge, an edge added to vertices at the same level and forward edge is added in a tree graph. The results of this paper provide new insights and applications of standard partitioning of vertices of the graph into levels using breadth-first search algorithm. Then, one determines PageRanks as the expected numbers of random walk starting from any vertex in the graph. We noted that time complexity of the proposed method is linear, which is quite good. Also, it is important to point out that the types of vertex play essential role in updating of PageRank.

Ort, förlag, år, upplaga, sidor
Springer, 2018
Serie
Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009 ; 271
Nyckelord
Breadth-first search, Forward edge, PageRank, Random walk, Tree, Forestry, Graph theory, Iterative methods, Random processes, Stochastic systems, Trees (mathematics)
Nationell ämneskategori
Beräkningsmatematik Sannolikhetsteori och statistik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
urn:nbn:se:mdh:diva-41833 (URN)10.1007/978-3-030-02825-1_16 (DOI)2-s2.0-85058567338 (Scopus ID)978-3-030-02824-4 (ISBN)
Konferens
International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789
Tillgänglig från: 2018-12-27 Skapad: 2018-12-27 Senast uppdaterad: 2018-12-31Bibliografiskt granskad
Biganda, P., Abola, B., Engström, C., Mango, J. M., Kakuba, G. & Silvestrov, S. (2018). Traditional and lazy pageranks for a line of nodes connected with complete graphs. In: Sergei Silvestrov, Anatoliy Malyarenko, Milica Rančić (Ed.), Stochastic Processes and Applications: SPAS2017, Västerås and Stockholm, Sweden, October 4-6, 2017. Paper presented at International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789 (pp. 391-412). Paper presented at International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789. Springer, 271
Öppna denna publikation i ny flik eller fönster >>Traditional and lazy pageranks for a line of nodes connected with complete graphs
Visa övriga...
2018 (Engelska)Ingår i: Stochastic Processes and Applications: SPAS2017, Västerås and Stockholm, Sweden, October 4-6, 2017 / [ed] Sergei Silvestrov, Anatoliy Malyarenko, Milica Rančić, Springer, 2018, Vol. 271, s. 391-412Kapitel i bok, del av antologi (Refereegranskat)
Abstract [en]

PageRank was initially defined by S. Brin and L. Page for the purpose of measuring the importance of web pages (nodes) based on the structure of links between them. Due to existence of diverse methods of random walk on the graph, variants of PageRank now exists. They include traditional (or normal) PageRank due to normal random walk and Lazy PageRank due to lazy random walk on a graph. In this article, we establish how the two variants of PageRank changes when complete graphs are connected to a line of nodes whose links between the nodes are in one direction. Explicit formulae for the two variants of PageRank are presented. We have noted that the ranks on a line graph are the same except their numerical values which differ. Further, we have observed that both normal random walk and lazy random walk on complete graphs spend almost the same time at each node.

Ort, förlag, år, upplaga, sidor
Springer, 2018
Serie
Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009
Nyckelord
Graph, Lazy PageRank, PageRank, Random walk, Random processes, Stochastic systems, Websites, Complete graphs, Diverse methods, Explicit formula, Line graph, Numerical values, Graph theory
Nationell ämneskategori
Matematik
Forskningsämne
matematik/tillämpad matematik
Identifikatorer
urn:nbn:se:mdh:diva-41835 (URN)10.1007/978-3-030-02825-1_17 (DOI)2-s2.0-85058552957 (Scopus ID)978-3-030-02824-4 (ISBN)
Konferens
International Conference on “Stochastic Processes and Algebraic Structures – From Theory Towards Applications”, SPAS 2017; Västerås and Stockholm; Sweden; 4 October 2017 through 6 October 2017; Code 221789
Tillgänglig från: 2018-12-27 Skapad: 2018-12-27 Senast uppdaterad: 2018-12-31Bibliografiskt granskad
Organisationer

Sök vidare i DiVA

Visa alla publikationer