Re: combinatorics/graph theory problem for set partitions
From: Keith A. Lewis (lewis_at_PROBE.mitre.org)
Date: 08/11/04
- Next message: jake: "conditional independence test"
- Previous message: Lee Rudolph: "Re: Help with academic genealogy"
- In reply to: Faheem Mitha: "combinatorics/graph theory problem for set partitions"
- Next in thread: Chas Brown: "Re: combinatorics/graph theory problem for set partitions"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 11 Aug 2004 15:31:39 +0000 (UTC)
Faheem Mitha <faheem@email.unc.edu> writes in article <slrnchiff8x.rsk.faheem@Chrestomanci.home.earth> dated Tue, 10 Aug 2004 21:28:08 GMT:
>Consider n vertices. Then there are $\binom{n}{2} = \frac{n(n-1)}{2}$
>edges that can connect these n vertices.
>
>Suppose I construct a random graph by choosing k edges in such a way
>that each edge is chosen independently with probability p, where p is
>small.
>
>Then I consider the set partition defined by this graph such that two
>vertices i and j are in the same partition iff they are connected by
>some sequence of edges.
>
>The motivation for this is to get a probability distribution on set
>partitions of sets of a fixed size. It is clear that the above recipe
>defines one. However, it is less clear for a given model M how to
>compute its probability P(M). This seems to involve adding up the
>probabilities over all graphs that give rise to a particular M, which
>might be a hard problem. Does anyone know if there is a known answer
>for this? I don't need a closed form solution. A recursive algorithm
>would work fine.
I tried doing it by paths but didn't get very far.
Probability that i and j are connected by a path of length 1 is p.
Probability that i and j are connected by a path of length 2 is (n-2)*p^2.
Probability that i and j are connected by a path of length 3 is C(n-2,2)*p^3.
The first two probabilities are independent of each other, but after that
they are not. So this approach may be a dead end.
Exhaustive enumeration? You have C(n*(n-1)/2, k) possible sets of paths,
all of equal probability. This type of problem lends itself to a Monte
Carlo simulation.
Pick k different random links, and compute the partition sizes. Repeat as
many times as your computing environment allows.
I'd suggest using an array linked[n,n] to store the link information,
possibly symetric such that linked[i,j] = linked[j,i]. A structured array
for partition information, partition[n] which initially has .id
partition[i].id = i, partition[i].size = 1, and partition[i].next = NULL.
For each new link (i,j), look at partition[i].id and partition[j].id. If
they are different, set them both to the lower value, add the sizes, and
append one list to the other.
Another approach would be to model each partition based on size and number
of links, computing probabilities of each interatively. Do not count
unconnected vertices as partitions, but maintain a count of how many there
are.
If there's a partition of size n1 with k1 links, there are n1*(n1-1)/2 - k1
potential links which would not change anything except the link count. If
there's another partition of size n2, there are n1*n2 potential links which
would cause the partitions to merge. And there are n1*singleton_count links
which would increment the size by 1.
--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
- Next message: jake: "conditional independence test"
- Previous message: Lee Rudolph: "Re: Help with academic genealogy"
- In reply to: Faheem Mitha: "combinatorics/graph theory problem for set partitions"
- Next in thread: Chas Brown: "Re: combinatorics/graph theory problem for set partitions"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
