2
$\begingroup$

I have a system with 72 nodes. I have a binary adjacency matrix $S$ of size $72\times 72$. If $S_{i,j}=1$, then node $i$ is adjacent to node $j$. So, we also have $S_{i,j}=S{j,i}$. So, $S$ is a binary symmetric matrix.

$D$ is an another matrix of same size. It is the distance matrix. $D_{i,j}$ is the distance between node $i$ and node $j$, so, $D_{i,i}=0$.

Now, my target is to form 12 adjacent groups of nodes where we have exactly 6 nodes in each group/cluster. The group elements are adjacent, i.e, every node of a group must be adjacent to at least one of the remaining nodes in that cluster. The group elements should be as close as possible, i.e., the sum of distances needs to be minimize.

Can this problem be modeled in Mathematica?

Lets say, vector $U\in 1\times 12$ contains all the summations of distances in a cluster and we can solve a min-max problem as

            Minimize Max U

But, the question is how to formulate the constraints required to form the clusters?

If possible can we consider a variable binary integer matrix $B\in 72\times 12$? So, $B_{i,j}$ defines the association of nodes in a cluster. If $B_{i,j}=1$, it means that node $i$ is in cluster $j$. The summation of all the elements in each column is 6.

$\endgroup$
9
  • 1
    $\begingroup$ How about considering a smaller analogous problem, like 6 nodes that you want divided into 2 groups of 3. In this case you can list the matrices S and D explicitly, and maybe it will become more obvious how to solve it. With luck, that might generalize to the full problem. Even in the simpler case, it would seem that there are configurations of S which would make it impossible to achieve the goal -- for example, what if one of the nodes was isolated and not adjacent to any others... then it could not be in any group. $\endgroup$ – bill s Oct 27 '18 at 19:52
  • $\begingroup$ @bill s, however it is not the case. no node is isolated. $\endgroup$ – dipak narayanan Oct 27 '18 at 19:57
  • $\begingroup$ FindGraphPartition[WeightedAdjacencyGraph[adjmat],6]? $\endgroup$ – kglr Oct 27 '18 at 20:00
  • $\begingroup$ @kglr, the Mathematica documentation says that WeightedAdjacencyGraph works on weighted adjacency matrix. But in my case, the adjacency matrix is not weighted. What about your comment? $\endgroup$ – dipak narayanan Oct 27 '18 at 20:35
  • $\begingroup$ @kglr, Thanks a lot. But when run the code, I am getting this..WeightedAdjacencyGraph::matsq: Argument {{0,0,0,0,0,0,0,363.18,371.88,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,431.19,0,0,0,0,0,0,0,0,632.24,366.3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},<<48>>,<<22>>} at position 1 is not a non-empty square matrix. $\endgroup$ – dipak narayanan Oct 29 '18 at 14:50
2
$\begingroup$

You can use the built-in functions FindGraphPartition to get partition with approximately equal sized groups and FindGraphCommunities to modify partition to equalize the group sizes.

SeedRandom[123]
n = 72;
utm = UpperTriangularize[RandomChoice[{3/4, 1/4} -> {0, 1}, {n, n}], 1];
am = utm + Transpose[utm];
coords = RandomReal[100, {n, 2}];
dm = Rescale @ DistanceMatrix[coords];
wam = ((1 - dm) am) /.  0 | 0. -> ∞;

wag = WeightedAdjacencyGraph[Range[n], wam, 
  VertexSize -> Scaled[.03], VertexLabels -> Placed["Name", Center], 
  ImageSize -> Large]

enter image description here

CommunityGraphPlot[wag]

enter image description here

FindGraphPartition:

  • FindGraphPartition[g, k] gives a partition of vertices into k approximately equal-size parts.

  • For a weighted graph, FindGraphPartition finds a partition such that the sum of edge weights for edges having endpoints in different parts is minimized.

partition = FindGraphPartition[wag, ConstantArray[6, 12]]

{{5, 7, 34, 44, 45, 63, 68}, {6, 10, 12, 22, 36, 58},
{1, 18, 26, 38, 39, 62}, {28, 37, 48, 51, 56, 67},
{8, 16, 43, 47, 54, 70}, {13, 14, 29, 40, 57, 64},
{11, 19, 25, 42, 50, 53}, {2, 4, 17, 23, 24, 61},
{15, 35, 46, 52, 59, 66}, {9, 21, 31, 32, 33, 65},
{20, 27, 30, 49, 55, 60}, {3, 41, 69, 71, 72}}

Length /@ partition

{7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5}

CommunityGraphPlot[wag, partition]

enter image description here

Next, we use FindGraphCommunities with option Method -> "VertexMoving" using partition as the value of the sub-option "InitialPartitioning" and (-(Length[#2] - 12)^2 - Total[(6 - Length@#)^2 & /@ #2] &) as the value of the sub-option "ObjectiveFunction" to get equal sized groups:

partition2 = FindGraphCommunities[wag,  
  Method -> {"VertexMoving", "InitialPartitioning" -> partition, 
    "ObjectiveFunction" -> (-(Length[#2] - 12)^2 - Total[(6 - Length@#)^2 & /@ #2] &)}]

{{1, 18, 26, 38, 39, 62}, {2, 4, 17, 23, 24, 61},
{3, 5, 41, 69, 71, 72}, {6, 10, 12, 22, 36, 58},
{7, 34, 44, 45, 63, 68}, {8, 16, 43, 47, 54, 70},
{9, 21, 31, 32, 33, 65}, {11, 19, 25, 42, 50, 53},
{13, 14, 29, 40, 57, 64}, {15, 35, 46, 52, 59, 66},
{20, 27, 30, 49, 55, 60}, {28, 37, 48, 51, 56, 67}}

Length /@ partition2

{6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6}

CommunityGraphPlot[wag, partition2]

enter image description here

HighlightGraph[Graph[Join @@ partition2, EdgeList @ wag], 
 Subgraph[wag, #] & /@ partition2, VertexSize -> 7/10, 
 GraphLayout -> "CircularEmbedding", 
 VertexLabels -> Placed["Name", Center]]

enter image description here

... every node of a group must be adjacent to at least one of the remaining nodes in that cluster.

Grid[Partition[Subgraph[wag, #, PlotLabel -> #,
  GraphLayout -> "CircularEmbedding", ImageSize -> 200, VertexStyle -> White, 
  EdgeLabels -> {e_ :>  Round[PropertyValue[{wag, e}, EdgeWeight], .1]}, 
  VertexLabels -> Placed["Name", Center], VertexSize -> Medium] & /@ 
partition2, 4]]

enter image description here

$\endgroup$
4
  • $\begingroup$ thanks for your answer. But I think I could not explain my question. How can I upload my data in Mathematica XChange? Lets say {a,b,c,d,e,f} is a cluster where a, b, c, d, e, f are nodes. a must be connected (have an edge) to at least of of the remaining nodes (b,c,d,e,f). Likewise b must be connected (have an edge) to at least of of the remaining nodes (a,c,d,e,f). $\endgroup$ – dipak narayanan Oct 30 '18 at 22:31
  • $\begingroup$ @dipaknarayanan, your requirement is satisfied by all the clusters in partition and partition2 (see the last picture). $\endgroup$ – kglr Oct 30 '18 at 22:49
  • $\begingroup$ @kglr beautiful answer +1 ! $\endgroup$ – chris Oct 31 '18 at 0:42
  • $\begingroup$ Thank you @chris. $\endgroup$ – kglr Oct 31 '18 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.