search

wllgrnt / protein-networks

Refactored version of my PhD code using a MongoDB backend to store the generated data
GNU General Public License v3.0
0 stars 0 forks source link

Write Tree Comparison Algorithm #13

Open wllgrnt opened 6 years ago

wllgrnt commented 6 years ago

We (and perhaps everybody else) need a weak isomorphism algorithm, but no quick ones are known. Idea: By using community detection to generate a dendrogram, we can compare two graphs by comparing their trees.

wllgrnt commented 6 years ago

Code has now been added to convert a partition into a tree, stored in proteinnetworks.partition

wllgrnt commented 6 years ago

Next step: review the tree comparison literature

wllgrnt commented 6 years ago

Results of SEA Meeting 22/1:

Tree comparison as iterative labelling exercise.

Bottom-up. Take the penultimate level of the tree and assign label based on the isomorphism class of the sub-nodes. E.g. do the child nodes form a triangle? A square? Something else entirely?

Then take the next level. Label by the labelled isomorphism class. E.g. is it a label-3, label-1, label-2 in a triangle?

Repeat. This allows subtree matching including the isomorphism information.