我没有使用图形数据库的密集图的经验,但我不认为密集图是一个问题。由于您将使用图算法,我想,您将受益于使用图数据库(取决于算法的复杂性 - 越多“跳跃”,您从恒定边缘遍历时间中受益越多)。
一个很好的权衡可能是使用非原生图形数据库之一(如Titan,其后续JanusGraph,Mongo Db,...),它实际上使用基于列的存储(Cassandra,Barkley DB,..)作为其后端。