Thread: 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?

tanks in advance.

I found a reference quoting that there are approximately ways of partitioning n data points into k clusters, assuming hard partitioning.

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?

tanks in advance.

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

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.
tanks for your reply

Originally Posted by jlt199

I found a reference quoting that there are approximately ways of partitioning n data points into k clusters, assuming hard partitioning.

tanks, it helped me.