0

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?

Arash Mohamadpour
  • 13
  • 4
  • There are many Q&A on this site about getting the intersection of two sets. You need the size of that intersection. So maybe search around depending on your language environment. – trincot Sep 06 '22 at 14:18
  • Thank you for answering :) can you lead me to one of these Q&As? I couldn't find one. The language doesn't matter, python would work for me. – Arash Mohamadpour Sep 06 '22 at 14:23
  • https://stackoverflow.com/search?q=intersection+of+sets – trincot Sep 06 '22 at 14:33

2 Answers2

0
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
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
0

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.

btilly
  • 43,296
  • 3
  • 59
  • 88