It seems that you are generating a full density matrix here:
so it seems you are already using a full matrix (which uses by far the most memory). It might help more to address that part than to address others later (sparse) parts.
At any rate, simply converting the resulting simlarity_matrix_np to a scipy.sparse format (COO in particular), using scipy.sparse.coo_matrix, and then passing the sparse graph to Graph.Adjacency (or its weighted counterpart) will be about as efficient as you can get.
Running the walktrap algorithm in C or Python should not make a difference (as @szhorvat already explained here). (Unless the VertexDendrogram consumes a lot of memory, perhaps you can confirm this is not the case @iosonofabio or @tamas)?