It isn't clear to me why you are adding the additional indirection of the String names for the nodes. Wouldn't it make more sense for your Edge constructor's signature to be something like public Edge(String, Node, Node) instead of public Edge (String, String, String)?
I don't know where clone would help you here.
ETA: If the danger comes from having the node name changed after the node is created, throw an IllegalOperationException if the client tries to call setName() on a node with an existing name.