Nagyméretű véletlen gráfok statisztikai vizsgálata = Statistical inference on large random graphs

Tusnády, Gábor and Bolla, Marianna and Csiszár, Villő and Krámli, András and Miklós, Dezső (2013) Nagyméretű véletlen gráfok statisztikai vizsgálata = Statistical inference on large random graphs. Project Report. OTKA.

Preview

PDF 76481_ZJ1.pdf Download (167kB) | Preview

Abstract

Nagyméretű gráfok struktúrájának feltárására alkalmaztunk és fejlesztettünk ki paraméteres és nemparaméteres statisztikai módszereket. Paraméteres vizsgálatok: az ún. általánosított véletlen gráf modellben és az alpha-beta-modellekben a paraméterek maximum likelihood becslésére EM-algoritmust használtunk. A modellt a Rasch-modell páros gráfokra történő alkalmazásával kiterjesztettük a többklaszteres szituációra. Nemparaméteres vizsgálatok: minimális, maximális és reguláris vágások. A klaszterek számára a normált Laplace ill. modularitás mátrix sajátértékeiből következtettünk, míg maguknak a klasztereknek a megkeresésére a k-közép eljárást alkalmaztuk a csúcsreprezentánsok segítségével. Tételeket bizonyítottunk a vágások, a térfogatregularitás mérőszáma, a spektrális rés és a klaszterek k-varianciája közti összefüggésekre, ha csúcsok száma tart a végtelenbe úgy, hogy nincsen domináns csúcs. Általánosítottuk az ún. Newman-Girvan modularitást, és a normált modularitás mátrix nagy abszolút értékű sajátértékeit és azok előjelét használtuk a klaszterek jellegének megállapítására. Az általánosított véletlen gráfok spektrális karakterizációját adtuk a strukturális sajátértékek és sajátalterek segítségével. Vizsgálatainkat kiterjesztettük súlyozott, irányított gráfokra és kontingenciatáblákra is. Foglalkoztunk továbbá minimális többszempontú vágássűrűségek tesztelhetőségével a Lovász L. és társszerzői által konvergens gráfsorozatoknál használt értelemben. | We applied and developed parametric and nonparametric statistical methods to recover the structure of large graphs. Parametric inference: in the so-called generalized random graph model and alpha- beta-models we applied EM-algorithm for the maximum likelihood estimation of the parameters. We extended the model to the several clusters case via the Rasch-model applied to the bipartite graphs formed by the pairs of the clusters. Nonparametric inference: minimal, maximal, and regular cuts. For the number of clusters, we concluded from the spectra of the Laplacian and modularity matrices, whereas we found the clusters by the k-means algorithm applied for the vertex representatives. We proved theorems for the relations between the multiway cuts, the constant of the volume-regularity, and the spectral gap together with the k-variance of the clusters, when the number of the vertices tends to infinity in such a way that there are no dominant vertices. We generalized the notion of the so-called Newman-Girvan modularity and gave the spectral characterization of the generalized random graphs. We extended our findings to weighted and directed graphs, further, to contingency tables. We also investigated the testability of balanced multiway cut densities, where for the testability we used the definitions of Lovász L. and coauthors in the context of convergent graph sequences.

Actions (login required)

Edit Item