walkdan
asked on
request graph algorithmic
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.
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.
ASKER
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.
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
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I am making sure I understand what you are asking for.
-bcl