Solved

request graph algorithmic

Posted on 2004-08-06
8
301 Views
Last Modified: 2013-12-26
Do you know Friendster or Orkut, a social networking connected people together, I'm interesting some algorithm in the site:

Can anybody tell me how to calculate quickly to determined the count of people in everyone's personal networking. I think the breadth first search is very slowly.
0
Comment
Question by:walkdan
  • 3
  • 2
8 Comments
 
LVL 11

Expert Comment

by:bcladd
ID: 11739304
By personal network you mean the connected component (of the social network graph) that the person is in, right? That is, the count of people that can be reached through "associate" links.

I am making sure I understand what you are asking for.

-bcl
0
 

Author Comment

by:walkdan
ID: 11741061
The count of people is calucalte 4 degree. for example, My 1 degree of people is direct connected to me, 2 degree of people is connected through one people. how many people in my 4 degree networking.
0
 
LVL 11

Expert Comment

by:bcladd
ID: 11742952
How often is the graph changed? I ask because I think breadth-first is the best solution (especially a depth-limited breadth-first search). If the graph changes regularly, then you can do the search at the moment of query. If the graph is MOSTLY static, that is there are lots and lots of queries you can update the count when you insert a node or add a connection (again, depends on the relative frequency of operations).

Other thoughts:
It is possible to keep a list of distance n neighbors (probably not too space intensive) though in social networks there is a large percentage of the graph at distance 4. Probably easier to just keep the count (perhaps as a count at each distance).

-bcl
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 17

Accepted Solution

by:
davebytes earned 125 total points
ID: 11743383
Generally, each node stores the number of exit paths.  So at degree 1, you know your count, degree 2, you follow out each path and get their counts and add them, etc.

Breadth vs depth doesn't really make a difference, as in all of these programs (that I've seen), the numbers are approximate -- i.e., I don't know that they eliminate duplicate friends from counts.  And, since they only tell you to degree 4 or so anyway, the search doesn't take that long.

It is also possible that these systems actually store both degree 1 AND degree 2 counts at every node (updates to one node push to all connected), so that traversal/calc is THAT much faster.

-d
0
 

Author Comment

by:walkdan
ID: 11745405
The count can precalculated and store to database, when user request the count, just pick it from database and return immediately.

But the precalculation is also unefficient if do breadth-frist travel every time to get everyone's count.
Can way get the counts only one or several travel times.
0
 
LVL 11

Assisted Solution

by:bcladd
bcladd earned 125 total points
ID: 11746570
(1) Depth-first versus breadth-first traversal will vist the same number of nodes (assuming it is not depth limited, each will visit every node in the connected component where the search starts). If answers are approximate, precalculating the depth 2 numbers means that you can get the "number" you want with a breadth first sum of depth 2 friends of your friends' friends.

(2) Pre-calculation is not that expensive IF updates are relatively rare. Yes, pushing the change through 4 layers is expensive but if you think about it you really only update when a new connection is added (or one is removed) and that means that we are really already 1 ply down in the graph (we know the new friend). If we're not worried about overcounting, we can just move down to all their friends, their friends' friends, and their friends' friends' friends, counting them AND incrementing their counts (we added a new friend to the group). If we're worried about overcounting, then we need some list of all of the members of the group and that would require calculating _or_storing it. That is a full depth 4 traversal OR a fair amount of storage. We can use a depth 2 set of friends  to quickly build the depth 4 set (just union all the depth 2 neighbor's depth 2 sets, counting on union to handle duplicates).

-bcl
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Concerto provides fully managed cloud services and the expertise to provide an easy and reliable route to the cloud. Our best-in-class solutions help you address the toughest IT challenges, find new efficiencies and deliver the best application expe…
Need to grow your business through quality cloud solutions? With everything required to build a cloud platform and solution, you may feel like the distance between you and the cloud is quite long. Help is here. Spend some time learning about the Con…

943 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

1 Experts available now in Live!

Get 1:1 Help Now