I looked at some of the other answers on the stack exchange but they didn't seem to answer what I was looking for, so let me elaborate.
I have a large un-directed tree/graph where I need to extract some node-level features (centralities for example). One of the key characteristics that I need to extract is the "symmetry" a certain node displays based on how similar the subgraphs connected to it are (along with giving weightage to the size of these subgraphs as well)
As an illustration -
- Node A is quite "symmetric" as the majority of the subgraphs connected to it look exactly the same in structure. Even though 2/3 of connected subgraphs are equivalent, the 2 that are the same contain a large proportion of the graph, thus contributing to the symmetry.
- Node B is also somewhat "symmetric" because it has a large number of single nodes connected to it, however, the size of those subgraphs is quite small while there is a larger subgraph that doesn't contribute to its "symmetry"
- Finally, node C is not symmetric because the 2 subgraphs connected to it are completely different.
I can come up with some custom measures for this problem as well, but I am looking for any formalism that already exists if at all. Any leads would be appreciated!
PS: The actual problem is one level deeper as the graph is heterogenous and nodes can be of different types as well, which need to be taken into account when we talk about equivalent subgraphs, but thats a problem for another time!