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.
  • $\begingroup$ Sure, there are an infinite number of measures -- one can invent any crazy thing. I don't think a question asking "give me a list of all possible measures" is answerable or useful. Can you narrow down your question? If someone gave you a long list of possibilities, how would you choose among them? What criteria would you use? Are there some requirements that you want the measure to satisfy? You'll have to look at your application and think about what makes sense there -- you know your application, and we don't, so only you can do that part. $\endgroup$ – D.W. Jul 3 '17 at 15:15
  • $\begingroup$ @D.W. updated the question $\endgroup$ – dineshdileep Jul 4 '17 at 4:37
  • $\begingroup$ You might want to consider not deleting edges and using a dense graph instead. This way you don't have to identify clusters. And it might avoid you corner cases such as multiple connected components, etc. With a dense graph every time you add a new vertex you can find the max edge to do so, and see if it falls below a minimum: super simple. $\endgroup$ – marcv81 Jul 4 '17 at 6:46
  • $\begingroup$ If $v$ is the vertex in cluster $C \subseteq V$, did you consider the measure $\deg(v) / |C|$? (You can also lift this to use the weights.) Or you use the distance to the vertex as far as possible away from $v$ in $C$. $\endgroup$ – Pål GD Jul 4 '17 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.