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 Article

A local updating algorithm for personalized PageRank via Chebyshev polynomials

verfasst von: Esteban Bautista, Matthieu Latapy

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 personalized PageRank algorithm is one of the most versatile tools for the analysis of networks. In spite of its ubiquity, maintaining personalized PageRank vectors when the underlying network constantly evolves is still a challenging task. To address this limitation, this work proposes a novel distributed algorithm to locally update personalized PageRank vectors when the graph topology changes. The proposed algorithm is based on the use of Chebyshev polynomials and a novel update equation that encompasses a large family of PageRank-based methods. In particular, the algorithm has the following advantages: (i) it has faster convergence speed than state-of-the-art alternatives for local personalized PageRank updating; and (ii) it can update the solution of recent extensions of personalized PageRank that rely on complex dynamical processes for which no updating algorithms have been developed. Experiments in a real-world temporal network of an autonomous system validate the effectiveness of the proposed algorithm.
Vorheriger Artikel Characterizing the role of bots’ in polarized stance on social media
Nächster Artikel A core-periphery structure-based network embedding approach

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
Page L, Brin S, Motwani R, Winograd T (1999) The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab
Ding C, He X, Husbands P, Zha H, Simon H (2003) Pagerank, hits and a unified framework for link analysis. In: Proceedings of the 2003 SIAM International Conference on Data Mining, pp. 249–253. SIAM
Haveliwala TH (2003) Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Trans Knowl Data Eng 15(4):784–796CrossRef
Andersen R, Chung F, Lang K (2006) Local graph partitioning using pagerank vectors. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 475–486. IEEE
Tabrizi SA, Shakery A, Asadpour M, Abbasi M, Tavallaie MA (2013) Personalized pagerank clustering: A graph clustering algorithm based on random walks. Physica A: Stat Mech Appl 392(22):5772–5785MathSciNetCrossRefMATH
Avrachenkov K, Gonçalves P, Legout A, Sokol M (2012) Classification of content and users in bittorrent by semi-supervised learning methods. In: 2012 8th International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 625–630. IEEE
Merkurjev E, Bertozzi AL, Chung F (2018) A semi-supervised heat kernel pagerank mbo algorithm for data classification. Commun Math Sci 16(5):1241–1265MathSciNetCrossRefMATH
Dostal M, Nykl M, Ježek K (2014) Exploration of document classification with linked data and pagerank. In: Intelligent Distributed Computing VII, pp. 37–43. Springer
Avrachenkov K, Mishenin A, Gonçalves P, Sokol M (2012) Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 966–974. SIAM
Fontugne R, Bautista E, Petrie C, Nomura Y, Abry P, Gonçalves P, Fukuda K, Aben E (2019) Bgp zombies: An analysis of beacons stuck routes. In: International Conference on Passive and Active Network Measurement, pp. 197–209. Springer
Yoon M, Hooi B, Shin K, Faloutsos C (2019) Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 647–657
Yao Z, Mark P, Rabbat M (2012) Anomaly detection using proximity graph and pagerank algorithm. IEEE Trans Inf Forens Secur 7(4):1288–1300CrossRef
Al_Janabi S, Kadiam, N (2019)Recommendation system of big data based on pagerank clustering algorithm. In: International Conference on Big Data and Networks Technologies, pp. 149–171. Springer
Zhang Y, Zhang N, Tang J (2009) A collaborative filtering tag recommendation system based on graph. ECML PKDD discovery challenge, 297–306
Nguyen P, Tomeo P, Di Noia T, Di Sciascio E (2015) An evaluation of simrank and personalized pagerank to build a recommender system for the web of data. In: Proceedings of the 24th International Conference on World Wide Web, pp. 1477–1482
Ipsen IC, Wills RS (2006) Mathematical properties and analysis of google’s pagerank. Bol Soc Esp Mat Apl 34:191–196MathSciNetMATH
Brezinski C, Redivo-Zaglia M (2006) The pagerank vector: properties, computation, approximation, and acceleration. SIAM J Matrix Analy Appl 28(2):551–575MathSciNetCrossRefMATH
Pretto L (2002) A theoretical analysis of google’s pagerank. In: International Symposium on String Processing and Information Retrieval, pp. 131–144. Springer
Bautista E, Abry P, Gonçalves P (2019) L\(^\gamma\)-pagerank for semi-supervised learning. Appl Netw Sci 4(1):1–20CrossRef
De Nigris S, Bautista E, Abry P, Avrachenkov K, Gonçalves P (2017) Fractional graph-based semi-supervised learning. In: 2017 25th European Signal Processing Conference (EUSIPCO), pp. 356–360. IEEE
Mai X, Couillet R (2017) The counterintuitive mechanism of graph-based semi-supervised learning in the big data regime. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2821–2825. IEEE
Zhou X, Belkin M (2011) Semi-supervised learning by higher order regularization. In: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 892–900. JMLR Workshop and Conference Proceedings
Girault B, Gonçalves P, Fleury E, Mor AS (2014) Semi-supervised learning for graph to signal mapping: A graph signal wiener filter interpretation. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1115–1119. IEEE
Haveliwala T (1999) Ecient computation of pagerank. Technical report, Stanford
Fujiwara Y, Nakatsuji M, Yamamuro T, Shiokawa H, Onizuka M (2012) Efficient personalized pagerank with accuracy assurance. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 15–23
Bahmani B, Chakrabarti K, Xin D (2011) Fast personalized pagerank on mapreduce. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pp. 973–984
Maehara T, Akiba T, Iwata Y, Kawarabayashi K-i (2014) Computing personalized pagerank quickly by exploiting graph structures. Proc VLDB Endowment 7(12):1023–1034CrossRef
Avrachenkov K, Litvak N, Nemirovsky D, Osipova N (2007) Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM J Numer Analy 45(2):890–904MathSciNetCrossRefMATH
Ohsaka N, Maehara T, Kawarabayashi K-i (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
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
Zhang H, Lofgren P, Goel A (2016) Approximate personalized pagerank on dynamic graphs. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1315–1324
Yoon M, Gervet T, Hooi B, Faloutsos C (2020) Autonomous graph mining algorithm search with best speed/accuracy trade-off. In: 2020 IEEE International Conference on Data Mining (ICDM), 751–760
Shuman DI, Vandergheynst P, Frossard P (2011) Chebyshev polynomial approximation for distributed signal processing. In: 2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS), pp. 1–8. IEEE
Cheng C, Jiang J, Emirov N, Sun Q (2019) Iterative chebyshev polynomial algorithm for signal denoising on graphs. In: 2019 13th International Conference on Sampling Theory and Applications (SampTA), pp. 1–5. IEEE
Tseng C-C, Lee S-L (2021) Minimax design of graph filter using chebyshev polynomial approximation. IEEE Trans Circ Syst II: Express Briefs 68(5):1630–1634
Tian D, Mansour H, Knyazev A, Vetro A (2014) Chebyshev and conjugate gradient filters for graph image denoising. In: 2014 IEEE International Conference on Multimedia and Expo Workshops (ICMEW), pp. 1–6. IEEE
Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. Adv Neural Inf Process Syst 29:3844–3852
Yan B, Wang G, Yu J, Jin X, Zhang H (2021) Spatial-temporal chebyshev graph neural network for traffic flow prediction in iot-based its. IEEE Internet Things J
Tremblay N, Gonçalves P, Borgnat P (2018) Design of graph filters and filterbanks. In: Cooperative and Graph Signal Processing, pp. 299–324. Elsevier
Giovanidis A, Baynat B, Magnien C, Vendeville A (2021) Ranking online social users by their influence. IEEE/ACM Transactions on Networking
Metadaten
Titel
A local updating algorithm for personalized PageRank via Chebyshev polynomials
verfasst von
Esteban Bautista
Matthieu Latapy
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-00860-5

Weitere Artikel der Ausgabe 1/2022

Social Network Analysis and Mining 1/2022 Zur Ausgabe

Original Article

Favorite YouTubers as a source of health information during quarantine: viewers trust their favorite YouTubers with health information

Review Paper

Opinion mining in online social media: a survey

Original Article

Analyzing extremist social media content: a case study of Proud Boys

Original Article

Knowledge graph model development for knowledge discovery in dementia research using cognitive scripting and next-generation graph-based database: a design science research approach

Original Article

UCred: fusion of machine learning and deep learning methods for user credibility on social media

Original Article

Scalable real-time health data sensing and analysis enabling collaborative care delivery

Premium Partner

    Bildnachweise