I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make.

I have a bunch of undirected, unweighted, simple graphs representing communication networks with varying number of edges and vertices. Assume the graph is connected. I need to compare these networks to choose the "best" out of them. Here's how I define the "best";

  1. No. of edges and vertices; The more the better
  2. Path length from any vertex to another; the shorter the better
  3. Likelihood of a bottleneck; the lesser the better

I might be missing some other aspects which might be relevant for a communication network.

Some concepts that I've read about and not so clear on are;

  1. The Laplacian matrix of a graph; Eigenvalues of which are related to the connectivity of the graph (Algebraic Connectivity,Spectral Gap?)
  2. Conductance or Cheeger constant of the graph
  3. Various centrality measures

Ideally I would want a measure which is easy to compute for large graphs. Even if its not I would like to know more about them.

So far I've looked into various centrality measures. I'm using Mathematica for analysis and it has an inbuilt library of various centrality measures (example). I constructed a vector from each graph using a particular centrality measure (for example, say the Eigenvector centrality), the vector would consist of the centrality measures of the vertices in the graph. I found out that the vectors majorizes each other in the direction of decreasing number of vertices. I dont know for sure if this relevant to the question or not.



Browse other questions tagged or ask your own question.