I want to create a NFT graph in which each nft is a node and two nfts will have an edge between them if they have at least n owners in common.

For example:
nft1 has owners ['a', 'b', 'c', 'd', 'e']
nft2 has owners ['g', 'h', 'e', 's', 'a', 'b', 'd']
nft3 has owners ['g', 'h', 's', 'c']
and here n=3.

So now:
nft1 and nft2 are connected because they have 4 owners in common (['a', 'b', 'd', 'e'])
nft2 and nft3 are connected because they have 3 owners in common (['g', 'h', 's'])
BUT nft1 and nft3 are not connected because they only have 1 owner in common (['c'])
Result of the describes graph

Does anyone have any idea how i can accomplish this?

CodePudding user response：

SORT nfts into order of decreasing number of owners
LOOP A over sorted nfts
   LOOP B over sorted nfts starting at A 1
      Count common owners of A and B
      IF count > N
          Add edge between A and B

CodePudding user response：

The idea behind https://stackoverflow.com/a/26028865/585411 applies here.

1. For each NFT emit (owner, NFT) pairs.
2. MapReduce groups by owner.
3. For each (owner, [NFT1, NFT2, ...]) emit ((NFTi, NFTj), owner) pairs with i < j.
4. MapReduce groups by NFT pairs.
5. For each ((NFTi, NFTj), [owner1, owner2, ...]) pair with enough owners, emit (NFTi, NFTj) and (NFTj, NFTi) pairs.
6. MapReduce groups by NFT
7. Each NFT now has a list of its edges.

This can be done in a distributed way with a real MapReduce. Or with a fake MapReduce as described there. Or with a hashmap if you have relatively few owners and NFTs. But the logic pattern remains the same.