I am very happy you’re looking into this. I’ve never seen a well motivated procedure for choosing k, and we’re going to need one.
Let’s try and justify why this notion of choice might be appropriate. Firstly, let’s state the obvious that choice here is clearly related to information and entropy. If someone wishes to communicate a partition that doesn’t match one of the natural module numbers, they need to specify how many partitions to divide our graph into and then transmit additional information about specifics of that partition. In the worst case (there are no connections between nodes) specifying the exact partition involves specifying an amount of information proportional to the logarithm of The Bell Number.
This alone doesn’t seem satisfactory to me. I think you could make up lots of other prescriptions for picking partitions that take little information to specify. E.g.: “The ones with minimal n-cuts for their k that come closest to having equal numbers of nodes in each subgraph.”
“Cuts with a single minimum n-cut partition” could be what we’re looking for, but I don’t see anything yet showing it has to be this, and it could not be anything else.
We’ll probably have a post with our own thoughts on measuring modularity out soon, though it’ll be more focused on how to translate a neural network into something you can get a meaningful n-cut-like measure that captures what we care about for at all.
If you’re interested in exchanging notes, drop me or TheMcDouglas a pm.
I am very happy you’re looking into this. I’ve never seen a well motivated procedure for choosing k, and we’re going to need one.
This alone doesn’t seem satisfactory to me. I think you could make up lots of other prescriptions for picking partitions that take little information to specify. E.g.: “The ones with minimal n-cuts for their k that come closest to having equal numbers of nodes in each subgraph.”
“Cuts with a single minimum n-cut partition” could be what we’re looking for, but I don’t see anything yet showing it has to be this, and it could not be anything else.
We’ll probably have a post with our own thoughts on measuring modularity out soon, though it’ll be more focused on how to translate a neural network into something you can get a meaningful n-cut-like measure that captures what we care about for at all.
If you’re interested in exchanging notes, drop me or TheMcDouglas a pm.