Find shortest path between two addresses?

Cyberdyne

hero member

Activity: 630

Merit: 500

Quote from: domob on July 10, 2013, 03:10:00 AM

Note also that I believe the percents showed on the taint page are related also to the number of coins actually transferred between both addresses, and it is not clear how/if this correlates strongly with the shortest path in the graph. So I'm not sure what exactly you are looking for.

Oh, I didn't realize that, but I guess that's what I'm looking for - How about I word it like this:

Input: 2 addresses

Output: A number between 0 and 100, showing how strongly the addresses are 'connected' or related, and the number of coins in each transaction would be a useful metric in this case.

0 being there is no connection between them whatsoever, and 100 being that the ONLY coins sent from one address were to the other one.

Ah, if only I had all the time in the world...

domob

legendary

Activity: 1135

Merit: 1166

Quote from: Cyberdyne on July 09, 2013, 04:17:37 PM

Maybe finding ANY path is too complicated as you guys are discussing, but what about just finding a STRONG path if it exists.

For example, on blockchain.info's Taint page, it lists the associated addresses and the % that they are connected.

What would be great would be if you could enter 2 addresses, and see if they were connected to each other in a strong way.

On a practical level, this would involve nothing more than entering 1 or 2 of addresses into blockchain.info's Taint page and seeing if the other address is on that list, but in an automated way, so one doesn't need to use CTRL-F.

Like, find out if two addresses have a X% or more linkage, otherwise forget it!

This would correspond to running Dijkstra's algorithm (I looked up the exact complexity, it is O(E + V log V) where E is the number of edges = transactions, and V is the number of vertices = addresses) in such a way that you stop early as soon as your distance is larger than the treshold you want and you haven't yet found your second address.

Note also that I believe the percents showed on the taint page are related also to the number of coins actually transferred between both addresses, and it is not clear how/if this correlates strongly with the shortest path in the graph. So I'm not sure what exactly you are looking for.

Cyberdyne

hero member

Activity: 630

Merit: 500

Maybe finding ANY path is too complicated as you guys are discussing, but what about just finding a STRONG path if it exists.

For example, on blockchain.info's Taint page, it lists the associated addresses and the % that they are connected.

What would be great would be if you could enter 2 addresses, and see if they were connected to each other in a strong way.

On a practical level, this would involve nothing more than entering 1 or 2 of addresses into blockchain.info's Taint page and seeing if the other address is on that list, but in an automated way, so one doesn't need to use CTRL-F.

Like, find out if two addresses have a X% or more linkage, otherwise forget it!

dexX7

legendary

Activity: 1106

Merit: 1026

Quote from: domob on July 09, 2013, 03:43:53 AM

Excactly. Without having thought it through, what about simply applying Dijkstra's algorithm? Its complexity (when edges are stored in a heap) is like N log N, where N is the order of magnitude of number of addresses / transactions, which seems feasible to me. But please correct me if not, as I said, I haven't really thought that through.

Dijkstra's helps to find the shortest path, but I'm not sure if it reduces the complexity at all in this case, because each edge weight is equal and thus there is no path in favor and so we'd start with the source address and visit each neighbor. If target isn't found, we'd need to visit each neighbor of each neighbor. If it's not found, each neighbor of each neighbor of each neighbor and so on. I guess that would take something like E(k^n) = k^0 + k^1 + k^2 ... steps, where k is the number of connections per node and n is the search depth.

O(n*log(n)) (n for comparison, log(n) for going deeper in a tree) is the best possible complexity for searching based on pairwise comparison, but we don't have any attribute like "this tx-path is more likely than the others" to create an order.

Please correct me if I'm wrong, this is all stuff I know only vague about.

domob

legendary

Activity: 1135

Merit: 1166

Quote from: piotr_n on July 09, 2013, 03:25:26 AM

This is not an impossible problem to solve, buy rather beyond my math skills.
You'd definitely want to use some smart algo here - probably some flavor of finding the shortest route between two nodes in a graph.
Analyzing all possible paths is too complex.

Excactly. Without having thought it through, what about simply applying Dijkstra's algorithm? Its complexity (when edges are stored in a heap) is like N log N, where N is the order of magnitude of number of addresses / transactions, which seems feasible to me. But please correct me if not, as I said, I haven't really thought that through.

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

This is not an impossible problem to solve, buy rather beyond my math skills.
You'd definitely want to use some smart algo here - probably some flavor of finding the shortest route between two nodes in a graph.
Analyzing all possible paths is too complex.

dexX7

legendary

Activity: 1106

Merit: 1026

You'd need to walk through each possible path till you find a connection, if any. Quite complex. :/

Cyberdyne

hero member

Activity: 630

Merit: 500

I know blockchain.info has it's Taint Analysis thing, but you can only enter 1 address, and then you need to search for the 2nd address manually, on the page that's returned.

Does anyone know of a place I can input 2 addresses, and have it show me the shortest list of transactions that connect them? (If there is any connection at all)?

Topic: Find shortest path between two addresses? (Read 2709 times)