Usually, another way to control the exported image size would be:
Export["graph.png", graph, ImageSize -> 2000]
This doesn't work correctly unless you prepare the graph with a sufficiently thin EdgeStyle. I did that in the example graph that I initially played with, because it looked better in the notebook to begin with.
Here is what I get in the external file from the above export command applied to a graph defined as
graph = CompleteGraph[100, EdgeStyle -> Thickness[.0001], ImageSize -> 360]

and here is what I get when I double the width, ImageSize -> 4000:

There is still something buggy to see here, though: the Thickness of the circles is scaled up, in the same way that the edge thickness becomes too thick if I don't set it to a small value beforehand.
End edit
In fact, I wonder if it would be better for you to export in vector format and not in a rasterized bitmap format. For example, if you can work with PDF files, you get much smaller file sizes with lots of detail. With this graph
graph = CompleteGraph[100, EdgeStyle -> Directive[Thin,Opacity[.2]], ImageSize -> 360]
and the export command
Export["graph.pdf", graph]
you get a 77kB PDF file, whereas the exported PNG file above is almost 7MB large. Note that I didn't include an image size in the last command because it is irrelevant for the amount of detail in the exported vector format.
If you want to publish the exported figure on the web, it may also be useful to export as SVG because most browser now support it. Try this:
Export["graph.svg", graph]
and drag it to Firefox to see the amount of detail in this file.