My graph consists of a computer network topology where each vertex is a physical node/device (depicted using its IP address). Two vertices will have an edge if the nodes have had communication with each other. We call each communication a conversation, which will have multiple packets transferred in both directions. Multiple edges between two nodes are thus obvious.

For any conversation, I need to capture multiple features, such as:

  1. Bytes transferred between the two nodes
  2. No. of packets transferred between the nodes
  3. The duration of data transfer between the nodes
  4. The inter-arrival time of packets between the nodes

While trying to find communities in my graph, I am coming across certain difficulties:

  1. Should I go for multi-attribute edges (with each of the above feature taken as a weight), or should I be taking something like weighted average of all features and make them a single attribute?
  2. Will I obtain better results if each of the above feature is taken as a separate edge-attribute? If so, how and why?. Does it influence 'modularity' calculations? Again, how? (Links to past works or papers will do)
  3. What algorithms may suit my task well? I do not know about other algorithms apart from Louvain (igraph implementation).

First off, community detection is a also known as graph clustering. They are the exact same thing. Second, I am not aware of any widely used program that works on multi-graphs. The current state of affairs is that you should incorporate your domain-specific knowledge to combine information into a single edge weight and cluster thusly. It is possible of course to create more than one graph and cluster them independently. It could be interesting to analyse/reconcile such groups; it depends on the questions that you are asking. Well known graph clustering algorithms are indeed Louvain, also RNSC, MCL, APC.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.