How to Cluster Hierarchical Network Data

Question

I have thousands of "small" networks that are strictly hierarchical in nature. Here is an example (some are much deeper, much wider etc) but this is the strict structure:

How can one cluster (e.g. k-means) this type of data and is there a package or library in R or Python that can do this?

ADD:

• The nature of the data is that the top node (1) can grow the network immediately beneath them and also help direct the growth below that. So, the choice of topology is of interest here - how it may be associated with other outcomes.
• The objective of clustering this data would be in order to 1) identify typical network structures and both plot the prototype within each cluster (like plotting centroids in "typical" clustering with tabular data) and 2) measure how far from this prototype each is within the cluster.
• Further, there is a numerical value associated with each edge that could be used as a weight for the clustering.

Answer 1

Clustering typical data points such as geographical lattitude and longitude of a given set of locations implies we are trying to group locations by comparing their "nearness" to each other.

One approach to your query would be to identify the aspects of these networks which you could use to measure nearness/similarity for grouping them together.

You haven't mentioned the nature of your problem and the actual objective, a better understanding of the problem may lead to more specific suggestions.

However, you may try using these attributes to create "metrics" to use for clustering:

• network depth
• number of nodes
• max/min no of child nodes per parent node
• properties of the nodes (e.g. sum of values of all nodes, etc), etc.
• Longest traversal path from one leaf node to another
• shortest traversal path from one leaf node to another
• sum of weights on all edges of the tree
• balanced or imbalanced tree / measure of imbalance
• depth weighted sum of "weights" on all edges of the tree

EDIT: Added a few more suggestions based on additional information provided in the question.