4
$\begingroup$

Background:
There are 5 ways to represent a mathematical idea: words/text, tables of numbers, plots/figure, symbolic expressions, flowcharts/graph.

When I ask about "graphs" (below) I do not mean a picture of the relationship of x-vs-y (aka plot), but I do mean the nodes-and-edges, graph-theory version. I also presume that the graph is connected - there is not any node such that by traversing edges it is impossible to get from that node to any other node in the graph.

Within the words/text there is the idea of cyclomatic complexity for a program.

Within the symbolic expressions we can look at count of operators and count of parameters to get an idea of complexity of an expression.

Question:
What are some ways to measure the complexity of a graph? Is is an expression comprised of edges and nodes? Is there a single number? I would think there are an infinite variety, but I'm not sure how to grapple with this one.

Example random metric:
How long it takes in step-count, on average, over many trials, with random starting position, for a random graph walker to touch every edge and every node? Is that a thing? (I just thought of this, and it is a thing. 1, 2)

Follow-up question:
How does the complexity change for a directional graph, or a directionally weighted graph? I know that digraphs are a subset of all graphs.

Update:
Possibly relevant references:

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ @Henry - is this updated version sufficiently less ambiguous? $\endgroup$ – EngrStudent Oct 11 '16 at 21:19
  • $\begingroup$ Yes, it seems clearer now $\endgroup$ – Henry Oct 11 '16 at 21:33
  • 1
    $\begingroup$ The modularity statistic is one way to measure how readily the graph can be divided into 2 partitions. pnas.org/content/103/23/8577.full $\endgroup$ – Sycorax Apr 28 '17 at 16:23
  • $\begingroup$ @Sycorax - I am looking at igraph::modularity for it, but I'm still figuring out how to specify a particular graph. I don't (yet) see how modularity applies to directed graphs. $\endgroup$ – EngrStudent Apr 28 '17 at 16:44
  • 2
    $\begingroup$ This seems rather different than the questions that are presently in the text! $\endgroup$ – whuber♦ Apr 28 '17 at 21:04
5
+50
$\begingroup$

Common graph measures include :

  1. Connectivity : is the graph connected - i.e. can you reach any node from any other node, or can you break the graph down into "islands" or regions that are unreachable from one another?
  2. Tree-test : does the graph conform to a tree-shape (i.e. can you reach any node from any other node via a single, unique path?)
  3. Bipartite Test : some graphs are bipartite, that is, they consist of two groups of nodes, such that members of each group only connect with members of the other group. For example, a graph of buildings and connected utilities (gas, electricity, water) would be bipartite
  4. Planarity : is the graph planar? That is, can it be drawn on a 2-dimensional surface such that no edges must be drawn intersecting one another?
  5. Hamiltonian/Eularian tests - can every node in the graph be reached without using the same edge twice? Can a path be traced on the graph such that every edge is visited once, and only once?
  6. Clique Analysis : what is the maximum clique number of the graph, and how many cliques of each size up to this number exist?
  7. Center, Diameter, Eccentricity, Periphery, Girth, Expansion and Radius measures : other (non-exhaustive) metrics that describe different aspects of the graph

There's more besides, but here are some links to sites discussing metrics such as these:

https://people.hofstra.edu/geotrans/eng/methods/ch1m3en.html

https://www.nas.ewi.tudelft.nl/people/Piet/papers/TUDreport20111111_MetricList.pdf

https://math.stackexchange.com/questions/301778/what-are-some-measures-of-connectedness-in-graphs

http://www.bu.edu/networks/files/2012/08/basics-of-network-analysis.pdf

And this is a fairly neat list: http://mathworld.wolfram.com/topics/GraphProperties.html

Another resource is the networkx python library reference: http://networkx.readthedocs.io/en/stable/reference/index.html

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.