Matrix and discrepancy view of generalized random and quasirandom graphs

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.

Keywords

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