Tuesday, March 23, 2010

[piokirhg] Bad links in a trust network

Nodes are people.  Directed edges represent trust relationships (one concrete example: X believes Y is not a spammer).

One might try to answer "Can I trust Z?" by finding a path from yourself to Z.  But if trust is a binary question, an attacker needs to infiltrate only one node in the trust network to join it.  We need a probabilistic model.

If I discover Z cannot be trusted (I look at a message from Z and see it is spam), I need to modify the probabilities on the network to account for this new information.  However, probabilities, which are probably attached to nodes and edges, must be updated in a way that accounts for every path between you and Z.  Who was it between you and Z that allowed Z into the trust network?  Suppose we discover (somehow) it was Q. Was it a deliberate malicious act (in which case all of Q's links should be completely distrusted), or just that Q is not a good judge or character (in which case Q's links are only slightly adjusted)?  The nodes are people: people make mistakes.

The problem seems formidable when the entire trust network is visible.  Harder still is you can only see local portion of the network (friends and friends of friends). (We leave unstated how a distant connection between you and Z is even made in the first place and how you query paths between you and Z.)   Is it Bayesian network structure learning?

No comments :