# graph clustering, clustering numbers

• Oct 6th 2010, 07:57 AM
zareiramin
graph clustering, clustering numbers
hi every body.
i want to cluster a graph with n nodes to k clusters.

for example suppose that n=10, k=3. some different clustering could be:

clustering 1:
c1={n1,n2,n3} , c2={n4,n5}, c3={n6,n7,n8,n9,n10}

clustering 2:
c1={n1,n2,n10} , c2={n4,n5}, c3={n6,n7,n8,n9,n3}

clustering 3:
c1={n1,n2} , c2={n4,n5}, c3={n6,n7,n8,n9,n3,n10}

i want to know how many different clusters is possible?

• Oct 6th 2010, 08:24 AM
jlt199
I found a reference quoting that there are approximately $\frac{k^n}{k!}$ ways of partitioning n data points into k clusters, assuming hard partitioning.
• Oct 6th 2010, 09:36 AM
undefined
Quote:

Originally Posted by zareiramin
hi every body.
i want to cluster a graph with n nodes to k clusters.

for example suppose that n=10, k=3. some different clustering could be:

clustering 1:
c1={n1,n2,n3} , c2={n4,n5}, c3={n6,n7,n8,n9,n10}

clustering 2:
c1={n1,n2,n10} , c2={n4,n5}, c3={n6,n7,n8,n9,n3}

clustering 3:
c1={n1,n2} , c2={n4,n5}, c3={n6,n7,n8,n9,n3,n10}

i want to know how many different clusters is possible?

Is a cluster allowed to be empty? If we switch c1 and c2, do we get an equivalent or a distinct clustering?

Assuming that switching c1 and c2 produces an equivalent clustering, what you are doing is equivalent to placing n distinguishable objects into k indistinguishable bins. There is more info here

http://www.johndcook.com/TwelvefoldWay.pdf
• Oct 7th 2010, 08:54 AM
zareiramin
Quote:

Originally Posted by undefined
Is a cluster allowed to be empty? If we switch c1 and c2, do we get an equivalent or a distinct clustering?

Assuming that switching c1 and c2 produces an equivalent clustering, what you are doing is equivalent to placing n distinguishable objects into k indistinguishable bins. There is more info here

http://www.johndcook.com/TwelvefoldWay.pdf

a cluster can not be empty and switching c1 and c2 leads same clustering.
I found a reference quoting that there are approximately $\frac{k^n}{k!}$ ways of partitioning n data points into k clusters, assuming hard partitioning.