Economists and sociologists disagree over markets' potential to assume functions typically performed by networks of personal connections, first among them the transmission of information. This paper begins from a model of labor markets where social ties are stronger between similar individuals and firms employing productive workers prefer to rely on personal referrals than to hire on the anonymous market (Montgomery (1991). However, we allow workers in the market to engage in a costly action that can signal their high productivity, and ask whether the possibility of signaling reduces the reliance on the network. We find that the network is remarkably resilient. To be effective signaling must fulfill two contradictory requirements: unless the signal is extremely precise, it must be expensive or it is not informative; but it must be cheap, or the network can undercut it.