We will discuss how graph based matrices are capable to find classification of the graph vertices with small within- and between-cluster discrepancies. The structural eigenvalues together with the corresponding spectral subspaces of the normalized modularity matrix are used to find a block-structure in the graph. The notions are extended to rectangular arrays of nonnegative entries and to directed graphs. We also investigate relations between spectral properties, multiway discrepancies, and degree distribution of generalized random graphs. These properties are regarded as generalized quasirandom properties, and we conjecture and partly prove that they are also equivalent for certain deterministic graph sequences, irrespective of stochastic models.
@article{bwmeta1.element.doi-10_1515_spma-2016-0004,
author = {Marianna Bolla and Ahmed Elbanna},
title = {Matrix and discrepancy view of generalized random and quasirandom graphs},
journal = {Special Matrices},
volume = {4},
year = {2016},
pages = {31-45},
zbl = {1338.05241},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_spma-2016-0004}
}
Marianna Bolla; Ahmed Elbanna. Matrix and discrepancy view of generalized random and quasirandom graphs. Special Matrices, Tome 4 (2016) pp. 31-45. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_spma-2016-0004/
[1] N. Alon, J. H. Spencer, The Probabilistic Method. Wiley (2000).
[2] N. Alon et al., Quasi-randomness and algorithmic regularity for graphs with general degree distributions, Siam J. Comput. 39, 2336-2362 (2010).[WoS] | Zbl 1227.05225
[3] A. L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286, 509-512 (1999).[WoS] | Zbl 1226.05223
[4] P. J. Bickel, A. Chen, A nonparametric view of network models and Newman-Girvan and other modularities, Proc. Natl. Acad. Sci. USA, 106, 21068-21073 (2009). | Zbl 06685211
[5] M. Bolla, Recognizing linear structure in noisy matrices, Linear Algebra Appl. 402, 228-244 (2005). | Zbl 1077.15019
[6] M. Bolla, Noisy random graphs and their Laplacians, Discret. Math. 308, 4221-4230 (2008). | Zbl 1153.05062
[7] M. Bolla, Penalized versions of the Newman–Girvan modularity and their relation to normalized cuts and k-means clustering, Phys. Rev. E 84, 016108 (2011).[WoS]
[8] M. Bolla, Spectral Clustering and Biclustering. Learning Large Graphs and Contingency Tables. Wiley (2013). | Zbl 1341.62005
[9] M. Bolla, Modularity spectra, eigen-subspaces and structure of weighted graphs, European J. Combin. 35, 105-116 (2014).[WoS] | Zbl 1292.05167
[10] M. Bolla, SVD, discrepancy, and regular structure of contingency tables, Discret. Appl. Math. 176, 3-11 (2014).[WoS] | Zbl 1300.05158
[11] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, K. Friedl, Spectral properties of modularity matrices, Linear Algebra Appl. 73, 359-376 (2015).[WoS] | Zbl 1311.05109
[12] B. Bollobás, P. Erdős, An extremal problem of graphs with diameter 2, Math. Mag. 48, 419-427 (1975).
[13] B. Bollobás, Random Graphs, 2nd edition. Cambridge Univ. Press, Cambridge (2001).
[14] B. Bollobás, V. Nikiforov, Hermitian matrices and graphs: singular values and discrepancy, Discret. Math. 285, 17-32 (2004). | Zbl 1050.05082
[15] B. Bollobás, S. Janson, O. Riordan, The phase transition in inhomogeneous random graphs, Random Struct. Algorithms 31, 3-122 (2007).
[16] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi, Convergent graph sequences I: Subgraph Frequencies, metric properties, and testing, Advances in Math. 219, 1801-1851 (2008). | Zbl 1213.05161
[17] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi, Convergent sequences of dense graphs II: Multiway cuts and statistical physics, Ann. Math. 176, 151-219 (2012).[WoS] | Zbl 1247.05124
[18] S. Butler, Using discrepancy to control singular values for nonnegative matrices, Linear Algebra Appl. 419, 486-493 (2006). | Zbl 1120.15007
[19] F. Chung, R. Graham, R. K. Wilson, Quasi-random graphs, Combinatorica 9, 345-362 (1989).[WoS][Crossref] | Zbl 0715.05057
[20] F. Chung, R. Graham, Quasi-random graphs with given degree sequences, Random Struct. Algorithms 12, 1-19 (2008). | Zbl 1130.05052
[21] F. Chungm L, Lu, V. Vu, Eigenvalues of random power law graphs. Ann. Comb. 7, 21-33 (2003). | Zbl 1017.05093
[22] A. Coja-Oghlan, A. Lanka, Finding planted partitions in random graphs with general degree distributions, J. Discret. Math. 23, 1682-1714 (2009).[WoS] | Zbl 1207.05178
[23] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5, 17-61 (1960).
[24] P. Holland, K. B. Laskey, S. Leinhardt, Stochastic blockmodels: some first steps, Social Networks 5, 109-137 (1983).[Crossref]
[25] S. Hoory, N. Linial, A. Widgerson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N. S.) 43, 439-561 (2006).[Crossref] | Zbl 1147.68608
[26] T. Kanungo et al., An efficient k-means clustering algorithm: analysis and implementation, IEEE Trans. Pattern Anal. Mach. Intell. 24, 881-892 (2002).[Crossref]
[27] B. Karrer, M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83, 016107 (2011).
[28] L. Lovász, V. T. Sós, Generalized quasirandom graphs, J. Comb. Theory B 98, 146-163 (2008).[WoS][Crossref]
[29] L. Lovász, Very large graphs. In: D. Jerison et al. (Ed.), Current Developments in Mathematics, International Press, Somerville MA (2008), pp. 67-128.
[30] F. McSherry, Spectral partitioning of random graphs. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, Nevada (2001), pp. 529–537.
[31] M. E. J. Newman, Networks. An Introduction. Oxford University Press (2010).
[32] R.G.E. Pinch, Sequences well distributed in the square, Math. Proc. Cambridge Phil. Soc. 99, 19-22 (1986). | Zbl 0581.10024
[33] K. Rohe, S. Chatterjee, B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel, Ann. Stat. 39, 1878-1915 (2011).[WoS] | Zbl 1227.62042
[34] M. Simonovits, V. T. Sós, Szemerédi’s partition and quasi-randomness, Random Struct. Algorithms 2, 1-10 (1991).
[35] E. Szemerédi, Regular partitions of graphs. In: J-C. Bermond et al. (Ed.), Colloque Inter. CNRS. No. 260, Problémes Combinatoires et Théorie Graphes (1976), pp. 399–401.
[36] A. Thomason, Pseudo-random graphs, Ann. Discret. Math. 33, 307-331 (1987).
[37] A. Thomason, Dense expanders and pseudo-random bipartite graphs, Discret. Math. 75, 381-386 (1989). | Zbl 0721.05051
[38] R. C. Thompson, The behavior of eigenvalues and singular values under perturbations of restricted rank, Linear Algebra Appl. 13, 69-78 (1976). | Zbl 0343.15007