Best database solution for highly interconnected entities?

I'm building a service (or rather a set of microservices) to serve as the backend for a social-network-like website. In short that means the following for my data: - millions of entities - with dozens of attributes - with potentially thousands of connections between the entities that change over time (like on Facebook, someone might have thousands of "friends"). - (there is more than one type of connection, each potentially numbering in the thousands) - connection examples: - entity A knows entity B - entity A has blocked entity B - etc. - conceptually each entity maintains long lists of identifiers of other entities - and I need to be able to do searches where - I can search all entities based on a set of attributes to match - while filtering out already existing connections of the initiating entity I'm trying to figure out what would be the best database solution to store this data. I'm not well-versed in database tech, so I need some suggestions to consider. I know SQL / relational databases can easily scale for the first 2 criteria (number of entities and number of attributes), but I'm not sure how well suited they are for managing the connections. I need a suitable database tech, which can also be set up in a distributed fashion - and ideally available in a cloud environment. If that is a SQL database, how would I store and manage the connections?