How are PPI networks constructed?
It depends on the PPI network. Some, like DIP are exclusively experimental, depending on high-throughput robotic AP/MS, Tandem Affinity Purification, Y2H, cross-linking with formaldehyde, clever things involving half-fluorophores, etc. There are a lot of different methods, is what I'm saying. Y2H has a high false-positive rate, immunoprecipitation is expensive (antibodies cost money), others have other drawbacks.

You can also exploit the existing huge body of research using text mining, even though that's really crude. (It boils down to: protein A and protein B or their pseudonyms are often mentioned in the same sentence, they must be related somehow). There are also RNASeq methods, where you just do hundreds of RNASeq experiments and two genes that correlated(or inversely correlated) are probably interacting in some way. If two proteins interact in organism A and they have closely-related homologs in organism B, the proteins probably interact in organism B too. 

In short: In a lot of different ways. It would be wise to check the provenance of a link in such a network and handle it differently depending on what kind of link it is if you're working with big networks like this.

I don't know that there are any companies that do this commercially, but the Max Delbruck Center will talk to you about screening something custom. I don't know how long it would take but 2000 proteins would not take a long time, relatively speaking. The human genome has tens of thousands of proteins, so 2000 proteins would only be a few percentage points of the effort. However if they're totally novel there's probably library setup times and overhead, but I don't even have a good guess how long this would take. Depends on who you talk to, I expect.