I think you're on the right track, but perhaps haven't used the right settings on the fractal.
Make a black solid, layer it over your image with a multiply blend mode, and apply fractal noise.
You are likely going to want to use a very fine fractal so that the pattern is not visible and small enough that it appears to be correlating to the very tiny lights in the image. I did a quick test and it seems to work great. With your image grabbed from this page at 535 x 357, a fractal scale of 2 seemed to work well, with the evolution animated to 12 over 10 secs. Complexity is also turned up to 10 to get some fine grain in the fractal (with default type settings). If you're working at a higher resolution the scale and complexity settings will likely be different, so you will need to experiment.
You could even layer several precomps to create more randomness and/or experimenting with blending these over your original image with Add or Screen.
Finally, if you really want to get crazy, if you made the fractal layer 3D and positioned it so it's "parellel" with the ground plane in your image, you could get finer detail where the ground is farther away. Or if you're not comfortable working that way, create two or more fractal layers with different levels of detail, and create soft masks so that the finer fractal is affecting the top part of the image and the larger fractal the bottom.
Hope that helps!
