There is an interesting set of papers out this year by Milan Randic et al (sorry about the accents - blogger seems to have a problem with accented 'c'...). I've looked at his work before here.
[1] Common vertex matrix: A novel characterization of molecular graphs by counting
[2] On the centrality of vertices of molecular graphs
and one still in publication to do with fullerenes. The central idea here (ho ho) is a graph descriptor a bit like path lengths called 'centrality'. Briefly, it is the count of neighbourhood intersections between pairs of vertices. Roughly this is illustrated here:
For the selected pair of vertices, the common vertices are those at the same distance from each - one at a distance of two and one at a distance of three. The matrix element for this pair will be the sum - 2 - and this is repeated for all pairs in the graph. Naturally, this is symmetric:
At the right of the matrix is the row sum (∑) which can be ordered to provide a graph invariant. In the case of 2-methylpentane it is [6, 5, 5, 3, 3, 2] - this is referred to as the ORS (ordered row sum) in the papers. Naturally, such a simple property to calculate is not a complete graph invariant, although it does have quite a high discriminatory power for acyclic graphs.
Some examples of pairs of graphs with identical ORS are these two pairs:
Where it is clear that they have quite similar structures - which is also true for ORS close together in lex order. There is some code to test all this here. However the implementation I've made is quite inefficient, I suspect. My algorithm was:
1) Calculate a distance matrix (with Floyd-Warshall).
2) Use this matrix to get lists of vertices arranged by neighbourhood.
3) For each pair of vertices, sum the sizes of the intersections of the neighbourhoods.
It really seems like this could be done in less steps, perhaps in some way similar to the first step?
[1] Common vertex matrix: A novel characterization of molecular graphs by counting
[2] On the centrality of vertices of molecular graphs
and one still in publication to do with fullerenes. The central idea here (ho ho) is a graph descriptor a bit like path lengths called 'centrality'. Briefly, it is the count of neighbourhood intersections between pairs of vertices. Roughly this is illustrated here:
For the selected pair of vertices, the common vertices are those at the same distance from each - one at a distance of two and one at a distance of three. The matrix element for this pair will be the sum - 2 - and this is repeated for all pairs in the graph. Naturally, this is symmetric:
Some examples of pairs of graphs with identical ORS are these two pairs:
Where it is clear that they have quite similar structures - which is also true for ORS close together in lex order. There is some code to test all this here. However the implementation I've made is quite inefficient, I suspect. My algorithm was:
1) Calculate a distance matrix (with Floyd-Warshall).
2) Use this matrix to get lists of vertices arranged by neighbourhood.
3) For each pair of vertices, sum the sizes of the intersections of the neighbourhoods.
It really seems like this could be done in less steps, perhaps in some way similar to the first step?
Comments