How can I track my stolen iPhone 4S phone? My iPhone 4S was stolen and I reported it to the police and my network. 

By my iCloud account through Find My iPhone, I had request for remote locking. I don't know if the remote locking worked because I didn't get any mail.
After 1 week when I checked my iCloud account again, I saw contacts that I don't know and there are none of my previous contacts. (How is it possible if it's my iCloud account?). 

How can I track my stolen iPhone 4S phone?
It sounds like whoever has your phone hasn't bothered (most likely doesn't know how to) to change the Apple ID and has entered their own contacts in. You should take this information to the police. 

Then check if there's a contact labelled "Mum", call the persons mother and tell them that their child is a thief :-)

Best of luck!