Notice: On April 23, 2014, Statalist moved from an email list to a forum, based at statalist.org.

# st: All possible combinations of X "nodes+neighbor clusters" that sum to a given number range

 From Kari Hexem To statalist@hsphsun2.harvard.edu Subject st: All possible combinations of X "nodes+neighbor clusters" that sum to a given number range Date Wed, 22 Dec 2010 14:27:23 -0500

```Hi all,

I'm trying to analyze a network in which there are 100 nodes, each of
which has defined neighbors and a defined weight. I'm trying to find
all the combinations of contiguous nodes that, when the weights are
added, add up to a given number range, say between 20 and 40.  There
can only be 30 possible combinations of "node+neighbors" clusters in a
solution, and in the final network, each of the 100 nodes can only be
represented once.

I've been writing a script that:
(1) starts from a given node, which in a row, contains that node, its
weight, and all of that nodes' neighbors and their respective weights
(2) walks through adding each neighbor one at a time
(3) determines if that addition is below 40, if yes, add it to the
"node+neighbors" cluster.  if number is above 40, doesn't add it.
(4) then goes from that cluster to all possible next neighbors - (e.g.
from nodes A+B the next neighbors are remaining neighbors of A other
than B and all neighbors of B).
(5) repeats for all the neighbors of those neighbors, until all
possible clusters are identified.  I haven't done this yet, b/c I'm
still trying to figure out a macro for steps 2-4, and also because ...

My strategy is to develop all of the possible clusters that fulfill
the requirements of being between 20 and 40, and then in a later step,
to try to create all possible networks where all of the clusters only
contain unique elements with the correct weighting requirements.
However, the numbers of possible clusters start to get very large very
quickly, and I was wondering if there was a way to add the restriction
of a limited number of clusters (30) and the fact that each node can
only be represented once earlier in the my strategy.

I've also tried using some other networking software to do this, but I
am most comfortable in Stata and so would like to know (a) whether
this can be done in Stata and (b) if not, if there is some other
program people would recommend.

Thanks for all your help!

Kari
*
*   For searches and help try:
*   http://www.stata.com/help.cgi?search
*   http://www.stata.com/support/statalist/faq
*   http://www.ats.ucla.edu/stat/stata/
```