For the naive approach of going for neighbours, have a look at the ego_graph() function of the igraph R package. Alternatively, given a list of genes (e.g. those in your network) and an interaction graph, you could extract the relevant subgraph as described here. The method is implemented as get_relevant_subgraph() in my perl Graph module. Depending on your objective, this may give you a more meaningful graph.

Apart from what @Jean-Karim Heriche suggested, I would also ask the OP to take a look at this paper that uses an integrated approach of SWC, DECOMP and SSS. Might be worth taking a shot since it works on sparsely PPI network connections.

Another thing which I have recently come across while I was working on gene regulatory network with VIPER was the use of leading edge analysis that uses the GSEA on the gene expression signature. This work was first shown by Subramanium et. al and the paper can be found here. Take a look at both and see which fits well.

There is apparently a new paper as well published a year back based on transcriptome studies. But I am sure it can be used for your own purposes as well.