Results 1 to 2 of 2

Math Help - Clique Problem of Social Networks

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    1

    Smile Clique Problem of Social Networks

    First off, I am not sure if this is the appropriate place to post this question but it's my best guess. An op can move it if appropriate.

    My question is about what I understand is the 'decision problem' of the 'clique problem' of social networks. As far as I understand it it basically says that it is computationally very difficult or at the least time consuming to locate a clique of a given size (a group of people that are all connected to each other) within a well connected social network. It would seem to take an exponential amount of time to do relative to the number of people in the social graph.

    My question is. If we take facebook as example, and I add a new 'friend' would it be simple enough to determine whether that new connection completes a clique of a given size (i.e. 5), or would that still be computationally very difficult to do.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by runner108 View Post
    First off, I am not sure if this is the appropriate place to post this question but it's my best guess. An op can move it if appropriate.

    My question is about what I understand is the 'decision problem' of the 'clique problem' of social networks. As far as I understand it it basically says that it is computationally very difficult or at the least time consuming to locate a clique of a given size (a group of people that are all connected to each other) within a well connected social network. It would seem to take an exponential amount of time to do relative to the number of people in the social graph.

    My question is. If we take facebook as example, and I add a new 'friend' would it be simple enough to determine whether that new connection completes a clique of a given size (i.e. 5), or would that still be computationally very difficult to do.

    Thanks
    Some thoughts.

    If you have a fixed size like 5, then you should be able to speed things up by keeping an updated list of all 4-cliques for each member, stored as the three friends connected to that member (obviously, no need to include the member himself/herself in the list). Then when two members become friends, see if the two people have a list element in common (maybe organize lexicographically and iterate through both lists in parallel). If and only if they share a common list element, their friendship will create a 5-clique. Of course, you can keep track of 4-cliques by keeping lists of 3-cliques, etc. The memory overhead of this could be quite a lot in practice.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: February 12th 2011, 05:02 AM
  2. Social Security Number/Birthday Paradox problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 16th 2010, 06:21 AM
  3. Replies: 9
    Last Post: March 27th 2010, 03:14 AM
  4. Social stats VERY IMPORTANT PLEASE!
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 3rd 2010, 12:20 PM
  5. sampling problem for scale free networks
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: July 14th 2009, 12:07 AM

Search Tags


/mathhelpforum @mathhelpforum