You probably trying to create a graphical output of it and that takes time. But what would you able to see in 15000 nodes and 75000 edges ? Is it useful, do you really need it? You also have VertexLabeling -> True which will be a complete mess of things visually. Large networks can be built quickly and mostly are used to run algorithms on them. It takes less than 1/10 of a second to build a random graph with 15000 nodes and 75000 edges on my machine - suppressing graphical output:
In[]:= g = RandomGraph[{15000, 75000}]; // AbsoluteTiming
Out[]= {0.032981, Null}
And it takes say 2 seconds:
In[]:= c = FindGraphCommunities[g]; // AbsoluteTiming
Out[]= {1.180309, Null}
to find 14 Communities inside that graph:
In[]:= c // Length
Out[]= 14
