Do you know where your variables are? | |
PerlMonks |
Cliques solution pertinent to my use caseby Sanjay (Sexton) |
on Jul 07, 2021 at 15:57 UTC ( [id://11134769]=perlmeditation: print w/replies, xml ) | Need Help?? |
This refers to the hardness of finding cliques in a graph when the number of nodes becomes high. My use case is that I am trying to form cliques within a cluster where the sum of relationships is maximum. Background & definition (anthropomorphized for ease of understanding): Cluster: A number of persons where each person is related to at least one another person. The strength of the relationship is a number, i.e. Si-j is the strength of the relationship between person i & person j (Symmetric: Si-j = Sj-i). All combinations need not be present - if person x & person y have no relationship then Sx-y does not exist. No relationship with self - Si-i does not exist as well. Problem: Given a list of relationships Si-j: i from 1 to N, for each i some j from 1 to N, i!= j; (graph with the edges giving the strength of the relationship). Find those groups (cliques) where each member is connected to each other and the sum of the relationship is maximum, e.g. if the persons are as follows:
Then the groups formed would be (A,B) & (C,D) for a sum of relationships of 180 (92 + 88). Any other combination would have a lesser sum, e.g. (A,B,C) & (D) would have a sum of relationships of 101 (92 + 7 + 2). How I did it: Convert the list of Si-j's into an integer linear programming problem and call a free solver lp_solve. Got good results - out of about 40,000 problem sets (clusters) only about 20 timed out. This on an ancient 3'rd gen i7 laptop with 4GB RAM. About another 10 were "very" large (more than 2,000 edges). Gives me confidence that use of a commercial solver and a larger timeout period may give even better results. Linear programming problem formulation left out here as it is more an algorithm issue rather than a Perl issue. We can discuss if interested. Off forum perhaps? Hope this is interesting. And, perchance, if it is useful for anyone then it would be the icing on the cake!
Back to
Meditations
|
|