4
$\begingroup$

I'm doing a bit of research on doing social analysis between so called "hub" people. Basically what I want to try to do is determine the shortest paths between two individuals. The problem is that while there are relatively few individuals (a few hundred at most), there are a LOT more connections between the nodes (and several categories of connections). So while a graph may have 100 nodes, there may be tens of thousands of connections (Some of which are redundant).

Now, what we want to try to do is show the relationships from each individual to each other. So for example, if you pick person A, show all of their first degree relationships. Then show all second degree relationships, etc until all the relationships are shown.

There may be as many as 1000 nodes and 100,000 connections, but I don't think too much more than that. Are there any simple algorithms available for this, or would pre-computing unique permutations (via a Map-Reduce style system) be my best bet?

Am I right by thinking this problem is a NP problem (I don't think it's NP-Complete, but it might by NP-Hard)?

Thanks

|cite|improve this question
$\endgroup$
3
$\begingroup$

You can create a table with the degrees-of-separation between every two users by doing a BFS or DFS from each node and recording the length of the shortest path to each node you reach as you get there (sometimes replacing a larger value with a shorter one through a different path you explored later). That's definitely polynomial time (O(|V|^2 + |V|*|E|)), but that's not to say it's cheap to do.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Actually, just BFS. DFS won't give you the right results. $\endgroup$ – Jeffε Dec 12 '10 at 7:26
3
$\begingroup$

You are looking for breadth-first search. O(n + m) and pretty simple to code. If you want to calculate the number of shortest paths from a to b, there is a variant of breadth-first search described as an exercise in "Algorithm Design" by Kleinberg and Tardos which will do the job.

The algorithms work extremely quickly - I wrote a variant of this in Python to analyze a 30000 vertex / 100000 edge graph and the slowest part of the process was reading the graph data off the hard drive.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

You want all solutions, so it is closer to http://en.wikipedia.org/wiki/Sharp-P-complete type problems, although I don't think this is #P complete.

Highly symmetric graphs will yield large numbers as many paths will be the shortest from A->B. Think of a torus grid when you are making paths between two points on opposite sides of the torus.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.