Is there a way to modify the algorithm to make it avoid including two vertexes of the same type into one cluster?

[RaisssHab]

Hello!

Suppose I want to cluster vertexes of the graph which are labeled with certain types. I know that the result of the clustering must not include two or more vertexes of the same type, only zero or one.

Is there a way to modify the algorithm to achieve it?

I tried the following:

1. at every step consider each row (which represents a cluster at the end of the process);
2. find the most probable vertex of the given type at this step;
3. find other vertexes of this type in the row and power them not by r (-I parameter), but by 2*r or even replace with zero.

Also I considered that if the row is going to become the cluster, then it doesn't make sense to change the possible attractor by powering it or by nullifying it, instead we should minimize other vertexes of the same type as the possible attractor. So the algorithm would look like:

1. at every step consider each row (which represents a cluster at the end of the process);
   2.1) if the given type is the same as the possible attractor type, then find other vertexes of this type in the row and power by 2r;
   2.2) else find the most probable vertex of the given type at this step, find other vertexes of this type in the row and power them by 2r.

While it converges on small amount of data (maybe 5 000-10 000 vertexes, not sure really), I can't reach that effect on a big graph with 50 000 vertexes. Also the result isn't good enough: although cluster size gets reduced compared to the initial algorithm, the size nevertheless may be big enough.

Thanks in advance!

[micans]

Hello,

This sounds like an interesting problem, with a bit of a flavour of a colouring problem -- you only want clusters in which all the nodes/vertexes have different colours only, no colour repeating in a cluster. I had a quick look whether this has been studied, but I was hampered a bit by the dominance of all the other graph colouring problems. Are you aware of any other efforts in this direction?

My initial thought is that modifying rows does not fit very well into the ideas underlying mcl - it destroys the mathematical niceness of the matrix, and I don't think it is possible to guarantee that it will do what you want. Normally I would search for a way to change the input graph so that the problem is encoded in the data. However, the nature of what you describe feels like an optimisation problem with hard discrete constraints. It is not really possible for example to give a special weight to an edge between two vertices with the same type/colour that conveys to the algorithm "these shall not be put together". In that sense, mcl is not a natural fit, as it was designed to not do any bookkeeping or accounting and hence adding any bookkeeping or accounting to it is awkward. Especially the negative aspect of this constraint (do NOT put together certain things) is difficult in this respect, as well as the fact that it is absolute.