Results 1 to 5 of 5

Math Help - graph clustering, clustering numbers

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2010
    Posts
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by zareiramin View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2010
    Posts
    3
    Quote Originally Posted by undefined View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2010
    Posts
    3
    Quote Originally Posted by jlt199 View Post
    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.
    tanks, it helped me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. EM Algorithm Clustering Nominals
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: August 6th 2010, 03:00 PM
  2. Clustering vectors with different length
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2010, 01:41 PM
  3. Rmsd-based clustering, cluster properties
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: October 6th 2009, 11:43 AM
  4. SVD and clustering with 3D data
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: August 31st 2009, 10:14 AM
  5. help regarding hierarchical clustering in matlab
    Posted in the Math Software Forum
    Replies: 0
    Last Post: September 12th 2008, 01:43 AM

Search Tags


/mathhelpforum @mathhelpforum