I have a set of lists that represent molecular descriptors. I need to identify which descriptors are highly correlated and eliminate the correlated pairs. I can represent the connectivity by assigning a number to each descriptor-list and creating edges that correspond to my correlation criteria, generating images that look like this:
It is not too difficult to find the vertices that have many connections, and I can cull this dataset down to the following types of elements:
edges = # /. List -> DirectedEdge & /@ {{1, 2}, {2, 3}, {1, 3}, {4,
5}, {5, 6}, {7, 8}, {8, 9}, {9, 10}, {11, 12}, {13, 14}, {14,
15}, {15, 16}, {16, 17}, {18, 19}, {19, 20}, {20, 21}, {21, 18}};
ranks = {4, 12, 6, 3, 21, 14, 1, 17, 20, 13, 2, 19, 11, 15, 10, 8, 9,
7, 5, 16, 18};
Graph[Labeled[#, ranks[[# /. DirectedEdge -> List]]] & /@ edges,
ImagePadding -> 10, VertexLabels -> "Name"]
Each vertex has a rank assigned to it, and these ranks are shown as edge labels (the 1st element corresponds to the rank at the tail of the directed edge, so the rank of vertex 20 is 16. What I am struggling with now is culling this list further according to the following rules:
- Maximize number of vertices remaining
- Keep vertices with the lowest rank
- When keeping pairs of vertices in chains and rings, use the sum of the ranks as the comparator.
- Tiebreaker: random choice
Based on these rules, the sample graph should result in the following output (with the possible exception of vertices 17 and 15, which are tied with keeping 16/14).
desiredoutput = {20, 18, 1, 17, 15, 10, 7, 4, 6, 11};
I've noted that @MrWizard has looked at finding neighbors which may be of help, but I'm still fumbling with applying that code to my situation.
Examples
Take the chain of length 4. By inspection, the maximum number of vertices we could keep without there being a correlation (edge) between the two is 2. The combinations can be found by determining the permutation of Range@4 and delete cases where the numbers in the pair are consecutive. Then replacing the pairs with rank values to determine the pair of vertices to keep:
DeleteCases[Permutations[Range@4, {2}], {x_, y_} /; Abs[x - y] == 1 || y < x]
(* {{1, 3}, {1, 4}, {2, 4}} *)
Total /@ (% /. {1 -> 13, 2 -> 20, 3 -> 17, 4 -> 1})
{30, 14, 21}
Because pair {1,4}, which corresponds to vertices 10 and 7, has the lowest combined rank, these are the two vertices that will be kept in the chain.
A 3-membered chain will always lose its middle vertex, since rule 1 states that we are trying to maximize the number of vertices in the result.
The 3-membered ring will reduce to only one vertex, so we take the vertex with the smallest rank, which by inspection is vertex 1.
My problem boils down to identifying the 'shape' of a feature in the graph (chain, ring) so that the appropriate rule can be applied, and then modifying the above process so that it does not require manual interaction.
