0
$\begingroup$

I have a weighted graph representing traffic network. Nodes represent the locations and vertices represent available paths between locations. Weight values represent number of the passages on the path.

I would like to cluster based on the similarity of the weight values (i.e. number of passages) and establish different traffic frequentation zones. The weights in different zones are roughly similar except for a few outliers.

In the clustering techniques I've seen the methods often involve using weights as a "distance" between the nodes and finding the best way to split the graph based on the distance and connectivity. Here, I'm trying to cluster nodes according to the weights of the edges linking them. For example there are certains zones in the graph where all the nodes are connected by vertices with weights of ~4, these should form one cluster, and in another distinct part of the graph the weights are ~1, this forms another cluster. Do you know any methods for this?

Perhaps my problem is not well suited to graph theory.

$\endgroup$
  • 1
    $\begingroup$ I don't understand what you are asking. What are you trying to cluster? Each cluster is a group of nodes? What do you mean by "based on the similarity of weight values"? Did you have in mind some way for measuring the similarity of two nodes? If so, what? Also, what do mean by "frequentation zones"? $\endgroup$ – D.W. Nov 16 '17 at 0:32
  • $\begingroup$ I'm sorry if my question was confusing. I'm trying to cluster nodes according to the weights of the edges linking them. For example there are certains zones in the graph where all the nodes are connected by vertices with weights of ~4, these should form one cluster, and in another part of the graph the weights are ~1, this forms another cluster. $\endgroup$ – cyts Nov 16 '17 at 0:41
  • $\begingroup$ When I was talking of "frequentation zones" it was specific to my initial problem where I was looking at frequency of passages which make up the vertices weight. $\endgroup$ – cyts Nov 16 '17 at 0:43
  • $\begingroup$ OK, that helps, thanks. If I suggest a proposed clustering (a proposed division of nodes into clusters), do you have in mind a way to measure how good that clustering is? It'd be great if you could edit the question to make this clearer for people who encounter the question for the first time, so they don't have to read the comments to understand what you're asking. $\endgroup$ – D.W. Nov 16 '17 at 0:47
  • $\begingroup$ My guess was checking for an average autocorrelation value over some proposed neighbours until the next cluster is reached ? $\endgroup$ – cyts Nov 16 '17 at 0:53

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.