Lets say I'm Sam and I have 10 friends. Tomorrow I change my name to
Mark with a new phone number, however I still have those 10 friends
that I call. Lets say that , that is enough to conclude that Mark's
identity can be traced to Sam, by going through his call records,
which are similar to what Sam used to have. Now if one or more of
those 10 friends may also change identity, with the property that he
still calls the same people ,holding true, is it possible for us to
trace Mark's identity back to Sam.

This is just an example. What is the approximate mathematical model to
capture this general problem. I dont need extreme precision, i.e. I
know if all 11 friends call only each other and they all change their
identity, ie their cell phone number, its impossible to get the trace.

What a strange question. Could you give some context to help someone
answer this (and persuade us this is not to be used for a nefarious
purposes eg a terrorist cell)

Well, this is anti-terrorism idea, so nothing nefarious about it. If
Sam is a member of a terrorist cell , you want this model to be
implemented by cell phone service providerr. Thats so much for the
context, which started out purely as a discussion at a coffee table.

Let me know if more information is required about it.

If each friend has the same situation of Sam where they have a defined
amount of friends who they call / get calls from with no addition or
subtraction to that list of friends then the trace would be fairly
easy, if one of Sams friends had a friend list of

Person a
Person b
Person c 
Sam
Person d 
Person e

before Sam became Mark and 

Person a
Person b
Person c 
Mark
Person d 
Person e

after, then clearly Sam is Mark, however if another person on that
list changed info then you would need to look at another of Sam's old
friends call logs and try to get 2 equations with 2 unknowns, at least
that is my first guess at the problem.