Top

Social Network Analysis and Mining

Published in:

01-12-2022 | Original Paper

FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes

Authors: Rohith Parjanya Pashikanti, Suman Kundu

Published in: Social Network Analysis and Mining | Issue 1/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The paper presents a new algorithm FPPR which updates PageRanks of a directed network after topological changes in the graphs. The algorithm is capable of regenerating scores on node and link addition/deletion. The changes in the expected value of random surfers are used for updating the scores of the newly added nodes as well as the impacted chain where the nodes/links are added or removed. The complexity of the algorithm for k new node addition is \(\mathcal {O}(k\times d^{(k)}_{avg})\) where \(d^{(k)}_{avg}\) is the average degree of k nodes added. On the other hand for node deletion, the complexity is \(\mathcal {O}(|V_s|+|E_s|)\) where \(V_s\) and \(E_s\) the set of nodes and edges updated using Selective Breath First Update. Extensive experiments have been performed on different synthetic and real-world networks. The experimental result shows that the rank generated by the proposed method is highly correlated with that of the recalculation on changes using the benchmark Power Iteration algorithm.

previous article Political polarization on Twitter during the COVID-19 pandemic: a case study in Brazil

next article The effects of scheduling network models in predictive processes in sports

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Albert Réka, Barabási Albert-László (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47–97MathSciNetCrossRefMATH

Avrachenkov K, Litvak N, Nemirovsky D, Osipova N (2007) Monte Carlo methods in PageRank computation: when one iteration is sufficient. SIAM J Numer Anal 45(2):890–904MathSciNetCrossRefMATH

Bahmani Bahman, Chowdhury Abdur, Goel Ashish (2010) Fast incremental and personalized PageRank. Proc VLDB Endow 4(3):173–184CrossRef

Bautista Esteban, Latapy Matthieu (2022) A local updating algorithm for personalized PageRank via Chebyshev polynomials. Soc Netw Anal Min 12(1):1–11CrossRef

Breyer LA (2002) Markovian page ranking distributions: some theory and simulations. Citeseer

Chien Steve, Dwork Cynthia, Kumar Ravi, Simon Daniel R, Sivakumar D (2004) Link evolution: analysis and algorithms. Internet Math 1:277–304MathSciNetCrossRefMATH

Chuai Y, Zhao J (2020) Anger makes fake news viral online. arXiv:2004.10399

Desikan P, Pathak N, Srivastava J, Kumar V (2005) Incremental page rank computation on evolving graphs. In: Special interest tracks and posters of the 14th international conference on World Wide Web, WWW ’05, New York. Association for Computing Machinery, pp 1094–1095

Erdös P, Rényi A (2011) On the evolution of random graphs. Princeton University Press, pp 38–82

Gupta P, Goel A, Lin J, Sharma A, Wang D, Zadeh R (2013) Wtf: the who to follow service at twitter. In: Proceedings of the 22nd international conference on World Wide Web, WWW ’13, New York. Association for Computing Machinery, pp 505–514

Isham Valerie, Seneta E (1983) Non-negative matrices and Markov chains. J R Stat Soc. Ser A (Gen) 146(2):202CrossRef

Iván Gábor, Grolmusz Vince (2011) When the web meets the cell: using personalized PageRank for analyzing protein interaction networks. Bioinformatics 27(3):405–407CrossRef

Jiang Bin (2009) Ranking spaces for predicting human movement in an urban environment. Int J Geogr Inf Sci 23(7):823–837CrossRef

Kleinberg Jon M (1999) Authoritative sources in a hyperlinked environment. J ACM 46(5):604–632MathSciNetCrossRefMATH

Knuth DE (2014) Art of computer programming. Volume 2: seminumerical algorithms. Addison-Wesley Professional

Langville AN, Meyer CD (2004) Updating PageRank with iterative aggregation. In: Proc. of 13th international world wide web conference, New York, pp 1124–1125

Lempel R, Moran S (2000) Stochastic approach for link-structure analysis (SALSA) and the TKC effect. Comput Netw 33(1):387–401CrossRef

Leskovec Jure, Lang Kevin J, Dasgupta Anirban, Mahoney Michael W (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123MathSciNetCrossRefMATH

Liao Q, Jiang S, Yu M, Yang Y, Li T (2017) Monte Carlo based incremental PageRank on evolving graphs. In: Kim J, Shim K, Cao L, Lee J-G, Lin X, Moon Y-S (eds) Advances in knowledge discovery and data mining. Springer, Cham, pp 356–367

Ohsaka N, Maehara T, Kawarabayashi KI (2015) Efficient PageRank tracking in evolving networks. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp 875–884

Page Lawrence, Brin Sergey, Motwani Rajeev, Winograd Terry (1998) The PageRank citation ranking: bringing order to the web. WWW Internet Web Inf Syst 54(1999–66):1–17

Parjanya R, Kundu S (2022) Fppr: fast pessimistic PageRank for dynamic directed graphs. In: Benito RM, Cherifi C, Cherifi H, Moro E, Rocha LM, Sales-Pardo M (eds) Complex networks and their applications X. Springer, Cham, pp 271–281

Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. In: International semantic Web conference. Springer, pp 351–368

Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI conference on artificial intelligence, AAAI’15. AAAI Press, pp 4292–4293

Salehi O (2007) PageRank algorithm and Monte Carlo methods in PageRank computation. PhD thesis, Bogazici University

Spearman C (1904) The proof and measurement of association between two things. Am J Psychol 15(1):72CrossRef

Tong H, Faloutsos C, Pan JY (2006) Fast random walk with restart and its applications. In: 6th international conference on data mining (ICDM’06). IEEE, pp 613–622

Vargas B (2020) Exploring PageRank algorithms: power iteration and Monte Carlo methods. PhD thesis, California State University, San Marcos

Yoon M, Jin W, Kang U (2018) Fast and accurate random walk with restart on dynamic graphs with guarantees. In: Proceedings of the 2018 World Wide Web Conference, pp 409–418

Zar JH (2005) Spearman rank correlation. In: Encyclopedia of biostatistics. Wiley

Zhan Z, Hu R, Gao X, Huai N (2019) Fast incremental PageRank on dynamic networks. In: Bakaev M, Frasincar F, In-Young K (eds) Proc. of international conference on web engineering, volume 11496 LNCS. Springer, Cham, pp 154–168

Zhou Z (2015) Evaluation of Monte Carlo method in PageRank. PhD thesis, University of Missouri-Columbia

Title: FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes
Authors: Rohith Parjanya Pashikanti
Suman Kundu
Publication date: 01-12-2022
Publisher: Springer Vienna
Published in: Social Network Analysis and Mining / Issue 1/2022
Print ISSN: 1869-5450
Electronic ISSN: 1869-5469
DOI: https://doi.org/10.1007/s13278-022-00968-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2022

Fractional-order rumor propagation model with memory effect

Correction to: Extracting time patterns from the lifespans of TikTok challenges to characterize non‑dangerous and dangerous ones

Analyzing the far-right political action on Twitter: the Chilean constituent process

Evolving friendship? Essential changes, from social networks to artificial companions

Automatically detecting and understanding the perception of COVID-19 vaccination: a middle east case study

An Implementation of Fake News Prevention by Blockchain and Entropy-based Incentive Mechanism

Premium Partner