I was wondering if any of you could help me understand the response I got from this clustering algorithm (Metis). As you probably can see, I'm trying to cluster IP addresses based on common records accessed. The graph file contains one node per IP, and weighted edges, where the weight is equal to the number of common accesses. A couple of specific questions:

  • This algorithm requires a pre-defined number of clusters. How should I, based on this response, decide on the optimal number? (The algorithm is really fast, so repeated runs is possible).

  • How should I go about evaluating this clustering? I don't have a training/test set as of now. Should I create one? How would I do that with a binary access log?

If you have any other tips regarding this algorithm, they are more than welcome!

Thanks for taking a look! Here comes the response:

METIS 5.0 Copyright 1998-13, Regents of the University of Minnesota
(HEAD: , Built on: Jul  1 2014, 14:23:44)
size of idx_t: 32bits, real_t: 32bits, idx_t *: 64bits

Graph Information -----------------------------------------------------------
 Name: gt2rec_gt2ip_b_rec_sorted_nobots_pdf_full.graph, #Vertices: 103924, #Edges: 34678560, #Parts: 10

Options ---------------------------------------------------------------------
ptype=kway, objtype=cut, ctype=shem, rtype=greedy, iptype=metisrb
dbglvl=0, ufactor=1.030, no2hop=NO, minconn=NO, contig=NO, nooutput=NO
seed=-1, niter=10, ncuts=1

Direct k-way Partitioning ---------------------------------------------------
 - Edgecut: 16083558, communication volume: 662037.

 - Balance: constraint #0:  1.030 out of 0.000

 - Most overweight partition:
 pid: 4, actual: 10704, desired: 10392, ratio: 1.03.

 - Subdomain connectivity: max: 9, min: 9, avg: 9.00

 - The original graph had 1243 connected components and the resulting 
   partitioning after removing the cut edges has 2362 components.
Timing Information ----------------------------------------------------------
 I/O:                  7.162 sec
 Partitioning:        10.511 sec   (METIS time)
 Reporting:            2.118 sec

Memory Information ----------------------------------------------------------
  Max memory used:       1021.427 MB

1 Answer 1


Reporting back with what I've found out:

Edge cut: This is the number of edges that stretch between the partitions, and are "cut" when the partitioning is done. If the edges are weighted, it is the sum of weights. Naturally you want this to be as low as possible.

Communication volume: This is the number of nodes, or sum of weights for the nodes that are connected to nodes in other partitions. Those nodes connected by "edge cut"-edges if you will.

Subdomain connectivity: The number of other partitions each partition is connected to (using the "edge cut"-edges).

The original graph had 1243 connected components and the resulting partitioning after removing the cut edges has 2362 components.

This means that the partitioning has split connected components in the graph, resulting in an increased number of components.

Furthermore, I've found that plotting the edge cut for different partitionings produce a graph similar to that used to decide on the optimal number of cluster in k-Means clustering. A "knee" can be found where for the optimal partitioning.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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