Matrix and discrepancy view of generalized random and quasirandom graphs

• Autorzy: Marianna Bolla , Ahmed Elbanna
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

modularity matrix; spectral clustering; multiway discrepancy; generalized random graphs; generalized quasirandom properties

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2016
• Tom: 4
• Numer: 1
• Strony: 31-45

Daty

wydano

2016-01-01

otrzymano

2015-08-18

zaakceptowano

2015-11-03

online

2015-12-16

Twórcy

autor

Marianna Bolla

• Institute of Mathematics, Budapest University of Technology and Economics, 1111. Budapest, Műegyetem rkp. 3, Hungary

autor

Ahmed Elbanna

• Institute of Mathematics, Budapest University of Technology and Economics, 1111. Budapest, Műegyetem rkp. 3, Hungary

Bibliografia

• [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]
• [3] A. L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286, 509-512 (1999).[WoS]
• [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).
• [5] M. Bolla, Recognizing linear structure in noisy matrices, Linear Algebra Appl. 402, 228-244 (2005).
• [6] M. Bolla, Noisy random graphs and their Laplacians, Discret. Math. 308, 4221-4230 (2008).
• [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).
• [9] M. Bolla, Modularity spectra, eigen-subspaces and structure of weighted graphs, European J. Combin. 35, 105-116 (2014).[WoS]
• [10] M. Bolla, SVD, discrepancy, and regular structure of contingency tables, Discret. Appl. Math. 176, 3-11 (2014).[WoS]
• [11] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, K. Friedl, Spectral properties of modularity matrices, Linear Algebra Appl. 73, 359-376 (2015).[WoS]
• [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).
• [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).
• [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]
• [18] S. Butler, Using discrepancy to control singular values for nonnegative matrices, Linear Algebra Appl. 419, 486-493 (2006).
• [19] F. Chung, R. Graham, R. K. Wilson, Quasi-random graphs, Combinatorica 9, 345-362 (1989).[WoS][Crossref]
• [20] F. Chung, R. Graham, Quasi-random graphs with given degree sequences, Random Struct. Algorithms 12, 1-19 (2008).
• [21] F. Chungm L, Lu, V. Vu, Eigenvalues of random power law graphs. Ann. Comb. 7, 21-33 (2003).
• [22] A. Coja-Oghlan, A. Lanka, Finding planted partitions in random graphs with general degree distributions, J. Discret. Math. 23, 1682-1714 (2009).[WoS]
• [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]
• [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).
• [33] K. Rohe, S. Chatterjee, B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel, Ann. Stat. 39, 1878-1915 (2011).[WoS]
• [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).
• [38] R. C. Thompson, The behavior of eigenvalues and singular values under perturbations of restricted rank, Linear Algebra Appl. 13, 69-78 (1976).

Identyfikatory

DOI

10.1515/spma-2016-0004