Matrix and discrepancy view of generalized random and quasirandom graphs

Marianna Bolla; Ahmed Elbanna

Special Matrices (2016)

  • Volume: 4, Issue: 1, page 31-45
  • ISSN: 2300-7451

Abstract

top
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.

How to cite

top

Marianna Bolla, and Ahmed Elbanna. "Matrix and discrepancy view of generalized random and quasirandom graphs." Special Matrices 4.1 (2016): 31-45. <http://eudml.org/doc/276944>.

@article{MariannaBolla2016,
abstract = {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.},
author = {Marianna Bolla, Ahmed Elbanna},
journal = {Special Matrices},
keywords = {modularity matrix; spectral clustering; multiway discrepancy; generalized random graphs; generalized quasirandom properties},
language = {eng},
number = {1},
pages = {31-45},
title = {Matrix and discrepancy view of generalized random and quasirandom graphs},
url = {http://eudml.org/doc/276944},
volume = {4},
year = {2016},
}

TY - JOUR
AU - Marianna Bolla
AU - Ahmed Elbanna
TI - Matrix and discrepancy view of generalized random and quasirandom graphs
JO - Special Matrices
PY - 2016
VL - 4
IS - 1
SP - 31
EP - 45
AB - 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.
LA - eng
KW - modularity matrix; spectral clustering; multiway discrepancy; generalized random graphs; generalized quasirandom properties
UR - http://eudml.org/doc/276944
ER -

References

top
  1. [1] N. Alon, J. H. Spencer, The Probabilistic Method. Wiley (2000). 
  2. [2] N. Alon et al., Quasi-randomness and algorithmic regularity for graphs with general degree distributions, Siam J. Comput. 39, 2336-2362 (2010).[WoS] Zbl1227.05225
  3. [3] A. L. Barabási, R. Albert, Emergence of Scaling in Random Networks, Science 286, 509-512 (1999).[WoS] Zbl1226.05223
  4. [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). Zbl06685211
  5. [5] M. Bolla, Recognizing linear structure in noisy matrices, Linear Algebra Appl. 402, 228-244 (2005). Zbl1077.15019
  6. [6] M. Bolla, Noisy random graphs and their Laplacians, Discret. Math. 308, 4221-4230 (2008). Zbl1153.05062
  7. [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. [8] M. Bolla, Spectral Clustering and Biclustering. Learning Large Graphs and Contingency Tables. Wiley (2013). Zbl1341.62005
  9. [9] M. Bolla, Modularity spectra, eigen-subspaces and structure of weighted graphs, European J. Combin. 35, 105-116 (2014).[WoS] Zbl1292.05167
  10. [10] M. Bolla, SVD, discrepancy, and regular structure of contingency tables, Discret. Appl. Math. 176, 3-11 (2014).[WoS] Zbl1300.05158
  11. [11] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, K. Friedl, Spectral properties of modularity matrices, Linear Algebra Appl. 73, 359-376 (2015).[WoS] Zbl1311.05109
  12. [12] B. Bollobás, P. Erdős, An extremal problem of graphs with diameter 2, Math. Mag. 48, 419-427 (1975). 
  13. [13] B. Bollobás, Random Graphs, 2nd edition. Cambridge Univ. Press, Cambridge (2001). 
  14. [14] B. Bollobás, V. Nikiforov, Hermitian matrices and graphs: singular values and discrepancy, Discret. Math. 285, 17-32 (2004). Zbl1050.05082
  15. [15] B. Bollobás, S. Janson, O. Riordan, The phase transition in inhomogeneous random graphs, Random Struct. Algorithms 31, 3-122 (2007). 
  16. [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). Zbl1213.05161
  17. [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] Zbl1247.05124
  18. [18] S. Butler, Using discrepancy to control singular values for nonnegative matrices, Linear Algebra Appl. 419, 486-493 (2006). Zbl1120.15007
  19. [19] F. Chung, R. Graham, R. K. Wilson, Quasi-random graphs, Combinatorica 9, 345-362 (1989).[WoS][Crossref] Zbl0715.05057
  20. [20] F. Chung, R. Graham, Quasi-random graphs with given degree sequences, Random Struct. Algorithms 12, 1-19 (2008). Zbl1130.05052
  21. [21] F. Chungm L, Lu, V. Vu, Eigenvalues of random power law graphs. Ann. Comb. 7, 21-33 (2003). Zbl1017.05093
  22. [22] A. Coja-Oghlan, A. Lanka, Finding planted partitions in random graphs with general degree distributions, J. Discret. Math. 23, 1682-1714 (2009).[WoS] Zbl1207.05178
  23. [23] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5, 17-61 (1960). 
  24. [24] P. Holland, K. B. Laskey, S. Leinhardt, Stochastic blockmodels: some first steps, Social Networks 5, 109-137 (1983).[Crossref] 
  25. [25] S. Hoory, N. Linial, A. Widgerson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N. S.) 43, 439-561 (2006).[Crossref] Zbl1147.68608
  26. [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. [27] B. Karrer, M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83, 016107 (2011). 
  28. [28] L. Lovász, V. T. Sós, Generalized quasirandom graphs, J. Comb. Theory B 98, 146-163 (2008).[WoS][Crossref] 
  29. [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. [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. [31] M. E. J. Newman, Networks. An Introduction. Oxford University Press (2010). 
  32. [32] R.G.E. Pinch, Sequences well distributed in the square, Math. Proc. Cambridge Phil. Soc. 99, 19-22 (1986). Zbl0581.10024
  33. [33] K. Rohe, S. Chatterjee, B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel, Ann. Stat. 39, 1878-1915 (2011).[WoS] Zbl1227.62042
  34. [34] M. Simonovits, V. T. Sós, Szemerédi’s partition and quasi-randomness, Random Struct. Algorithms 2, 1-10 (1991). 
  35. [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. [36] A. Thomason, Pseudo-random graphs, Ann. Discret. Math. 33, 307-331 (1987). 
  37. [37] A. Thomason, Dense expanders and pseudo-random bipartite graphs, Discret. Math. 75, 381-386 (1989). Zbl0721.05051
  38. [38] R. C. Thompson, The behavior of eigenvalues and singular values under perturbations of restricted rank, Linear Algebra Appl. 13, 69-78 (1976). Zbl0343.15007

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.