Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity values below a threshold). Now, let us say I have a group of nodes who are known to be similar (say determined by a clustering algorithm). I randomly pick a node from the graph and I want to measure some notion of distance of this node to the given group (or cluster). What are the different measures considered in this regard? I understand that one can plainly look at the number of edges in the shortest path between the node and the group. Are there more measures?
UPDATE: Upon comments from others, I have decided to give the application as well. Assume that we have been given a sparse graph. Now, we have uses who select nodes from this graphs. Typical users select nodes which are close to each other. Thus, they sample from a small neighborhood in the graph and they go far outside that range very rarely. Assume that you have a set of users like that and their past choices. Given this data, there are two problems now
- Identify scenarios when the user selects a node far outside his usual neighborhood in future.
- Identify spam users (or bots) which randomly sample from this graph.