The best way to do network mapping on Linux is to use 'nmap', which is literally, network mapper.
You can do it one of two ways. The first is a ping scan, which will just send a ping to IPs and report back the IPs that respond. For instance:
msimmons@msimmons-laptop:~$ nmap -sP 192.168.1.1-254
Starting Nmap 4.53 ( http://insecure.org ) at 2009-12-12 07:52 EST
Host Wireless_Broadband_Router.home (192.168.1.1) appears to be up.
Host 192.168.1.3 appears to be up.
Host 192.168.1.4 appears to be up.
Host msimmons-laptop.home (192.168.1.8) appears to be up.
Host 192.168.1.100 appears to be up.
Nmap done: 254 IP addresses (5 hosts up) scanned in 0.869 seconds
That works well enough, but lots of machines have firewalls setup to block incoming ICMP packets, and so won't reply to a ping request.
If it's an all-Linux network, you can scan for port 22, which is the ssh port. That's done like this:
root@msimmons-laptop:~# nmap -sS -p 22 192.168.1.1-254 | grep -B3 open | grep ports
Interesting ports on 192.168.1.4:
Interesting ports on 192.168.1.5:
Interesting ports on msimmons-laptop.home (192.168.1.8):
You might want to notice that I've parsed the nmap output through grep a couple of times. By default, the output is verbose, and nmap reports on every host it finds, whether or not the port is open. Since I only care about hosts with that open port, I grepped out the lines that reported the IP, only if the result was that the port was open.
Also, I performed a "syn" scan, which only initiates 1 step out of the three that comprise the TCP handshake protocol. This means that it's able to identify open, closed, and filtered ports. It also requires root privileges to create the raw socket necessary to perform this type of scan.
Once you've done this, go to the physical switch and check the lights. If there are more lights lit than hosts who responded, investigate by following the cables.