Comment les graphiques de réseaux sociaux sont-ils implémentés? La liste d'adjacence ou la matrice d'adjacence

Question

Plus précisément, ma question est de savoir comment les réseaux sociaux comme Facebook mettent en œuvre leurs graphiques de relation.

Comme il y a beaucoup d'opérations qui interrogent les relations, la contiguïté Matrix est une bonne idée. Mais alors le graphique se développe si rapidement jour après jour que de nouvelles personnes font des comptes. Donc, la matrice d'adjacence peut entraîner beaucoup de gaspillage d'espace.

Answer 1

J'avais la même question que vous. Presque toutes les ressources que j'ai trouvées ont dit que cela dépend de la «densité» du graphique. Utilisez la liste d'adjacence pour un graphe fragmenté, une matrice d'adjacence pour un graphe dense. Selon wikipedia, la densité du graphe simple est non orienté:

2*|E|/|V| * (|V|-1) 

du petit ensemble de données Facebook je suis arrivé, la densité est d'environ 0,008 qui est je suppose que relativement peu. Alors peut-être que la liste d'adjacence est meilleure dans les réseaux sociaux comme Facebook (graphique non orienté).