Top

Published in:

2019 | OriginalPaper | Chapter

Random Graph Node Classification by Extremal Index of PageRank

Authors : Natalia M. Markovich, Maxim S. Ryzhov

Published in: Distributed Computer and Communication Networks

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Taking account for the graph randomness, our purpose is a node classification by their extremal indexes (EI) as the local dependence measure of node influence characteristics. The EI was calculated by node PageRanks of the local tree related to the node, which is a kind of Thorny Branching Tree (TBT). The blocks estimator was used for the EI estimation by sliding and disjoint block definitions. The classification by the node EI value and the average block size for the local node TBT was introduced for simulated graphs by the Forest Fire and Erdős-Rényi Models and the Berkeley-Stanford dataset as a real example. The new classification methodology is proposed irrespective on the graph structure.

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 "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

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

previous chapter Reliability Analysis of Systems with Hybrid Recovery and Imperfect Built-in-Test

next chapter Group Polling Method Upon the Independent Activity of Sensors in Unsynchronized Wireless Monitoring Networks

Fortunato, S., Boguñá, M., Flammini, A., Menczer, F.: Approximating pagerank from in-degree. In: Aiello, W., Broder, A., Janssen, J., Milios, E. (eds.) WAW 2006. LNCS, vol. 4936, pp. 59–71. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78808-9_6CrossRef

Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, pp. 107–117 (1998)CrossRef

Avrachenkov, K., Gonçalves, P., Legout, A., Sokol, M.: Graph based classification of content and users in BitTorrent. In: Proceeding of NIPS Big Learning Workshop, December 2011

Markovich, N.M.: Extremes in Random Graphs Models of Complex Networks, 5 April 2017. arXiv:1704.01302v1 [math.ST]

Desrosiers, C., Karypis, G.: Within-network classification using local structure similarity. In: Buntine, W., Grobelnik, M., Mladenić, D., Shawe-Taylor, J. (eds.) ECML PKDD 2009. LNCS (LNAI), vol. 5781, pp. 260–275. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04180-8_34CrossRef

Chen, N., Litvak, N., Olvera-Cravioto, M.: Ranking algorithms on directed configuration networks, 12 October 2014. arXiv:1409.7443v2 [math.PR]

Volkovich, Y., Litvak, N.: On the exceedance point process for a stationary sequence. Adv. Appl. Probab. 42, 577–604 (2010)CrossRef

Leadbetter, M.R.: Extremes and local dependence in stationary sequences. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, pp. 291–306 (1983)

Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters, eprint arXiv:0810.1355 (2008)

10.

Diestel, R., Oum, S.: Tangle-tree duality in abstract separation systems, 26 April 2018. arXiv:1701.02509v3 [math.CO]

11.

Beirlant, J., Goegebeur, Y., Teugels, J., Segers, J.: Statistics of Extremes: Theory and Applications. Wiley, Chichester (2004)CrossRef

12.

Markovich, N.M., Ryzhov, M., Krieger, U.R.: Nonparametric analysis of extremes on web graphs: pagerank versus max-linear model. In: Vishnevskiy, V.M., Samouylov, K.E., Kozyrev, D.V. (eds.) DCCN 2017. CCIS, vol. 700, pp. 13–26. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66836-9_2CrossRef

13.

Markovich, N.M., Ryzhov, M.S., Krieger, U.R.: Statistical clustering of a random network by extremal properties. In: Vishnevskiy, V.M., Kozyrev, D.V. (eds.) DCCN 2018. CCIS, vol. 919, pp. 71–82. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99447-5_7CrossRef

14.

Erdős, P., Rényi, A.: On random graphs. Publicationes Mathematicae 6, 290–297 (1959)MathSciNetMATH

15.

Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection (2014). http://snap.stanford.edu/data

16.

Leskovec, J., Faloutsos, C.: Sampling from large graphs (2006). https://doi.org/10.1145/1150402.1150479

Title: Random Graph Node Classification by Extremal Index of PageRank
Authors: Natalia M. Markovich
Maxim S. Ryzhov
Publisher: Springer International Publishing
Book: Distributed Computer and Communication Networks
Print ISBN: 978-3-030-36624-7

Electronic ISBN: 978-3-030-36625-4

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-36625-4_34

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner