nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Random Graph Node Classification by Extremal Index of PageRank

verfasst von : Natalia M. Markovich, Maxim S. Ryzhov

Erschienen in: Distributed Computer and Communication Networks

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

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.

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

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

Vorheriges Kapitel Reliability Analysis of Systems with Hybrid Recovery and Imperfect Built-in-Test

Nächstes Kapitel 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

Titel: Random Graph Node Classification by Extremal Index of PageRank
verfasst von: Natalia M. Markovich
Maxim S. Ryzhov
Verlag: Springer International Publishing
Buch: Distributed Computer and Communication Networks
Print ISBN: 978-3-030-36624-7

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"