Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Social Network Analysis and Mining
Erschienen in: Social Network Analysis and Mining 1/2022

01.12.2022 | Original Paper

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

verfasst von: Rohith Parjanya Pashikanti, Suman Kundu

Erschienen in: Social Network Analysis and Mining | Ausgabe 1/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Vorheriger Artikel Political polarization on Twitter during the COVID-19 pandemic: a case study in Brazil
Nächster Artikel The effects of scheduling network models in predictive processes in sports

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
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
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
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
Metadaten
Titel
FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes
verfasst von
Rohith Parjanya Pashikanti
Suman Kundu
Publikationsdatum
01.12.2022
Verlag
Springer Vienna
Erschienen in
Social Network Analysis and Mining / Ausgabe 1/2022
Print ISSN: 1869-5450
Elektronische ISSN: 1869-5469
DOI
https://doi.org/10.1007/s13278-022-00968-8

Weitere Artikel der Ausgabe 1/2022

Social Network Analysis and Mining 1/2022 Zur Ausgabe

Original Article

FA-Net: fused attention-based network for Hindi English code-mixed offensive text classification

Original Article

DeeProBot: a hybrid deep neural network model for social bot detection based on user profile data

Original Article

Ridge count thresholding to uncover coordinated networks during onset of the Covid-19 pandemic

Original Article

Supervised classifiers with TF-IDF features for sentiment analysis of Marathi tweets

Original Article

Analyzing the uncharted territory of monetizing scam Videos on YouTube

Original Article

Credibility aspects’ perceptions of social networks, a survey

Premium Partner

    Bildnachweise