Statistical inference on large random graphs  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
76481
Type K
Principal investigator Tusnády, Gábor
Title in Hungarian Nagyméretű véletlen gráfok statisztikai vizsgálata
Title in English Statistical inference on large random graphs
Keywords in Hungarian statisztikai módszerek, véletlen gráfok
Keywords in English statisztical inference, random graphs
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Statistics
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Bolla, Marianna
Csiszár, Villő
Krámli, András
Miklós, Dezso
Starting date 2009-01-01
Closing date 2012-12-31
Funding (in million HUF) 7.200
FTE (full time equivalent) 5.62
state closed project
Summary in Hungarian
Nagymeretű gráfok struktúrájának feltárása gyakori probléma a manapság elterjedt adatbányászatban. A klasszikus módszerek alkalmazhatóságát nehezíti a nagy méret és az adatokra rárakódó zaj. A következő két, dinamikus ill. statikus szituációt vizsgáljuk.

i. Fejlődő véletlen gráfok. A klasszikus Erdős-Rényi elmélet nem alkalmazható a csúcsok preferenciális kapcsolódásával fejlődő, ún. skálafüggetlen gráfokra (Barabási-Albert modell, elméleti bizonyítás Bollobástól
származik). A Rényi Intézetben modelleket dolgozunk ki gráfok evolúciójára, továbbá klasszikus statisztikai
módszereket adaptálunk a paraméterek becslésére és a modellek valódi (biológiai, tudománymetriai) adatokhoz
történő illesztésére.

ii. Lineáris struktúra keresése nagyméretű véletlen mátrixokban. A struktúrát kialakultnak képzeljük, mely
egyértelműen megadható két valószínűségi változó együttes eloszlásával (a súlyozott gráfok és géntérképek ennek speciális esetei). A másik kutatócsoport (BME és Szegedi Tudományegyetem) blokkstruktúrákhoz adódó ún. Wigner-zaj hatását vizsgálja spektrális módszerekkel, végtelenbe tartó blokkméretek mellett. Súlyozott gráfokra a csúcsok kiegyensúlyozott, minimális két- vagy több részre vágásait, mint tesztelhető gráfparamétereket kívánjuk tekinteni (l. Lovász László és társszerzői), majd becsülni a Laplace mátrix sajátértékeivel.

A fenti ritka és sűrű gráfos problémák mindegyike használja az ún. felfújt mátrixok elméletét, ill. a modern
adatbányászat algoritmikus modelljeit. PhD és matematikus hallgatók bevonását is tervezzük, elsősorban
számítógépes szimulációkba.
Summary
To reveal the hidden structure of graphs on large number of vertices is a crutial problem in the steadily developing data mining. The classical methods cannot be applied immediately because of the large sizes and the noise added to our observations. The following two, dynamic and static, situations are investigated.

i. Evolving random graphs. The classical Erdős-Rényi theory is not applicable to the so-called scale-free graphs evolving by preferential attachment of vertices (Barabási-Albert model, theoretical proof by Bollobás). Our group in the Rényi Institute sets up stochastic models for graphs' evolution and adopts classical statistical methods for parameter estimation and fitting the models to real world (biological and scientometrical) data.

ii. Finding linear structure in large random matrices. The structure has already evolved and it is defined by the joint distribution of two random variables (weighted graphs and microarrays are special cases). The other group (Technical university of Budapest and University of Szeged) investigates the effect of a so-called Wigner-noise added to a block structure, the block sizes tending to infinity, by means of spectral techniques. In case of weighted graphs, we plan to use minimum balanced multiway cuts as testable graph parameters (in the sense of Lovász et al.) and estimate them by Laplacian spectra.

The above sparse and dense graph problems both use blown up structures and algorithmic models of data mining. We plan to enroll PhD and mathematics students into the computer simulations.




 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=76481
Decision
Yes





 

List of publications

  
Bolla, M.: Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts and k-means clustering, Physical Review E, Vol. 84, No. 1, 016108, 10 pages, 2011
Bolla, M., Kói, T., Krámli, A.: Testability of minimum balanced multiway cut densities, Discrete Applied Mathematics 160, 1019-1027, 2012
Bolla, M., Friedl, K., Krámli, A.: Singular value decomposition of large random matrices (for two-way classification of microarrays), Journal of Multivariate Analysis 101, 434-446, 2010
Csiszár, V., Hussami, P., Komlós, J., Móri, T., Rejtő, L., Tusnády, G.: When the degree sequence is a sufficient statistic, Acta Mathematica Hungarica 134, No. 1-2, 45-53, 2012
Bolla, M.: Spectra and structure of weighted graphs, Electronic Notes in Discrete Mathematics 38, 49-54., 2011
Bolla, M.: SVD, discrepancy, and regular structure of contingency tables, arXiv: 1301.5259 [math.ST], submitted to the Discrete Applied Mathematics in 2012, 2013
Bolla, M.: Beyond the expanders, International Journal of Combinatorics, Paper 787596, 11 pages, 2011
Bolla, M.: Statistical inference on large contingency tables: convergence, testability, stability, Proc. of the COMPSTAT'2010, 19th International Conference on Computational Statistics, Paris. Physica-Verlag, springer, pp. 817-824., 2010
Bolla, M.: Parametric and nonparametric approaches to recover regular graph partitions, Proc. of the 14th Conference on Applied Stochastic Models and Data Analysis, ASMDA2011, Rome, 2011, ed. R. Manca and C. H. Skiadas, Universita di Sapiensa, 164-171., 2011
Bolla, M., Kurdyakova, A.: Dynamic factors of macroeconomic data, Abstracts of the CFE 09 Conference (Limassol, Cyprus, October 29-31), 2009
Csiszár, V.: EM algorithms for generalized Bradley-Terry models, Annales Univ. Sci. Budapest, Sect. Comp. 36, 143-157, 2012
Csiszár, V.: EM algorithms for Thrustonian and Bradley-Terry-type random permutation models, L. Fajfrová and D. Hlubinka (eds.): Prague Stochastics 2010, Book of Abstracts. Institute of Information Theory and Automation, Academy Sci. Czech Republic, p. 72., 2010
Bolla, M., Kurdyukova, A.: Dynamic factors of macroeconomic data, Annals of the University of Craiova, Mathematics and Computer Science Series 37 (4), pp. 18-28., 2010
Bolla, M.: Modularity sopectra, eigen-subspaces, and structure of weighted graphs, arXiv:1301.5254 [math.ST], submitted to the European Journal of Combinatorics in 2012, 2013
Bolla, M., Kói, T., Krámli, A.: Testability of minimum balanced multiway cut densities, arXiv: 1001.1623v1 [math.PR], 2010
Csiszár, V., Hussami, P., Komlós, J., Móri, F. T., Rejtő, L., Tusnády, G.: Testing goodness of fit of random graph models, Algorithms 5, 629-635, 2012
Harremoes, P., Tusnády, G.: Information divergence is most chi2-distributed than the chi2-statistics, Proceedings of the IEEE International Symposium on Information Theory (ISIT 2012), Cambridge MA, USA, 532-537, 2012
Győrfi, L., Harremoes, P., Tusnády, G.: Some refinements of large deviation tail probabilities, arXiv: 1205.1005, submitted to Statistics and Probability Letters, 2012
Csiszár, V., Móri, T. F.: A Bienaymé-Chebishev inequality for scale mixtures of the multivariate normal distributions, Math. Inequal. Appl. 12, 839-844., 2009
Nepusz, P., Bazsó, F., Négyessy, L., Tusnády, G.: Reconstructing cortical networks: case of directed graphs with high level of reciprocity, Handbook of Large-Scale Networks, Springer (Eds. Bollobás, B., Kozma, R., Dezső, M.), Series: Bolyai Soc. Math. Studies, Vol. 18, 325-368, 2009
Hatvani, L., Toókos, F., Tusnády, G.: A mutation-selection-recombination model in population genetics, Dynamic Systems and Applications 18, 335-362, 2009
Ispány, M., Michaletzky, Gy., Reiczigel, J., Tusnády, G., Tusnády, P., Varga, K.: Approximation of non-negative integer-valued matrices with application to Hungarian mortality data, Proc. of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS2010), Budapest (L. Gerencser, Gy. Michaletzky, A. Edelmayer eds.), 831-838., 2010
Tusnády, G., Gaudi, I., Rejtő, L., Kásler, M., Szentirmai, Z.: Survival chances of Hungarian cancer patients calculated from National Cancer Registry, manuscript, 2010
Csiszár, V.: Markov bases of conditional independence models for permutations, Kybernetika 45, 249-260, 2009
Csiszár, V.: On L-decomposability of random orderings, Journal of Math. Psychology 53, 294-297, 2009
Csiszár, V.: An acyclic operation on the symmetric group, Amer. Math. Monthly 116, 735-738, 2009
Csiszár, V.: Conditional independence relations and log-linear models for random matchings, Acta Math. Hungar. 122 (1-2), 131-152, 2009
Bolla, M.: Beyond the expanders, arXiv: 1101.5926v1 [math.PR], 2011
Reiczigel, J., Rejtő, L., Tusnády, G.: A sharpening of Tusnády's inequality, arXiv: 110.3627v2 [math.ST], 2011
Tusnády, G.: Fried Ervin gömbje, Mat. Lapok új sorozat 16/3, 2-11., 2010
Smith, J. L., Barrett, J. E., Tusnády, G., Rejtő, L., Carry, S. C.: Resolving environmental drivers of microbal community structures in antarctic soils, Antarctic Science 22, 673-680., 2010
Krámli, A.: 50 years of the Arató-Kolmogorov-Sinai paper, Proc. of Conference on Stochastic Models and their Applications, 22-24 August, 2011, Debrecen, p.43, 2011



Back »