A graph complexity measure based on the spectral analysis of the Laplace operator

Abstract

In this work we introduce a concept of complexity for undirected graphs in terms of the spectral analysis of the Laplacian operator defined by the incidence matrix of the graph. Precisely, we compute the norm of the vector of eigenvalues of both the graph and its complement and take their product. Doing so, we obtain a quantity that satisfies two basic properties that are the expected for a measure of complexity. First, complexity of fully connected and fully disconnected graphs vanish. Second, complexity of complementary graphs coincide. This notion of complexity allows us to distinguish different kinds of graphs by placing them in a “croissant-shaped” region of the plane link density - complexity, highlighting some features like connectivity, concentration, uniformity or regularity and existence of clique-like clusters. Indeed, considering graphs with a fixed number of nodes, by plotting the link density versus the complexity we find that graphs generated by different methods take place at different regions of the plane. We consider some of the paradigmatic randomly generated graphs, in particular the Erdös-Rényi, the Watts-Strogatz and the Barabási-Albert models. Also, we place some particular, let us say deterministic, well known hand-crafted graphs, to wit, lattices, stars, hyper-concentrated and cliques-containing graphs. It is worthy noticing that these deterministic classical models of graphs depict the boundary of the croissant-shaped region. Finally, as an application to graphs generated by real measurements, we consider the brain connectivity graphs from two epileptic patients obtained from magnetoencephalography (MEG) recording, both in a baseline period and in ictal periods (epileptic seizures). In this case, our definition of complexity could be used as a tool for discerning between states, by the analysis of differences at distinct frequencies of the MEG recording.