For those who use NeighborhoodGraph, be aware: when called with default options, this functions performs much worse than it should.

The reason is that it computes a graph layout even if the result is never displayed.

Let's see how slow it is on a big graph:

g = RandomGraph[BarabasiAlbertGraphDistribution[50000, 3]];

NeighborhoodGraph[g, 1]; // AbsoluteTiming
(* {61.2058, Null} *)

And now do the same computation using AdjacencyList:

Subgraph[g, Append[AdjacencyList[g, 1], 1]]; // AbsoluteTiming
(* {0.019827, Null} *)

It's 3000 times faster, even though it does the same thing! Why? Because NeighborhoodGraph recomputes the graph layout. Turn this off, and it becomes fast:

NeighborhoodGraph[g, 1, GraphLayout -> None]; // AbsoluteTiming
(* {0.018846, Null} *)

Why does NeighborhoodGraph compute the graph layout? I do not know, but it makes no sense at all, given that the result may never be displayed. Mathematica can generally work just fine with graphs that are simply too large to visualize in a reasonable amount of time. But not NeighborhoodGraph.

What is frustrating is that this problem was reported 4 years ago, and mentioned multiple times on this very site. Yet it is still unfixed in version 11.1. Unfortunately, this is an all too common experience with Graph-related functions.